Find integer $x$ such that $x^2 \mod {n}$ is divisible by $p$
For values $n = 1799832043, p = 67610791$
I have been using Tonelli-Shanks algorithm to solve this and it works for small primes with Legendre symbol $1$ like the number below
- $p=2,x=42425$
- $p=3,x=42425$
- $p=7,x=42430$
- $p=11,x=42430$
- $p=13, x=42429$
But for some reason, it's not working for $67610791$, why is that?
You are looking for an $x$ so that $x^2 \equiv n \mod p$. This implies that $(\frac{n}{p})=+1$.
As $n=28843 \cdot 62401$, this then implies that $(\frac{28843}{p})$ and $(\frac{62401}{p})$ both are $+1$, or both are $-1$. But $(\frac{28843}{p}) =-1$ and $(\frac{62401}{p})=+1$.
This can be easily derived by applying the quadratic reciprocity law a number of times on both Legendre symbols, but can also be derived from the fact that when $p \equiv 3 \mod 4$ (like $p=67610791$), then $$[a^{\frac{p+1}{4}}]^2 = a^{\frac{p+1}{2}} = a \cdot a^{\frac{p-1}{2}} \equiv a \cdot (\frac{a}{p})$$ and calculate $28843^{\frac{p+1}{4}}$ and $62401^{\frac{p+1}{4}}$.
A relatively simple calculation shows that
$28843^{\frac{p+1}{4}} \equiv 275671$, and $275671^2 \equiv 67581948 \equiv -28843$
and
$62401^{\frac{p+1}{4}} \equiv 49327081$, and $49327081^2 \equiv 62401$
Hence $(\frac{n}{p})=(\frac{28843}{p}) \cdot (\frac{62401}{p})=-1$
If you like, you can also directly calculate $n^{\frac{p+1}{4}}$ of course:
$n^{\frac{p+1}{4}} \equiv 28238849$, and $28238849^2 \equiv -41951477 \equiv -n$