two number theory questions

[Pete Chown]

Anton Stiglic wrote:

> If you can tell whether of not g^x mod p (for unknown x) is a
> quadratic residue or not, then there is a way to efficiently do what
> you ask (think about binary extended Euclidean algorithm).

Can't you just calculate the Jacobi symbol to find out whether g^x is a 
quadratic residue modulo p?  An algorithm for that is described in the 
Handbook of Applied Cryptography.

I can't immediately see how the extended Euclidean algorithm would work 
in this context; can you elaborate?

-- 
Pete


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