Elysia Tools
Navigation
Math & Numbers
Jacobi/Legendre symbol with deterministic Miller–Rabin primality, Tonelli–Shanks square roots for prime moduli, and brute-force resolution for small composite moduli.
Execution
Fill in the form, run the tool, and review the result in one place.
Samples
Related
Tool usage guide
The Quadratic Residue Checker evaluates whether an integer is a quadratic residue modulo an odd integer using the Legendre or Jacobi symbol, deterministic Miller–Rabin primality testing, and the Tonelli–Shanks algorithm to extract modular square roots.
Background
Studying modular square roots for elliptic curve point recovery over prime fields.
Problem
Check if 10 is a square modulo 13 and find the roots satisfying x² ≡ 10 (mod 13).
How to use
Set Value a to 10, Modulus n to 13, and check the option to solve roots.
Outcome
Confirms (10/13) = 1 and outputs the verified roots x = 6 and x = 7.
Background
Testing properties of composite integers where quadratic character evaluation can yield false positives.
Problem
Determine if 2 is a quadratic residue modulo 15 despite Jacobi(2/15) returning +1.
How to use
Input 2 for Value a, 15 for Modulus n, and run the calculation.
Outcome
Calculates Jacobi(2/15) = 1 and uses brute-force inspection to prove x² ≡ 2 (mod 15) has no solution.
The Legendre symbol applies strictly to odd prime moduli, while the Jacobi symbol extends this notation to odd composite moduli as a product of Legendre symbols.
No. For composite moduli, a Jacobi symbol of +1 is inconclusive; for values of n ≤ 100,000, the tool runs a brute-force scan to confirm actual solvability.
When n is prime, the tool employs the Tonelli–Shanks algorithm (or direct exponentiation when n ≡ 3 mod 4) to output the square roots.
The modulus n must be an odd integer up to 10¹⁸, and the integer a is accepted up to 10⁵¹² before being reduced modulo n.
The tool uses deterministic Miller–Rabin testing to verify primality without probabilistic error for 64-bit moduli.