mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-07-28, 12:57   #34
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101111000112 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
jasonp is offline   Reply With Quote
Old 2008-07-29, 04:26   #35
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by jasonp View Post
... 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
bdodson is offline   Reply With Quote
Old 2008-08-16, 01:48   #36
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×29×31 Posts
Default 21 factored with "Quantum Adiabatic Algorithm"

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

What next? Factor 33?
paulunderwood is offline   Reply With Quote
Old 2008-08-16, 09:01   #37
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2×73×17 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
xilman is online now   Reply With Quote
Old 2008-08-16, 14:19   #38
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Alternatively-gifted factoring algorithm Prime95 Miscellaneous Math 72 2015-10-26 00:14
Shor's Algorithm flouran Math 3 2009-10-27 09:31
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
Faster Factoring Algorithm? Citrix Factoring 6 2007-12-23 11:36
A new prime factoring algorithm? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”