mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-02-28, 16:03   #12
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100011002 Posts
Default

Thanks for pointing out the dead link! That is the correct paper. I find it an interesting method, and it turned out to be useful for a small range of tiny composites to maximize performance. For native ints outside that range I don't use it however (after trial and power detection I find Brent/Rho, P-1, and SQUFOF are the methods that work best for me). I don't call it at all for my general factoring of larger inputs, but it's useful to have available.
danaj is offline   Reply With Quote
Old 2017-02-28, 19:14   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1067110 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Which is actually pretty important!
Indeed.

Back in the hey-day of MPQS I started a search for algorithms optimised for factoring double large prime residues. If you don't know what that means, it's essentially composites known to be the product of two primes of roughly comparable magnitude. If Fermat's method stands a chance, it's here.

My experiments showed that Fermat was pretty good, though slightly inferior to SQFOF in practice. Pollard rho wasn't bad but the P \pm 1 methods were hopeless on average. Needless to say, trial division wasn't in the running. Peter Montgomery joined in the search and broadly reproduced my findings. Eventually a carefully optimised ECM proved to be the best and, AFAIK, it's still used today.
xilman is offline   Reply With Quote
Old 2017-02-28, 22:13   #14
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,433 Posts
Default

Quote:
Originally Posted by xilman View Post
Indeed.

Back in the hey-day of MPQS I started a search for algorithms optimised for factoring double large prime residues. If you don't know what that means, it's essentially composites known to be the product of two primes of roughly comparable magnitude. If Fermat's method stands a chance, it's here.

My experiments showed that Fermat was pretty good, though slightly inferior to SQFOF in practice. Pollard rho wasn't bad but the P \pm 1 methods were hopeless on average. Needless to say, trial division wasn't in the running. Peter Montgomery joined in the search and broadly reproduced my findings. Eventually a carefully optimised ECM proved to be the best and, AFAIK, it's still used today.
I would be interested in seeing data of carefully optimized ecm for dlp residues in bit ranges of say 38 to 52 bits. Can you point me toward any or toward implementations if the data does not exist?
bsquared is offline   Reply With Quote
Old 2017-03-01, 00:09   #15
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16EC16 Posts
Default

Quote:
Originally Posted by bsquared View Post
I would be interested in seeing data of carefully optimized ecm for dlp residues in bit ranges of say 38 to 52 bits. Can you point me toward any or toward implementations if the data does not exist?
lasieve5 contains ecm code although it is not used as we don't provide a parameter file. Optimizing the parameters would be quite a job.
I don't know if CADO uses ecm. It might.
henryzz is offline   Reply With Quote
Old 2017-03-06, 11:23   #16
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353710 Posts
Default

CADO uses very highly optimized P+-1 and ECM. Small MPQS was under development last time I looked.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...? jasong jasong 8 2017-04-07 00:23
Simple Script to get Trial Factoring Work jfamestad PrimeNet 3 2016-11-06 20:32
Simple factoring challenge + questions siegert81 Factoring 12 2016-05-28 18:36
This simple algorithm incomplete can only calculate prime numbers? Ale Miscellaneous Math 38 2015-11-29 23:27
Simple Idea for SIQS ThiloHarich Factoring 5 2006-03-16 08:22

All times are UTC. The time now is 03:03.

Thu May 6 03:03:39 UTC 2021 up 27 days, 21:44, 0 users, load averages: 2.91, 3.14, 3.02

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