mersenneforum.org Some code for factoring numbers up to 2^63
 Register FAQ Search Today's Posts Mark Forums Read

2019-10-14, 14:43   #210
bsquared

"Ben"
Feb 2007

3,733 Posts

Quote:
 Originally Posted by Till Thanks for the explanation; in my ignorance I half-ways expected that to be a bug.
Honestly, not a bad assumption for any code I write :) Thank you for looking everything over so closely.

2022-09-19, 13:57   #211
bsquared

"Ben"
Feb 2007

E9516 Posts

Quote:
 Originally Posted by bsquared I've been playing around with ECM lately and I thought I'd try to implement a toy version that works for inputs that fit in a single machine word (64-bit). Here are timings for lists of 100k random semiprimes compared to other methods explored in this thread: Code: Bits ECM Lehman Brent Factor64 SIQS 42 1.03 0.65 1.31 1.32 44 1.19 1.18 1.73 1.75 46 1.41 1.63 2.27 2.35 48 1.72 2.67 3.15 3.25 50 2.17 4.31 4.35 4.54 52 2.82 6.89 6.1 6.29 54 3.33 10.7 8.5 8.82 56 3.97 16.8 11.9 12.5 58 5.02 26.5 16.9 17.6 16.44 60 6.25 42.2 23.6 24.8 18.2 62 7.57 33.1 35.2 64 9.83 48.6 53.1 21.6 It scales quite well, crossing over with Lehman at around 44 bits and remaining well ahead of all others up to 64 bits. Combined with a bit of trial division I imagine it would work well for arbitrary inputs too.
Over the past few weeks, Jeff Hurchalla has driven a series of updates to the microecm code. Foremost among them a faster way to do Montgomery arithmetic on single-limb inputs. He has also been very helpful in cleaning up the code and creating a much improved interface. The latest and greatest is now available in the yafu github repository.

Below is an updated table of timings on the benchmark semiprime input files (100,000 semiprime inputs each composed of 2 factors of approximately equal size). Unfortunately I don't have the same hardware anymore, so the table incorporates speedups from the hardware as well. (spbrent didn't change, so the hardware portion of the speed increase could be extracted from that.) The code was compiled with
icc -Ofast -march=skylake-avx512 -o uecm microecm.c -lm

Code:
Bits   ECM     Lehman  Brent
42     0.41    0.38    1.13
44     0.51    0.59    1.50
46     0.64    0.94    1.99
48     0.81            2.75
50     0.99            3.76
52     1.25            5.23
54     1.55            7.29
56     1.95            10.3
58     2.46            14.4
60     3.06            20.3
62     3.90            28.7
64     4.76
Thank you Jeff!

 2022-09-21, 18:21 #212 bsquared     "Ben" Feb 2007 1110100101012 Posts Update: I borrowed some single-limb vector multiply functions from avx-ecm to make a vectorized version of microecm that operates up to 52 bits (the precision limit of the multipliers). Here it is compared to the others when processing the 100k input test sets. vec_uecm is structured to process large-ish lists of inputs... that turned out to be necessary in order to keep vector occupancy high. Code: timings in seconds for 100k inputs. Bits vec_uecm uecm Lehman Brent 42 0.24 0.41 0.38 1.13 44 0.29 0.51 0.59 1.50 46 0.35 0.64 0.94 1.99 48 0.44 0.81 2.75 50 0.53 0.99 3.76 52 0.65 1.25 5.23 54 1.55 7.29 56 1.95 10.3 58 2.46 14.4 60 3.06 20.3 62 3.90 28.7 64 4.76 Code is available in the yafu github. Last fiddled with by bsquared on 2022-09-21 at 18:37
 2022-09-21, 18:59 #213 Till     "Tilman Neumann" Jan 2016 Germany 10258 Posts Amazing!
 2022-09-21, 21:29 #214 VBCurtis     "Curtis" Feb 2005 Riverside, CA 160B16 Posts Might this be useful as some sort of patch for GGNFS? Then again, is anyone conversant-enough in the code to try changing the current cofactor-splitting routine for this one?
2022-09-22, 12:46   #215
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

24×13×29 Posts

