# Quadratic Residue Checker (Legendre / Jacobi Symbol) Jacobi/Legendre symbol with deterministic Miller–Rabin primality, Tonelli–Shanks square roots for prime moduli, and brute-force resolution for small composite moduli. > Canonical page: https://elysiatools.com/en/tools/quadratic-residue-checker - **Category:** Math & Numbers - **Keywords:** quadratic residue, legendre symbol, jacobi symbol, tonelli-shanks, square root modulo, euler criterion, miller-rabin, number theory ## Overview 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. ## Inputs - **Value a** (text): The value being tested for squareness; reduced mod n first (up to 10⁵¹²). - **Modulus n (odd)** (text): Odd modulus, 3 ≤ n ≤ 10¹⁸ (primality tested with deterministic Miller–Rabin). - **When n is prime, solve x² ≡ a (mod n)** (checkbox): Run Tonelli–Shanks and print the square roots when they exist. ## When to use - Determining if a modular congruence x² ≡ a (mod n) has integer solutions. - Computing modular square roots for prime moduli in cryptography or number theory tasks. - Evaluating Legendre and Jacobi symbols to analyze residues and non-residues. ## How it works - Enter the target value a (reduced modulo n) and an odd modulus n between 3 and 10¹⁸. - The tool performs deterministic Miller–Rabin primality testing on n and evaluates the Jacobi or Legendre symbol (a/n). - For prime moduli with a symbol of +1, Tonelli–Shanks computes the square roots when requested, while small composite moduli (n ≤ 100,000) are resolved via exhaustive search. ## Use cases - Solving quadratic congruences in cryptography implementations like Rabin cryptosystems or elliptic curve point decompression. - Verifying theoretical homework problems in abstract algebra and elementary number theory courses. - Analyzing pseudo-squares and composite modulus behavior in computational mathematics research. ## Frequently asked questions ### What is the difference between the Legendre and Jacobi symbols? 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. ### Does a Jacobi symbol of +1 guarantee that a is a quadratic residue? 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. ### What algorithms are used to solve the modular square roots? When n is prime, the tool employs the Tonelli–Shanks algorithm (or direct exponentiation when n ≡ 3 mod 4) to output the square roots. ### What limits apply to inputs a and n? 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. ### How is primality of modulus n verified? The tool uses deterministic Miller–Rabin testing to verify primality without probabilistic error for 64-bit moduli. ## Related tools - [Blood Gas Acid-Base Interpretation (AG / ΔAG)](https://elysiatools.com/en/tools/blood-gas-anion-gap): Complete ABG analysis: pH, primary disorder, compensation (Winter's formula), anion gap ± albumin correction, delta ratio for mixed disorder detection. Derived from Emmett 2016, Kraut 2007, Rastegar 2007, LITFL, MDCalc, and Adrogué 1998. Not medical advice. - [Primitive Root Finder](https://elysiatools.com/en/tools/primitive-root-finder): Smallest primitive root mod n with certificate g^(φ/q) ≠ 1, root count φ(φ(n)), up to 50 listed roots, and candidate verification. n ≤ 10¹². - [CURB-65 vs PSI vs SMART-COP (Pneumonia Severity Comparison)](https://elysiatools.com/en/tools/curb-65-vs-pneumonia-severity): Compare three pneumonia severity scores side-by-side from one set of inputs to support concordance reading. CURB-65 (0-5: Confusion, Urea, RR, BP, age ≥65) — quick bedside triage; PSI/PORT (Fine 1997, 5 risk classes) — the most accurate mortality stratification, more complex; SMART-COP (0-10, 2 points each for SBP <90 and hypoxia, 1 point each for multilobar CXR, albumin <3.5, RR ≥25, tachycardia ≥125, confusion, pH <7.35) — predicts need for ICU respiratory/vasopressor support. Each score has a different focus: CURB-65 is fast; PSI is more precise; SMART-COP identifies who needs ICU. The tool reports each score's total/category/interpretation and an agreement analysis (whether all three point to outpatient/admission/ICU). When scores disagree, favor the more conservative disposition. Derived from Lim 2003, Fine 1997, Charles 2008. Not medical advice. - [DNA Concentration Calculator (A260 Absorbance)](https://elysiatools.com/en/tools/dna-concentration-a260): Beer–Lambert DNA quantitation: c = A260 × dilution factor × K / path length with 1 OD = 50 µg/mL dsDNA or 33 µg/mL ssDNA, plus ng/µL, total yield, and a 0.1–1.5 linear-range check. Derived from Marmur & Doty, Sambrook & Russell, Thermo Fisher NanoDrop notes. Educational use only. - [File Type Detector (Magic Number)](https://elysiatools.com/en/tools/file-type-detect): Identify a file by its magic-number byte signature, not the extension. Reads the uploaded file directly across ~70 types. - [OD260/230 Nucleic Acid Purity Ratio Calculator](https://elysiatools.com/en/tools/od260-230-ratio): Check salt/organic-solvent contamination with A260/A230 (pure 2.0–2.2; below 2.0 = guanidinium/phenol/EDTA/salt carryover from TRIzol or columns), with an optional A260/280 cross-check. Derived from Thermo Fisher T042, Sambrook & Russell, Manchester 1995. Educational use only. - [OD260/280 Nucleic Acid Purity Ratio Calculator](https://elysiatools.com/en/tools/od260-280-ratio): Judge DNA/RNA purity from A260/A280 (pure DNA ~1.8, pure RNA ~2.0; low = protein/phenol contamination, DNA > 2.0 = RNA contamination) plus the optional A260/A230 secondary check. Derived from Manchester 1995, Sambrook & Russell, Thermo Fisher T042. Educational use only. - [Perfect Number Checker](https://elysiatools.com/en/tools/perfect-number-checker): σ(n) = 2n ⟺ perfect. Factorization-based σ(n), proper-divisor sum, deficient/perfect/abundant classification, abundancy index, Euclid–Euler form. n ≤ 10¹². ## Samples - [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion - [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion - [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion - [Web Image Processing Rust Samples](https://elysiatools.com/en/samples/web-image-processing-rust): Web Rust image processing examples including image read/save, scaling, and format conversion