Quadratic Residues#
Given an \(n\), the product of two small primes, ffind a \(t, x, y\) so that \(4tn = x^2 - y^2\).
An essential part of this is quadratic congruences
\(x^2 \equiv c \mod m\)
If you can solve mod p
Lagrange’s theorem?
\(p - x \ne x\)
\(px \equiv 0 \mod p \iff x \equiv 0 \mod p \iff x^2 \not\equiv c \mod p\)
theorem
\(x^2 \equiv -1 \mod p\) is solvable \(\iff p \equiv 1 \mod 4\)
theorem
\(N(x, c) = \text{count}\{ p \le x \mid x^2 \equiv c \mod p \text{ soluble} \} = \pi(x)/2 + \text{error}\)
It’s very fast to determine whether \(x^2 \equiv c \mod p\) is soluble, because underlying algrithm based on euclidean algorithm?
Quadratic Residue (QR)
Quadratic Non Residue (QNR)
\(0\) residue class is undefined
Legendre Symbol
\(1 + (\frac{c}{p})_L = \text{number of solutions to } x^2 \equiv c \mod p\)
Dirichlet generalization
Acknowledgements#
CENT 2023 [ h ] Vaughan, Robert. A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University. [ book ]