Congruence of squares

The Legendre - congruence is a term from the mathematical branch of number theory. There is a congruence in the stands on each side a perfect square:

These named after Adrien -Marie Legendre congruences form the basis of several factorization. Using factor bases Legendre congruences there are produced with the aid of dividers in turn are calculated by whole numbers. Examples are the continued fraction method, the quadratic sieve and SQUFOF.

A Legendre congruence modulo has exactly two solutions when the modulus is a prime number greater than two. These are called trivial solutions and loud

If the modulus, however, is a composite number, so has a Legendre congruence 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
  • Number Theory
Modular arithmetic Square number Adrien-Marie Legendre
504800
de