mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2020-12-03, 10:46   #1
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

7×23 Posts
Default Factor is found by GMP-ECM but not by GMP-ECM[GWNUM]

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
Lowering the value of B1, to say 3e6, exhibits the same behavior except that
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.
YuL is offline   Reply With Quote
Old 2020-12-03, 16:47   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

735310 Posts
Default

GWNUM only handles 53-bit sigma values -- 8646756833320245055 was truncated.
Prime95 is online now   Reply With Quote
Old 2020-12-04, 00:22   #3
mathwiz
 
Mar 2019

24×32 Posts
Default

Quote:
Originally Posted by Prime95 View Post
GWNUM only handles 53-bit sigma values -- 8646756833320245055 was truncated.
Is the net result that GMP-ECM is less likely to find factors when linked with gwnum, and if so by how much? (what's the range of sigma values used?)
mathwiz is offline   Reply With Quote
Old 2020-12-04, 00:33   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·3·19·41 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2020-12-04, 08:34   #5
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

7×23 Posts
Default

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?
YuL is offline   Reply With Quote
Old 2020-12-04, 15:41   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

11100101110012 Posts
Default

I am not familiar with the GMP-ECM code. The problem (truncation) may only occur when specifying a sigma on the command line.
Prime95 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
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

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

Mon Mar 1 21:48:54 UTC 2021 up 88 days, 18 hrs, 0 users, load averages: 2.53, 2.29, 2.47

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.