Modular square root
hanrot at gmail.com
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 free.fr
More information about the gmp-discuss