Talk:Tonelli–Shanks algorithm

the case where p = 3 mod 4

It is written that in the special case where p equals 3 modulo 4, then the solution is simply:

$n^{(p+1)/4}$

I don't get why. Is it supposed to be obvious? --Grondilu (talk) 14:01, 20 June 2012 (UTC)

Yes. Square it, and apply Euler's criterion.—Emil J. 14:41, 20 June 2012 (UTC)

alberto tonelli needs enwiki biop (from itwiki)

Alberto Tonelli needs a enwiki translation. He has an article on the itwiki, a small one that doesn't mention he first came up with the important Tonelli-Shanks modular square root algorithm. There are three algorithms to take a modular square root and Tonelli's is as good as any of them. It's actually a rather important algorithm, since public key cryptography uses modular arithmetic. Endo999 (talk) 02:13, 28 August 2017 (UTC)

dickson's work on tonelli says the algorithm will work on mod p^k

I'm not a professional mathematician but I just read Dickson's "History of Numbers" where it says on page 215 that

A. Tonelli gave an explicit formula for the roots of $x^{2}=c({\bmod {p^{\lambda }}})$

Perhaps some mathematician should work out if the Tonelli algorithm takes modular square roots for powers of primes as well as for primes This Wiki article says the algorithm only works for prime modula.

After reading the Dickson text a couple of times on p215,216 I came across this formula for the square root of Failed to parse (syntax error): {\displaystyle x^{2]\bmod{p^{y}}} .

when $p=4*7+1$, or $s=2$ and $a=7$

for $x^{2}{\bmod {p^{\lambda }}}\equiv c$ then

$x{\bmod {p^{\lambda }}}\equiv \pm (c^{a}+3)^{\alpha }*c^{(\alpha +1)/2}$ where $\alpha \equiv a*p^{\lambda -1}$

Noting that $23^{2}{\bmod {29^{3}}}\equiv 529$ and noting that $\alpha =7*29^{2}$ then

(529^{7} + 3)^{7 29^{2}}* 529^{(7*29^{2} + 1)/2}\bmod{ 29^{3}}\equiv 24366 \equiv -23</math>

So Tonelli's math does seem to take modular square roots of prime powers! Endo999 (talk) 03:17, 2 September 2017 (UTC)

Endo999 (talk) 06:36, 30 August 2017 (UTC)