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 <and...@persephoneslair.org> 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
pgpv_iM3WRwuC.pgp
Description: PGP signature
_______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
