# Factor base

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Factor_base
> Markdown URL: https://mediated.wiki/source/Factor_base.md
> Source: https://en.wikipedia.org/wiki/Factor_base
> Source revision: 1308306520
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Small set of prime numbers used in sieving algorithms}}

In [computational number theory](/source/computational_number_theory), a '''factor base''' is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive [sieving](/source/sieve_theory) for potential factors of a given integer.

==Usage in factoring algorithms==
A factor base is a relatively small [set](/source/set_theory) of distinct [prime number](/source/prime_number)s ''P'', sometimes together with −1.<ref>{{citation|first=Neal|last=Koblitz|title=A Course in Number Theory and Cryptography|year=1987|publisher=Springer-Verlag|isbn=0-387-96576-9|page=133}}</ref> Suppose we want to factorize an integer ''n''. We generate, in some way, a large number of integer pairs (''x'', ''y'') for which <math>x \neq \pm y</math>, <math> x^2 \equiv y^2 \pmod{n}</math>, and <math>x^2 \pmod{n} \text{ and }y^2 \pmod{n}</math> 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 <math>x^2 \pmod{n}</math> has all of its prime factors in the pre-chosen factor base. We represent each <math>x^2 \pmod{n}</math> expression as a [vector](/source/vector_space) of a [matrix](/source/matrix_(mathematics)) 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 <math>x^2 \equiv y^2 \pmod{n}</math>.<ref>{{citation|first1=Wade|last1=Trappe|first2=Lawrence C.|last2=Washington|title=Introduction to Cryptography with Coding Theory|edition=2nd|year=2006|publisher=Prentice-Hall|isbn=978-0-13-186239-5|page=185}}</ref> This essentially reformulates the problem into a [system of linear equations](/source/system_of_linear_equations), which can be solved using numerous methods such as [Gaussian elimination](/source/Gaussian_elimination); in practice advanced methods like the [block Lanczos algorithm](/source/block_Lanczos_algorithm_for_nullspace_of_a_matrix_over_a_finite_field) are used, that take advantage of certain properties of the system.

This congruence may generate the trivial <math>\textstyle n = 1 \cdot n</math>; 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.

==Algorithms==
Factor bases are used in, for example, [Dixon's factorization](/source/Dixon's_factorization_method), the [quadratic sieve](/source/quadratic_sieve), and the [number field sieve](/source/general_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](/source/Index_calculus_algorithm) for computing discrete logarithms.<ref>{{citation|first=Douglas R.|last=Stinson|title=Cryptography / Theory and Practice|year=1995|publisher=CRC Press|isbn=0-8493-8521-0|page=171}}</ref>

==References==
{{reflist}}

{{DEFAULTSORT:Factor Base}}
Category:Integer factorization algorithms

---
Adapted from the Wikipedia article [Factor base](https://en.wikipedia.org/wiki/Factor_base) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Factor_base?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.