Modular square root

Guillaume Hanrot hanrot at
Thu May 17 09:32:05 CEST 2007

> 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.

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

More information about the gmp-discuss mailing list