[Foxtrot] modular square roots

[Alan Lawrence]

Firstly, the Discrete Maths notes explain how to do square roots modulo a
prime of the form 4k+3 (pg. 18, "coin-tossing by telephone"). So you can
combine that with your existing method to compute square roots modulo any
prime.

I don't really have an answer as to how to do it modulo a^2 :-(....the
Chinese remainder theorem isn't really useful. You can compute the jacobi
symbol of a number (using foxtrot.primetest.PrimeTest.jacobiSymbol(n,a^2))
and see if the number you've got _is_ a quadratic residue; and then try
suitable values until you've got an answer??? Actually, no, think I may
have an answer....I just thought this through myself, so it's probably
wrong, but:

For x to be square root of b modulo a^2, we have

x^2 = b mod a^2
x^2 = b + n.a^2 for some n
x^2 = b + (n.a)a
x^2 = b mod a

i.e. the square root mod a^2 is also a square root mod a.

So get the square root mod a first; then for each i=0....a-1, try adding
i*a to the square root and testing to see if it's a square root mod a^2
? If your a's are smallish this shouldn't be hard. If they're larger....!!

e.g. take a=31, b=5

x=25 (25^2 = 625 = 5 mod 31)

x+(12*31) = 397

397 ^ 2 = 5 mod (31^2=961)

take b=7

x=10 (10^2 = 7 mod 31)

x+(20*31) = 630

630^2 = 7 mod (31^2=961)

but I can see no clear way (yet) to find out how many a's one has to add
on to get from the square root mod a to the square root mod a^2 :-(

HTH and good luck,

Alan


On Wed, 14 Feb 2001, Michael Pinna wrote:

> Guys,
> 
> have any of you, by any chance, found out to compute the modular square
> roots needed to choose the polynomial used in mpqs on line 5 of page 359
> of Montgomery? I can do the first one (where the modulus is prime),
> though actually I've imposed the condition that a = 1 mod 4 to make the
> sums easier :) The second one needs a square root computing mod a
> squared, and that's harder...
> 
> Any handy suggestions?
> 
> Mike
> 
> -- 
> "...like the floating elephant imitating a pen."
>       --Anon
> 
> 
> 
> 
> _______________________________________________
> Foxtrot mailing list
> Foxtrot@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/foxtrot
>