Modular square root

[Guillaume Hanrot]

> You can use Cantor-Zassenhaus' algorithm:

Or, alternatively, Tonelli-Shanks algorithm, which might be simpler to
implement and possibly faster. This is the generalization of what you
might have done for p = 3 mod 4 or 5 mod 8: split the problem between
the odd order part of (Z/pZ)^* (for which this is easy) and the 
2-part of (Z/pZ)^* (the tricky part). 

For pseudocode, see eg. 

http://en.wikipedia.org/wiki/Shanks-Tonelli_algorithm

Guillaume
-- 
Guillaume Hanrot                         Tel : (+33) (0)3 83 32 14 62
136 bis, rue Saint-Dizier
F-54000 NANCY                            Mel : ghanrot at free.fr