Factor base

small set of prime numbers used in sieving algorithms

Uses your system voice; voice and rate in settings.

Q5428723Snapshot

≈ 2 min read

Names in other languages

  • glBase de factores
  • EnglishFactor base
  • SvenskaFaktorbas
  • 中文因數基底

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

edit edit source

A factor base is a relatively small set of distinct prime numbers P, sometimes together with −1.[1] Suppose we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which x≠±y, x2≡y2(modn), and x2(modn) and y2(modn) 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 x2(modn) has all of its prime factors in the pre-chosen factor base. We represent each x2(modn) 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 x2≡y2(modn).[2] 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 n=1⋅n; 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

edit edit source

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.[3]

References

edit edit source
  1. ^ Koblitz, Neal (1987), A Course in Number Theory and Cryptography, Springer-Verlag, p. 133, ISBN 0-387-96576-9
  2. ^ Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, p. 185, ISBN 978-0-13-186239-5
  3. ^ Stinson, Douglas R. (1995), Cryptography / Theory and Practice, CRC Press, p. 171, ISBN 0-8493-8521-0

Text derived from https://en.wikipedia.org/w/index.php?oldid=1308306520 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot factor-base-617770-daaf2adabb0ba5ae · hash daaf2adabb0ba5ae996ec01dcdd85d96e4d7cd28e5d28fd5f31164e11dfc39f9 · captured 1756397174.0 · version history

Cite this page as: encyclopegia.org, “Factor base”, snapshot factor-base-617770-daaf2adabb0ba5ae. https://encyclopegia.org/a/factor-base