On Sat, Sep 07, 2013 at 08:45:34PM -0400, Perry E. Metzger wrote:
> I'm unaware of an ECC equivalent of the Shor algorithm. Could you
> enlighten me on that?

Shor's algorithm is a Fourier transform, essentially.  It can find periods of
a function you can implement as a quantum circuit with only polynomially many
invocations.  In particular, when that function is exponentiation in a group,
it can find the orders of group elements.  This allows finding discrete
logarithms in BQP for any group in which exponentiation is in P.

Andrea Shepard
PGP fingerprint (ECC): 2D7F 0064 F6B6 7321 0844  A96D E928 4A60 4B20 2EF3
PGP fingerprint (RSA): 7895 9F53 C6D1 2AFD 6344  AF6D 35F3 6FFA CBEC CA80

Attachment: pgpv_iM3WRwuC.pgp
Description: PGP signature

The cryptography mailing list

Reply via email to