20080728, 12:57  #34  
Tribal Bullet
Oct 2004
110111100011_{2} Posts 
Quote:
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 20080728 at 13:37 

20080729, 04:26  #35  
Jun 2005
lehigh.edu
2^{10} Posts 
Quote:
ecpp has expected degree 4 runtime (the same as the AKS variants), but is the current methodofchoice in practice. There have been a few c. 10,000digit (random) numbers proved prime; and Frankeetal have the top two, c. 15,000digits and c. 20,000digits. The report above is the first I've seen of AKS hitting even 300digits. 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,000digit 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 

20080816, 01:48  #36 
Sep 2002
Database er0rr
5×29×31 Posts 
21 factored with "Quantum Adiabatic Algorithm"

20080816, 09:01  #37  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2×7^{3}×17 Posts 
Quote:
Paul 

20080816, 14:19  #38  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Quote:
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 20080816 at 14:20 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Alternativelygifted factoring algorithm  Prime95  Miscellaneous Math  72  20151026 00:14 
Shor's Algorithm  flouran  Math  3  20091027 09:31 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 