| Congruence Of Squares |
Article Index for Congruence |
Website Links For Squares |
Information AboutCongruence Of Squares |
| CATEGORIES ABOUT CONGRUENCE OF SQUARES | |
| modular arithmetic | |
| integer factorization algorithms | |
|
:. Such a relationship carries information useful in trying to factor the integer ''n'': finding a Congruence Of Squares modulo ''n'' is something sought after in Integer Factorization . There follows from it that : This means that ''n'' divides (''x''+''y'')(''x''−''y'') but not (''x''+''y'') or (''x''−''y'') alone, so both (''x''+''y'') and(''x''−''y'') contain factors of ''n''. A simple s modulo ''n''. Here is an example. Say ''n'' = 35. A Perfect Square close to 35 is 36, and, conveniently, 36 ≡ 1 (mod 35). Now 1 is also a perfect square. Thus we have our congruence: : with gcd(6 + 1, 35) = 7 and gcd(6 - 1, 35) = 5. These are the two non-trivial factors of 35. |
|
|