![]() |
![]() |
#1 |
Feb 2012
Paris, France
16110 Posts |
![]()
I wanted to switch from
GMP-ECM 7.0.4 [configured with GMP 6.1.2, --enable-asm-redc] to GMP-ECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, --enable-asm-redc] for my factoring work. So I was doing some testing and it appears that a factor found by the first one is not found by the second one: Code:
GMP-ECM 7.0.4 [configured with GMP 6.1.2, --enable-asm-redc] [ECM] Tuned for x86_64/k8/params.h Input number is (103*10^286-1)/(3*43*47*9283691*60137568222544788641951) (255 digits) [Thu Dec 3 11:31:56 2020] Using MODMULN [mulredc:0, sqrredc:2] Using B1=6500000, B2=14271500890, polynomial Dickson(12), sigma=0:8646756833320245055 dF=16384, k=5, d=158340, d2=11, i0=31 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 178 1111 8108 67760 637802 6669522 7.6e+07 9.8e+08 1.3e+10 6.6e+11 Step 1 took 33016ms ********** Factor found in step 1: 42010916546178371843382678844466221253227 Found prime factor of 41 digits: 42010916546178371843382678844466221253227 Composite cofactor ((103*10^286-1)/(3*43*47*9283691*60137568222544788641951))/42010916546178371843382678844466221253227 has 214 digits Peak memory usage: 4MB Code:
GMP-ECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.8, --enable-asm-redc] [ECM] Tuned for x86_64/k8/params.h Due to incompatible licenses, this binary file must not be distributed. Input number is (103*10^286-1)/(3*43*47*9283691*60137568222544788641951) (255 digits) Found number: 103*10^286 + -1 [Thu Dec 3 11:33:38 2020] Using MODMULN [mulredc:0, sqrredc:2] Using B1=6500000, B2=14271500890, polynomial Dickson(12), sigma=0:8646756833320245055 dF=16384, k=5, d=158340, d2=11, i0=31 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 178 1111 8108 67760 637802 6669522 7.6e+07 9.8e+08 1.3e+10 6.6e+11 Using gwnum_ecmStage1(103, 10, 286, -1, 6500000, 1) Step 1 took 27268ms Using 30 small primes for NTT Estimated memory usage: 81.07MB Initializing tables of differences for F took 52ms Computing roots of F took 720ms Building F from its roots took 552ms Computing 1/F took 300ms Initializing table of differences for G took 44ms Computing roots of G took 636ms Building G from its roots took 576ms Computing roots of G took 668ms Building G from its roots took 608ms Computing G * H took 168ms Reducing G * H mod F took 172ms Computing roots of G took 664ms Building G from its roots took 588ms Computing G * H took 164ms Reducing G * H mod F took 168ms Computing roots of G took 664ms Building G from its roots took 584ms Computing G * H took 160ms Reducing G * H mod F took 164ms Computing roots of G took 652ms Building G from its roots took 576ms Computing G * H took 152ms Reducing G * H mod F took 160ms Computing polyeval(F,G) took 1076ms Computing product of all F(g_i) took 8ms Step 2 took 10312ms Expected time to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 1.86h 11.60h 3.53d 29.47d 277.41d 7.95y 90.42y 1164y 15695y 790907y Peak memory usage: 139MB the factor is found in step 2 instead of step 1. Any thoughts? Note: I built the binaries myself, I patched the source code of ECM 7.0.4 to include rev3084 (which fixes the bug reported here) and that is the only change I made. |
![]() |
![]() |
![]() |
#2 |
P90 years forever!
Aug 2002
Yeehaw, FL
32·823 Posts |
![]()
GWNUM only handles 53-bit sigma values -- 8646756833320245055 was truncated.
|
![]() |
![]() |
![]() |
#3 |
Mar 2019
100101012 Posts |
![]() |
![]() |
![]() |
![]() |
#4 |
"Curtis"
Feb 2005
Riverside, CA
10010100000012 Posts |
![]()
No, it just uses a smaller range of sigma. Each individual sigma has the same chance to find a factor, if one is to be found. Doesn't matter if the possible-sigma pool is 1 to 2^50 or 1 to 2^60.
If the pool were 1 to 10^9, then running hundreds of thousands of curves would likely repeat some work- that's a waste, so the pool is much bigger than that. GWNUM has a higher chance to repeat a curve due to a smaller pool, but if you calculate the odds you'll see it's still very very unlikely. |
![]() |
![]() |
![]() |
#5 |
Feb 2012
Paris, France
7·23 Posts |
![]()
Then when using a GMP-ECM linked with GWNUM the value of sigma
displayed is not the real one, I have to truncate it to a value < 253 to deduce the real one? |
![]() |
![]() |
![]() |
#6 |
P90 years forever!
Aug 2002
Yeehaw, FL
32·823 Posts |
![]()
I am not familiar with the GMP-ECM code. The problem (truncation) may only occur when specifying a sigma on the command line.
|
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Factor found that should have been found by P-1 | tha | Data | 65 | 2020-08-05 21:11 |
F12 factor found? | johnadam74 | FermatSearch | 16 | 2016-11-03 12:10 |
44-digit factor found using ECM w/ B1=1e6 & B2=1e8 | WVU Mersenneer | Factoring | 8 | 2010-04-24 17:01 |
found this factor | tha | Factoring | 4 | 2007-06-18 19:56 |
After a factor is found it keeps on going | jocelynl | Software | 6 | 2004-08-07 01:31 |