Concept

# Factor base

Summary
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. Usage in factoring algorithms 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 x \neq \pm y, x^2 \equiv y^2 \pmod{n}, and x^2 \pmod{n} \text{ and }y^2 \pmod{n} 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 x^2 \pmod{n} has all of its prime factors in the pre-chosen factor base. We represent each x^2 \pmod{n} expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresp
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.
Related publications

Related people

Related units