Second Degree Congruences

In Section 5.2, we learned how to solve linear congruences. This chapter introduces quadratic congruences. Some integer factoring algorithms and some protocols require the rapid solution of quadratic congruences. Certain primality testing methods become improved by the ability to tell whether some second degree congruences have solutions, although one need not find them. See the number theory texts 99, 78 and 98 for more about second degree congruences.