^{2}= 1 mod n means (s+1)(s-1) = 0 mod n and you're a gcd away from factoring n. Ok, so maybe think of a number k less than n and do a bunch of iterated powers of k hoping to find an even number 2p such that k

^{2p}= 1 mod n, meaning that k

^{p}is the nontrivial square root of 1 that you wanted. And hey! We have a lemma that tells us that picking k at random actually gives us a substantial (≥ 1/2) chance of succeeding! Amazing.

**But**doing all those iterated powers of k is still expensive, i.e. exponential in the number of bits of the the number we're factoring. But

**quantum**computers (and only now does anything quantum come into play) we can do a fourier transform of the sequence of iterated powers without actually having to compute the whole sequence, uh, sequentially. And we can stochastically read off information about its period by sampling the wavefunction in frequency space. And, voila, we have factored a number in polynomial time.