Comment Re:Related paper: Oversimplifying quantum factorin (Score 1) 62
Very interesting to see this idea has some history to it. I'm not surprised that other people thought of it too!
Like you, I had noticed that the number of qubits used (7) was smaller than the number needed to implement Shor's algorithm. I actually asked Shor about this and he said, "15 is special, because it is 4 to an integer power minus 1." I asked him what that meant and it said "it means it's divisible by 3."! This told me that there are special classes of numbers that are easy to "factor" (by which I mean "to run Shor's algorithm on") if only you know you are in the class.
What really stimulated us to write the paper was the observation that 21 had been factored on only a qutrit. The numbers being factored were growing, but the size of the quantum computer was shrinking. Surely something fishy was going on.