mersenneforum.org Shor's Factoring Algorithm - does it even work?
 Register FAQ Search Today's Posts Mark Forums Read

2008-07-28, 12:57   #34
jasonp
Tribal Bullet

Oct 2004

1101111000112 Posts

Quote:
 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

Last fiddled with by jasonp on 2008-07-28 at 13:37

2008-07-29, 04:26   #35
bdodson

Jun 2005
lehigh.edu

210 Posts

Quote:
 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

 2008-08-16, 01:48 #36 paulunderwood     Sep 2002 Database er0rr 5×29×31 Posts 21 factored with "Quantum Adiabatic Algorithm" I found this recent paper :http://arxiv.org/abs/0808.1935 What next? Factor 33?
2008-08-16, 09:01   #37
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2×73×17 Posts

Quote:
 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

2008-08-16, 14:19   #38
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts

Quote:
 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?

Last fiddled with by Raman on 2008-08-16 at 14:20

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime95 Miscellaneous Math 72 2015-10-26 00:14 flouran Math 3 2009-10-27 09:31 Visu Math 66 2008-05-12 13:55 Citrix Factoring 6 2007-12-23 11:36 Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 09:52.

Mon Feb 6 09:52:16 UTC 2023 up 172 days, 7:20, 1 user, load averages: 0.87, 0.93, 0.89