SQRTMOD

This function finds solutions to the modular equation x^2 \equiv a \pmod p.

The congruence is:

x^2 \equiv a \pmod p

Depending on the modulus and value, there may be no solution, one solution, or multiple solutions. Results are returned as a single-column 2D array for Excel spill compatibility.

Excel Usage

=SQRTMOD(a, p, all_roots)

a (int, required): Right-hand-side residue value.
p (int, required): Positive modulus.
all_roots (bool, optional, default: true): If true, request all roots from the solver.

Returns (list[list]): Single-column 2D array of modular square roots, or a single blank cell if no roots exist.

Example 1: Single modular square root example

Inputs:

a	p	all_roots
11	43	false

Excel formula:

=SQRTMOD(11, 43, FALSE)

Expected output:

21

Example 2: All square roots for composite modulus

Inputs:

a	p	all_roots
17	32	true

Excel formula:

=SQRTMOD(17, 32, TRUE)

Expected output:

Result
7
9
23
25

Example 3: No modular square root returns blank cell

Inputs:

a	p	all_roots
3	7	true

Excel formula:

=SQRTMOD(3, 7, TRUE)

Expected output:

""

Example 4: All roots modulo an odd prime

Inputs:

a	p	all_roots
10	13	true

Excel formula:

=SQRTMOD(10, 13, TRUE)

Expected output:

Result
6
7

Python Code

from sympy import sqrt_mod as sympy_sqrt_mod

def sqrtmod(a, p, all_roots=True):
    """
    Solve quadratic congruences of the form x squared congruent to a.

    See: https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.residue_ntheory.sqrt_mod

    This example function is provided as-is without any representation of accuracy.

    Args:
        a (int): Right-hand-side residue value.
        p (int): Positive modulus.
        all_roots (bool, optional): If true, request all roots from the solver. Default is True.

    Returns:
        list[list]: Single-column 2D array of modular square roots, or a single blank cell if no roots exist.
    """
    try:
      roots = sympy_sqrt_mod(a, p, all_roots=all_roots)
      if roots is None:
        return [[""]]
      if isinstance(roots, int):
        return [[int(roots)]]
      if len(roots) == 0:
        return [[""]]
      return [[int(r)] for r in roots]
    except Exception as e:
      return f"Error: {str(e)}"

Online Calculator

a *

Right-hand-side residue value.

p *

Positive modulus.

all_roots

If true, request all roots from the solver.