mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-04-15, 19:42   #23
Jushi
 
Jushi's Avatar
 
Sep 2005
UGent

22·3·5 Posts
Default

Quote:
Originally Posted by bearnol
Well you would say that, wouldn't you, Alex - since you're the competition (GMP-ECM)! :-)
Well, ecm finds the 12-digit factor of 2^607+1 in a matter of seconds, while you say your algorithm takes about an hour. I know which algorithm I prefer...
Jushi is offline   Reply With Quote
Old 2006-04-15, 20:29   #24
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default

Yes, I'm serious - I estimate (assuming all goes well - which is the point of the test) about 1 year to find the 20-digit factor of (M+2)607. Interested?
About 8000 cpu years to find 40-digit factor of similar numbers, about 64000000 cpu years to find 80-digit factors, etc... [so I know which algorithm _I_ would prefer for big factors]
This is using my (already-written) Java code - if I were to rewrite it in C might be faster??
J
bearnol is offline   Reply With Quote
Old 2006-04-15, 20:38   #25
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Run it yourself. I don't mind if you waste your own cpu time, but don't waste others' by luring them into pointless endeavours with baseless claims.

Alex
akruppa is offline   Reply With Quote
Old 2006-04-15, 22:21   #26
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

It's not a baseless claim (I've already had promising results).
Lay off of my potential helpers! :-)
J
bearnol is offline   Reply With Quote
Old 2006-04-15, 23:50   #27
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2216 Posts
Default

Quote:
Originally Posted by akruppa
I can't write up a formal analysis until some time in may due to higher priority tasks (yes, including GMP-ECM), and quite possibly will have other things to do even then. I have analysed the idea of trying different bases for P-1 for my thesis, though, and found it utterly useless. IIRC, less than log(B1)/B1 of the possible bases lead to a end-of-stage-1 residue of smaller order than the worst case can have. Btw, providing an analysis of the algorithm would be up to you anyway, especially in the light of your grand claim of polynomial time complexity.

Alex
Bearnol's claim to the contrary, I understand his proposal quite well.
It is strictly an exponential time algorithm and is actually worse than
trial division. It is pointless.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-16, 02:24   #28
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Trial division requires testing values of the 'base' up to the size of the factor. The results I'm already getting show that only a small percentage of the size of the factor is needed from the 'base' to find the factor. What's more this beneficial effect increases with size of factor.
Thinking theoretically, it is clear to me at least, that in the limit, the size of base needed for any size factor will tend to a constant (sic). How can this be worse than trial division!!!. Couple this fact with the polynomial/logarithmic time needed for each step (as I've already said, using Russian Peasant) and you get a polynomial/logarithmic algorithm.
If you don't believe me - try it!! There's working programs there...
bearnol is offline   Reply With Quote
Old 2006-04-16, 19:18   #29
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

24×7×101 Posts
Default

Quote:
Originally Posted by bearnol
Well you would say that, wouldn't you, Alex - since you're the competition (GMP-ECM)! :-)
I disagree - "competition" comes from the from the Latin competere, meaning to seek or strive together, and thus implies that the parties involved each have some nonvanishing chance of succeeding, which is most definitively not the case here. Not coincidentally, the word "competent" has the same root.
Quote:
I was unaware that this algorithm was 'well-known' by anyone other than me...
Trust me, we'd have been more than happy to let you keep this one all to yourself, except that you insisted on fluttering to the top of your barnyard Misthaufen and crowing loudly about it to all the world.
Quote:
If you don't believe me - try it!!
Wrong again - we don't believe you, so it's up to you to prove us wrong. Alas for you, this isn't the grade-school playground anymore, and your taunts of "I know something that the rest of you doooooooooon't" cut no ice here.
ewmayer is online now   Reply With Quote
Old 2006-08-16, 04:57   #30
bearnol
 
bearnol's Avatar
 
Sep 2005

12710 Posts
Default

You may already be aware of the Mersenneplustwo project - but if not I'd like to bring it to your attention, pls...
http://bearnol.is-a-geek.com/Mersenn...neplustwo.html
thanks,
J

Last fiddled with by akruppa on 2006-08-16 at 07:57 Reason: Post moved to "Tester(s) required" thread
bearnol is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help required ET_ Programming 19 2017-07-16 11:20
Triple check required houding PrimeNet 14 2015-12-21 09:34
New hardware - help required PageFault Software 2 2014-04-14 15:23
SBprp - a better PRP tester Ken_g6 Prime Sierpinski Project 10 2005-01-04 14:36
Sound Card Tester?? dave_0273 Hardware 2 2004-06-19 15:34

All times are UTC. The time now is 21:04.

Tue Jul 14 21:04:50 UTC 2020 up 111 days, 18:37, 0 users, load averages: 2.55, 2.16, 1.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.