Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Integer Factorization: Smoothness and Probabilities

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers the concept of smoothness in integer factorization, introducing the Dickman-de Bruijn function and its properties, along with theorems and corollaries related to smooth numbers and probabilities. The instructor explains how to analyze Dixon's method and the complexity of testing for smoothness.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (22)

Dixon's factorization method

In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by a polynomial. The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981.

Probability

Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin.

Integer factorization

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the process is called prime factorization, and includes the test whether the given integer is prime (in this case, one has a "product" of a single factor). When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist.

Smooth number

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers.

Factorization of polynomials

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems. The first polynomial factorization algorithm was published by Theodor von Schubert in 1793. Leopold Kronecker rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension.

Related lectures (49)

Integer Factorization: Quadratic Sieve

Covers the Quadratic Sieve method for integer factorization, emphasizing the importance of choosing the right parameters for efficient factorization.

Continuous Random Variables

Explores continuous random variables, density functions, joint variables, independence, and conditional densities.

Variance and Covariance: Properties and Examples

Explores variance, covariance, and practical applications in statistics and probability.

Probability and Statistics

Covers Simpson's paradox, probability distributions, and real-life examples in probability and statistics.

Probability and Statistics: Fundamental Theorems