square roots modulo a prime p

[Alexander Klimov]

Hi.

I have checked several papers and software packages which implement
modular square root and it looks like there is no agreement about what
algorithm is the best except that everybody does the same for p=3(4).

Chapter 3 of HAC suggests special algorithms for p=3(4) and p=5(8); a
general algorithm (IIUC, Shanks-Tonelli algorithm) which has
complexity O(|p|^3 s), where s is such that t is odd in t 2^s = p-1;
and an algorithm based on polynomial modular exponentiation:

 r = x^{(p+1)/2} mod (x^2 - bx + a)

where b^2-a is a quadratic non-residue modulo p for cases where s is
large.

Some standards, e.g., IEEE 1363-2000, X9-1.62, etc. use same approach
for 3(4) and 5(8) but propose an algorithm based on Lucas sequence in
general case.

Looks like GMP does not implement any algorithm.

Openssl uses Tonelli/Shanks algorithm (crypto/bn/bn_sqrt.c) checking
simple cases first.

Crypto++ (nbtheory.cpp) seems to do the same as openssl but does not
check 5(8).

NTL uses the smartest approach: it implements 3(4) and when for
s < sqrt(|p|) it uses Tonelli/Shanks algorithm and for large s it uses
polynomial reduction.

So I wonder why no well-known programs implement what respectable
standards suggest? And the other way around: why standards suggest
what is not usually implemented?

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com