# Computational Aspects ## Quadratic Residues as Computational Objects Quadratic residue theory is not only a theoretical subject. It also plays a major role in computational number theory, cryptography, primality testing, and algorithm design. Many arithmetic algorithms reduce to questions of the form: $$ x^2\equiv a\pmod n. $$ $$ x^2\equiv a\pmod n $$ Typical computational tasks include: - deciding whether $a$ is a quadratic residue modulo $n$, - finding square roots modulo primes, - computing Legendre or Jacobi symbols, - solving quadratic congruences efficiently. The structure developed in classical number theory leads directly to practical algorithms. ## Fast Modular Exponentiation Euler criterion determines whether $a$ is a quadratic residue modulo an odd prime $p$: $$ a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\pmod p. $$ Efficient computation therefore requires fast exponentiation modulo $p$. The standard method is repeated squaring. To compute $$ a^k\pmod n, $$ write $k$ in binary form: $$ k=b_0+b_12+b_22^2+\cdots+b_r2^r. $$ Then powers $$ a,a^2,a^4,a^8,\dots $$ are computed successively modulo $n$. This reduces complexity from roughly $k$ multiplications to approximately $$ O(\log k) $$ multiplications. Fast modular exponentiation is fundamental throughout computational number theory. ## Computing Legendre Symbols Directly testing all squares modulo $p$ is inefficient for large primes. Quadratic reciprocity provides a fast recursive method for computing $$ \left(\frac{a}{p}\right). $$ The computation repeatedly uses: - modular reduction, - multiplicativity, - reciprocity, - supplementary laws for $2$ and $-1$. The process resembles the Euclidean algorithm. ### Example Compute $$ \left(\frac{37}{101}\right). $$ Using reciprocity, $$ \left(\frac{37}{101}\right) = \left(\frac{101}{37}\right), $$ since both primes are congruent to $1\pmod4$. Now reduce: $$ 101\equiv27\pmod{37}, $$ so $$ \left(\frac{101}{37}\right) = \left(\frac{27}{37}\right). $$ Factor: $$ 27=3^3. $$ Thus $$ \left(\frac{27}{37}\right) = \left(\frac{3}{37}\right)^3 = \left(\frac{3}{37}\right). $$ Further reciprocity reductions eventually produce the answer efficiently. ## Jacobi Symbol Algorithms The Jacobi symbol can be computed without factoring the denominator. This is crucial because factoring large integers is computationally difficult. Algorithms for the Jacobi symbol use: - reciprocity, - extraction of powers of $2$, - modular reduction. Their running time is polynomial in the number of digits of the input. This efficiency makes the Jacobi symbol important in cryptographic protocols and primality tests. ## Modular Square Roots Another important problem is solving $$ x^2\equiv a\pmod p. $$ When a solution exists, how can it be found efficiently? For primes satisfying $$ p\equiv3\pmod4, $$ a square root is given by $$ x\equiv a^{(p+1)/4}\pmod p. $$ Indeed, $$ x^2 = a^{(p+1)/2} = a\cdot a^{(p-1)/2}. $$ Since $a$ is a quadratic residue, $$ a^{(p-1)/2}\equiv1\pmod p, $$ so $$ x^2\equiv a\pmod p. $$ For general primes, the Tonelli-Shanks algorithm computes square roots efficiently. ## Tonelli-Shanks Algorithm The Tonelli-Shanks algorithm solves $$ x^2\equiv a\pmod p $$ for odd primes $p$. The method decomposes $$ p-1=2^sm, $$ where $m$ is odd. It then iteratively corrects powers using quadratic nonresidues until a square root is obtained. The algorithm is efficient and widely used in computational algebra systems and cryptographic software. ## Primality Testing Quadratic residue theory appears naturally in primality testing. Euler criterion suggests that if $p$ is prime, then $$ a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\pmod p. $$ Composite numbers violating this congruence can be detected quickly. This idea leads to the Solovay-Strassen primality test. More advanced tests, such as the Miller-Rabin test, also rely heavily on modular exponentiation and residue behavior. These probabilistic tests are extremely efficient for large integers. ## Cryptographic Applications Quadratic residues are central in modern cryptography. ### Quadratic Residuosity Problem Given a composite integer $$ n=pq, $$ determine whether $a$ is a square modulo $n$. This problem is believed to be computationally difficult when the factorization of $n$ is unknown. Its hardness underlies several cryptographic constructions. ### Rabin Cryptosystem The Rabin cryptosystem encrypts messages using squaring modulo a composite integer: $$ c\equiv m^2\pmod n. $$ Decrypting requires computing square roots modulo $n$, which depends on factoring $n$. Thus the security relates directly to quadratic residue computation. ### Blum-Blum-Shub Generator The Blum-Blum-Shub pseudorandom generator repeatedly squares modulo a composite integer: $$ x_{n+1}=x_n^2\pmod M. $$ The unpredictability of the sequence relies on the difficulty of extracting modular square roots. ## Finite Fields and Algorithms Quadratic residues are naturally interpreted inside finite fields. The multiplicative group $$ \mathbb{F}_p^\times $$ is cyclic of order $$ p-1. $$ Quadratic residues form a subgroup of index $2$. This algebraic structure allows efficient algorithms based on: - discrete logarithms, - character theory, - polynomial factorization, - finite field arithmetic. Finite field computations are now standard in coding theory and cryptography. ## Modern Computational Number Theory Computational quadratic residue theory connects classical arithmetic with modern algorithms. The subject combines: - congruence theory, - algebraic structures, - complexity theory, - probabilistic algorithms, - cryptographic hardness assumptions. Questions originally studied by entity["people","Leonhard Euler","Swiss mathematician"], entity["people","Adrien-Marie Legendre","French mathematician"], and entity["people","Carl Friedrich Gauss","German mathematician"] now appear directly in secure communication systems and large-scale computational mathematics.