Shor's Factoring Algorithm - does it even work?

[jasonp]

Originally Posted by bsquared

Well, I'm pretty sure jasonp has done his homework w.r.t AKS: http://images.apple.com/acg/pdf/aks3.pdf

I didn't answer because I'm not familiar with the theory (and don't feel like changing that right now). AKS basically involves a single big exponentiation of a finite field polynomial, repeated however many times it takes to remove the possibility of the input having factors. The big research question is how often that one primitive should be repeated. A, K and S prove that the number of primitives is cubic in the number of bits in the input, and Bernstein shows that for 'most' numbers it's quadratic. That seems to be the limit of current research that I'm aware of. AKS is a very cool algorithm that's computationally essentially useless; the coolness comes from the simplicity of the tools it needs to work.

PS: Raman, the main identity is not over integers mod p, but polynomials mod the polynomial x^r, with coefficients mod p; the algorithm is computationally expensive because those polynomials have huge degree

[bdodson]

Originally Posted by jasonp

... limit of current research that I'm aware of. AKS is a very cool algorithm that's computationally essentially useless; the coolness comes from the simplicity of the tools it needs to work.

Just to fill-in more of the relevant background, on the computational side,
ecpp has expected degree 4 runtime (the same as the AKS variants), but
is the current method-of-choice in practice. There have been a few
c. 10,000-digit (random) numbers proved prime; and Franke-et-al have the
top two, c. 15,000-digits and c. 20,000-digits.

The report above is the first I've seen of AKS hitting even 300-digits. Is
there a more current update on an AKS record? Aside from collecting
evidence of how far away it is from being able to hit the 10,000-digit range.

On the coolness part; provable, deterministic polyn time was the AKS
theorem. And (unlike Fermat) using tools that everyone else had been
looking at, just put together better. There was a public effort to see
whether we might have overlooked something similar for factoring, or
other problems considered hard; but if anyone found something, especially
something that would work in practice, they're not telling. -Bruce

[paulunderwood]

I found this recent paper :http://arxiv.org/abs/0808.1935

What next? Factor 33?

[xilman]

Originally Posted by paulunderwood

I found this recent paper :http://arxiv.org/abs/0808.1935

What next? Factor 33?

Maybe. An plausible alternative is 65, that being the next two-factor integer greater than the next larger power of two.


Paul

[Raman]

Originally Posted by paulunderwood

I found this recent paper :http://arxiv.org/abs/0808.1935

What next? Factor 33?

Huh! Think of going exponentially!

A small Mersenne or Repunit
followed up by the Series of Fermat Numbers!
fifth, sixth, seventh, eighth Fermat Numbers,

followed by GNFS 100, 120, 140...

I think that it would already be hopefully long before reaching even RSA 129
It would be in fact a long term goal!

Quantum computing means that the bits overlapping one over the other?