[13136] in cryptography@c2.net mail archive
Re: two number theory questions
daemon@ATHENA.MIT.EDU (Pete Chown)
Mon Apr 28 15:48:38 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Mon, 28 Apr 2003 19:27:57 +0100
From: Pete Chown <Pete.Chown@skygate.co.uk>
To: cryptography@metzdowd.com
In-Reply-To: <001701c30dab$2b3295d0$0bab6395@p1038mobile>
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@metzdowd.com
