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. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.
A positive integer is called B-smooth if none of its prime factors are greater than B. For example, 1,620 has prime factorization 22 × 34 × 5; therefore 1,620 is 5-smooth because none of its prime factors are greater than 5. This definition includes numbers that lack some of the smaller prime factors; for example, both 10 and 12 are 5-smooth, even though they miss out the prime factors 3 and 5, respectively. All 5-smooth numbers are of the form 2a × 3b × 5c, where a, b and c are non-negative integers.
The 3-smooth numbers have also been called "harmonic numbers", although that name has other more widely used meanings.
5-smooth numbers are also called regular numbers or Hamming numbers; 7-smooth numbers are also called humble numbers, and sometimes called highly composite, although this conflicts with another meaning of highly composite numbers.
Here, note that B itself is not required to appear among the factors of a B-smooth number. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. In many scenarios B is prime, but composite numbers are permitted as well. A number is B-smooth if and only if it is p-smooth, where p is the largest prime less than or equal to B.
An important practical application of smooth numbers is the fast Fourier transform (FFT) algorithms (such as the Cooley–Tukey FFT algorithm), which operates by recursively breaking down a problem of a given size n into problems the size of its factors.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it. The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer is of the form: in O and L-notations.
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2 n⌋ + 1 bits) is of the form in O and L-notations. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots).
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties.
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
Algebraic number theory is the study of the properties of solutions of polynomial equations with integral coefficients; Starting with concrete problems, we then introduce more general notions like alg
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
Probabilistic arguments about the existence of technological life beyond Earth traditionally refer to the Drake equation to draw possible estimates of the number of technologically advanced civilizations releasing, either intentionally or not, electromagne ...
We consider the problem of sampling from a density of the form p(x) ? exp(-f (x) - g(x)), where f : Rd-+ R is a smooth function and g : R-d-+ R is a convex and Lipschitz function. We propose a new algorithm based on the Metropolis-Hastings framework. Under ...
MICROTOME PUBL2022
, ,
We present a novel framework for the reconstruction of 1D composite signals assumed to be a mixture of two additive components, one sparse and the other smooth, given a finite number of linear measurements. We formulate the reconstruction problem as a cont ...