In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
A factor base is a relatively small set of distinct prime numbers P, sometimes together with -1. Say we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which , , and can be completely factorized over the chosen factor base—that is, all their prime factors are in P.
In practice, several integers x are found such that has all of its prime factors in the pre-chosen factor base. We represent each expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresponds to multiplication of these expressions. A linear dependence relation mod 2 among the rows leads to a desired congruence . This essentially reformulates the problem into a system of linear equations, which can be solved using numerous methods such as Gaussian elimination; in practice advanced methods like the block Lanczos algorithm are used, that take advantage of certain properties of the system.
This congruence may generate the trivial ; in this case we try to find another suitable congruence. If repeated attempts to factor fail we can try again using a different factor base.
Factor bases are used in, for example, Dixon's factorization, the quadratic sieve, and the number field sieve. The difference between these algorithms is essentially the methods used to generate (x, y) candidates. Factor bases are also used in the Index calculus algorithm for computing discrete logarithms.
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.
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
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.
We present and demonstrate a novel assay for the detection and quantification of microRNA (miRNA) that leverages isotachophoresis (ITP) and molecular beacon (MB) hybridization. We use ITP to selectively preconcentrate miRNA from total RNA. We simultaneousl ...
We introduce VSH, very smooth hash, a new S-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an S-bit composite. By very smooth, we mean that the smoothnes ...
We propose an efficient variant for the initialisation step of quadratic sieving, the sieving step of the quadratic sieve and its variants, which is also used in sieving-based algorithms for computing class groups of quadratic fields. As an application we ...