Hey There,

Following up from yesterday’s post, I wanted to jump into pk, sk encryption. Why agreeing to the same shared secret and standard encryption breaks down.

The tldr is quantum computers make factoring large numbers easy. For classical computers this is hard and the basis of lots of encryption.

This isn’t a very satisfying answer so I wanted to dig up more.

I learned what this was in school but it flew over my head. Luckily MinutePhysics has a great video explaining it at a high level.

tldr:

• We guess are random number g and do quantum stuff to generate a better guess p. p has a much higher chance (~37.5%) to be a number that can help us factor N.

• How do we find the better guess? We find it’s period

  • g^period mod N = 1

    • If g and N are coprime (largest common factor is 1)

    • Euler-Fermat Theorem

  • g^p = m*N+1

    • → (g^(p/2)+1)(g^(p/2)-1)=m*N

  • 3/8s of the time (g^(p/2)+1) or (g^(p/2)-1) is N AND p is even

• Shor’s algorithm helps us find the period

  • How? (I’m not quite sure, it’s confusing)

  • so g^(x+ip) mod N = r for all integers i

    • g^(x+ip) mod N → g^x * g^ip mod N

    • (wN+r) (mN+1) = wmNN+wN+rmN+r= number*N + r = r mod N

  • This is where quantum computers get weird

    • We make a quantum circuit that takes a guess g and returns the remainder r of g (g^r mod N)

      • | 1, g^1 mod N>, |2 , g^2 mod N> …

      • we measure the remainder output and get r

      • By superposition and quantum magic this means everything we measure from here on out will have a remainder of r

        • | x, g^x mod N = r>, |y, g^y mod N =r> ...

      • We know that x, y, … differ by some factor of p

        • g^x * g^ip = g^y

      • We use a quantum fourier transformation to find p

        • fourier transformations find underlying wave relations

        • there’s good quantum versions of fourier and inverse fourier that are used in everything because everything can be broken down into a wave

    • If p is even, we check if g^(p/2)+/-1 is N. If not repeat.

I spent much longer trying to understand Shor’s than I thought I would. I wanted to spend more time trying to understand why the factoring of large numbers breaks key generation / pk sk (more than it factors large numbers and RSA).

I’ll do that another day. I’ll probably have to understand what an elliptical curve is.

Bye,

Lucas

update:

wanted to include shor’s algorithm has a ~O(log^3 n) quantum cost

https://quantumcomputing.stackexchange.com/questions/16421/classical-algorithm-with-complexity-similar-to-shors-discovered-are-there-more