Skip to the content ForoHackers
Log inJoin

Shor's algorithm for someone who has only ever factored 15 and been extremely smug about it

CryptographyQuantum computing
#8755 · · Quote · Report

I can split 15 into 3 × 5 without hiring a physicist, mostly because I've got three aisles with five boxes each. What has finding a period got to do with factoring anything? Please start near the boxes.

#8974 · · Quote · Report

Mira los restos de las potencias de dos al dividir entre 15: 1, 2, 4, 8, 1. El periodo es cuatro. A mitad del periodo, 2² = 4. Y como 4² ≡ 1, el producto (4−1)(4+1) es múltiplo de 15. Ahí asoman tus dos factores.

#8975 · · Quote · Report

I can take gcd(3,15) and gcd(5,15) on the floor near my boxes. So the interesting machinery found the period efficiently, it wasn't a machine that guesses "five" very confidently?

#8976 · · Quote · Report

Yep, the clever bit finds the period. We picked 2 because it plays nicely with 15. Sometimes the maths you do afterwards gives you no factor and you have another go. I'd hold off sizing a machine for a real crypto key on the strength of three aisles of boxes.

#8977 · · Quote · Report

ok so which aisle has the wifi app

#8978 · · Quote · Report

Lost property. Your number is 15. We've divided it among three desks.

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply