Some code for factoring numbers up to 2^63

[bsquared]

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.

[bsquared]

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:

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

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!

[bsquared]

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.

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.

[Till]

Amazing!

[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?

[henryzz]

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.

[Till]

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.

[bsquared]

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

[bsquared]

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.

[sweety439]

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/

[bsquared]

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.