Solving modular quadratic equations for beginners

Question

I'm trying to implement something in my program that requires solving modular equations with large numbers. I've seen two types of solution: those that require using trial and error to make the solution to the quadratic "fit" the modulus (which I cannot do because it will be too inefficient for large numbers), and those that use math symbols that I don't understand and don't know the name of so I can't look into them.

If you use any math symbol that's not on a standard scientific calculator, please include the name of it so I can look into it. And yes, I am aware of how ridiculous modular quadratic equations for beginners sounds.

My basic equation will be in the following form, and I know it will have at least two solutions:

$a^2-n\equiv0 \mod m$

a is the unknown, n is a positive integer, and m is an odd prime.

For example,

$a^2-10\equiv0 \mod 13$

has the solutions 6 and 7.

Basically, I'm looking for a way to solve the initial equation that will be efficient and complete in a reasonable time, even if n and m have hundreds of digits. Thanks in advance.

"I know it will have at least two solutions": that's not right. If $m$ is an odd prime, then your equation has either zero or two solutions, according as $n$ is a quadratic residue $\bmod m$. As for finding a solution, you can do that reasonably efficiently, but it is complicated. — TonyK, Jun 16 '21 at 13:44
@TonyK Thanks. I'm looking at the Tonelli Shanks algorithm, and something that I see often is (a | p) $\equiv$ 1 mod p. What does that mean? — Infinite Recursion, Jun 16 '21 at 15:35
(a | p) is the Legendre symbol, discussed here: https://en.wikipedia.org/wiki/Legendre_symbol — Michael Cohen, Jun 16 '21 at 15:51

Solving modular quadratic equations for beginners

0 Answers0