Summer 2015 Projects

Quantum Computer Programming and Simulation

Playing with QCL 0.6.4 (Mar 27 2014) by Bernhard Ömer, and implementation of the Shor factorization algorithm.

A non-quantum analysis of Shor's Figure 5.1 probability plot, factoring n=33 with x=5: x^a mod n, DFT output and plot using q=2048 (Shor used q=256). DFT peaks occur at (205, 410, 614, 819, 1024), and dividing those into 2048 produces period estimates (9.9902, 4.9951, 3.3355, 2.5006, 2.0000). Using r=10 ~= 9.9902 we have x^r - 1 = 0 (mod n), so (x^r/2 - 1)*(x^r/2 + 1) = (5⁵ - 1)*(5⁵ + 1) = 22*24; gcd(22,33) = 11, gcd(24,33) = 3, both factors of n. Code: shor.c, dft.c.

Also see Quantum Computing in Summer 2013 Projects

NIST Workshop on Elliptic Curve Cryptography Standards

Attended the workshop. Notable presentations: Simplicity, by Dan Bernstein; Vehicle to Vehicle Safety Applications, by Rob Lambert - see secg.org regarding implicit certificates.