Quote:
 Originally Posted by VBCurtis Might this be useful as some sort of patch for GGNFS? Then again, is anyone conversant-enough in the code to try changing the current cofactor-splitting routine for this one?
lasieve5 contains ecm/p-1 code that no one uses. It is only activated with a parameter file present. The format for this parameter file is pretty hard to understand and there is no documentation. Code comments are the best we have as clues.

The cofactorisation strategy is handled in:
https://github.com/gchilders/lasieve...ows/strategy.w

Probably not too hard to substitute in an alternate ecm method. It is also worth bearing in mind that the majority of time is spent on larger numbers than this thread covers.

I suspect that switching to the CADO siever is probably a better use of time though.

Last fiddled with by henryzz on 2022-09-22 at 13:27

2022-09-22, 15:43   #216
Till

"Tilman Neumann"
Jan 2016
Germany

13·41 Posts

Quote:
 Originally Posted by henryzz It is also worth bearing in mind that the majority of time is spent on larger numbers than this thread covers.

Maybe Ben's 128 bit ecm (should be somewhere in this thread to find, I'm too lazy) would be more adequate? It looked pretty fast and might profit from recent improvements, too.

2022-09-28, 02:25   #217
bsquared

"Ben"
Feb 2007

3,733 Posts

Quote:
 Originally Posted by henryzz Probably not too hard to substitute in an alternate ecm method. It is also worth bearing in mind that the majority of time is spent on larger numbers than this thread covers. I suspect that switching to the CADO siever is probably a better use of time though.
Agreed on the CADO note. However I think on most jobs, microecm is completely sufficient. Anything with mfba/r of 64 or less can use microecm as a complete replacement for mpqs. For really big jobs or jobs with three large primes on one side, then tinyecm would need to be used as well as Till said.

So I went ahead and experimented with this, and indeed it does help! microecm is almost 10x faster than the assembly mpqs in ggnfs. But, that portion of the job is pretty small compared to the whole. So overall the speed increase is not that big. Still, it is something.

edit:
more details here

Last fiddled with by bsquared on 2022-09-28 at 03:32

 2022-10-26, 14:01 #218 bsquared     "Ben" Feb 2007 373310 Posts I've had some fun lately creating a micropm1 (P-1) method. I made a pretty graph of success rate with various B1. At the ridiculous looking B1=33 level I was surprised to see that it succeeds between 65% and 25% of the time on semiprime inputs between 32 and 40 bits (smallest factor between 16 and 20 bits), in an average time of 700 nanoseconds per run. It actually turns out to be useful, as a pretest prior to running ecm curves. Running P-1 at B1=333 for inputs between 52-64 bits makes microecm slightly faster. Attached Thumbnails
 2022-10-28, 03:19 #219 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 2×7×263 Posts I have collected online integer factorizers: 1. https://www.numberempire.com/numberfactorizer.php 2. https://www.alpertron.com.ar/ECM.HTM 3. http://www.javascripter.net/math/cal...calculator.htm 4. https://betaprojects.com/calculators/prime_factors.html 5. https://www.emathhelp.net/calculator...on-calculator/ 6. http://www.numbertheory.org/php/factor.html 7. https://primefan.tripod.com/Factorer.html 8. http://www.se16.info/js/factor.htm 9. http://math.fau.edu/Richman/mla/factor-f.htm all of them can factor all numbers with <= 63 bits, in fact, most of them can factor larger numbers, say numbers with about 128 bits also you can use Wolfram Alpha: https://www.wolframalpha.com/ also you can use the online MAGMA calculator: http://magma.maths.usyd.edu.au/calc/
 2022-10-28, 13:48 #220 bsquared     "Ben" Feb 2007 3,733 Posts Thanks for your list... As it happens, I know a thing or two about factoring larger numbers as well. The point of this thread is factoring many small numbers very quickly.

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 18 2017-08-27 14:56 ShridharRasal Factoring 10 2008-03-20 17:17 Peter Nelson Software 9 2005-03-30 18:28 Axel Fox Software 14 2003-07-04 18:57 Joe O Software 2 2002-09-13 23:39

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

Tue Feb 7 02:09:53 UTC 2023 up 172 days, 23:38, 1 user, load averages: 0.88, 1.13, 1.10