Legendre congruence

The Legendre congruence is a term from the mathematical branch of number theory . It is a matter of congruence , with a square number on each side :

${\displaystyle x^{2}\equiv y^{2}\ {\pmod {m}}}$

These congruences, named after Adrien-Marie Legendre , form the basis of several factorization methods . Using factor bases , Legendre congruences are generated there, with the help of which, in turn, divisors of whole numbers are calculated. Examples are the continued fraction method , the quadratic sieve and SQUFOF .

A Legendre congruence has exactly two solutions modulo if the modulus is a prime greater than two. These are called trivial solutions and are called ${\displaystyle m}$ ${\displaystyle m}$

${\displaystyle x\equiv \pm y\ {\pmod {m}}}$

On the other hand, if the modulus is a composite number , then a Legendre congruence has additional solutions.

swell

• Hans Riesel : Prime Numbers and Computer Methods for Factorization. 2nd Edition. Birkhäuser, Boston 1994, ISBN 0-8176-3743-5 , pp. 156-158
• Song Y. Yan: Number theory for computing. 2nd Edition. Springer, 2002, ISBN 3-540-43072-5 , pp. 234-237