Python Driver for GGNFS and MSIEVE - Page 20

Brian Gladman · 2010-02-02, 21:01

Yes - drop the _1 in the miller_rabin def statement.

I had three versions of miller_rabin that I tested agianst each other in a separate program but I forgot to remove the '_1' when I pasted the selected version into the script.

Brian

frmky · 2010-02-02, 21:10

Quote:

Originally Posted by Brian Gladman

Is anyone willing to suggest some values?

Actually, minrels depends on lpbr/a rather than decimal digits. For most cases, I run with lpbr/a equal to the same value, and the approximate minrels I use are below. Feel free to tweak them based on your own experiences.

Code:

lpbr/a   minrels (millions)
 27        11
 28        22
 29        45
 30       110
 31       220
 32       425

I'm not accustomed to running with lpbr/a less than 27, but halving for each power of two should not be too far off. For the larger values (30 and above) there is some oversieving in those numbers. A matrix can usually be built with somewhat fewer relations, but it is significantly improved with the additional sieving.

10metreh · 2010-02-03, 07:34

Quote:

Originally Posted by frmky

Actually, minrels depends on lpbr/a rather than decimal digits. For most cases, I run with lpbr/a equal to the same value, and the approximate minrels I use are below. Feel free to tweak them based on your own experiences.

Code:

lpbr/a   minrels (millions)
 27        11
 28        22
 29        45
 30       110
 31       220
 32       425

I'm not accustomed to running with lpbr/a less than 27, but halving for each power of two should not be too far off. For the larger values (30 and above) there is some oversieving in those numbers. A matrix can usually be built with somewhat fewer relations, but it is significantly improved with the additional sieving.

Even the 27 figure looks like an overestimate for GNFS. 26 is about 4.5M (but can be lower), 25 is about 2M. 27 varies from about 7.5M to about 10.5M depending on size.

Brian Gladman · 2010-02-03, 10:37

Thanks to everyone for the information they have provided on required relations (and bugs in factmsieve.py).

We now have a lot of data for lpbr/a = 26 and 27 and the results for the relations needed for N decimal digits are:

Code:

lpbr/a                  rels (M)   data fit range
  26       4 + 0.900 * (N -  98)    98 <= N < 109
  27       7 + 0.175 * (N - 109)   109 <= N < 130

The data below 98 and above 130 is too limited to draw sensible conclusions at the moment. I hence suggest that, for lpbr/a values of 26 and 27, I use 95% of the above values for minrels.

I would hope we can collect data for lpbr/a = 25 quite quickly.

Brian

tmorrow · 2010-02-03, 12:26

My latest c132 just failed, using factmsieve.py 0.44. log fragment below.

Code:

Wed Feb 03 12:33:07 2010 Found 20847638 relations, 125.8% of the estimated minimum (16577238).
Wed Feb 03 12:33:07 2010 -> msieve -s c132.dat -l c132.log -i c132.ini -v -nf c132.fb -t 3 -nc1
Wed Feb 03 12:33:08 2010  
Wed Feb 03 12:33:08 2010  
Wed Feb 03 12:33:08 2010  Msieve v. 1.43
Wed Feb 03 12:33:08 2010  random seeds: 7bc25838 dd99475b
Wed Feb 03 12:33:08 2010  factoring 429962405704076145115191210862434843646721357610731407212040688044972805708211650820675393220494062079445933802318023112133336942751 (132 digits)
Wed Feb 03 12:33:09 2010  searching for 15-digit factors
Wed Feb 03 12:33:09 2010  commencing number field sieve (132-digit input)
Wed Feb 03 12:33:09 2010  R0: -38037036708079335067415374
Wed Feb 03 12:33:09 2010  R1:  227705585552093
Wed Feb 03 12:33:09 2010  A0:  1222481236174940950564260795655035
Wed Feb 03 12:33:09 2010  A1:  8553375075495923389487352322
Wed Feb 03 12:33:09 2010  A2: -7772706550307641196639
Wed Feb 03 12:33:09 2010  A3: -15200346995541290
Wed Feb 03 12:33:09 2010  A4:  6949706292
Wed Feb 03 12:33:09 2010  A5:  5400
Wed Feb 03 12:33:09 2010  skew 1074040.16, size 1.094205e-012, alpha -6.437809, combined = 6.315522e-011
Wed Feb 03 12:33:09 2010  
Wed Feb 03 12:33:09 2010  commencing relation filtering
Wed Feb 03 12:33:09 2010  estimated available RAM is 2048.0 MB
Wed Feb 03 12:33:09 2010  commencing duplicate removal, pass 1
Wed Feb 03 12:35:40 2010  found 2741788 hash collisions in 20847637 relations
Wed Feb 03 12:36:20 2010  added 54 free relations
Wed Feb 03 12:36:20 2010  commencing duplicate removal, pass 2
Wed Feb 03 12:37:53 2010  found 2381514 duplicates and 18466177 unique relations
Wed Feb 03 12:37:53 2010  memory use: 98.6 MB
Wed Feb 03 12:37:53 2010  reading ideals above 10420224
Wed Feb 03 12:37:56 2010  commencing singleton removal, initial pass
Wed Feb 03 12:40:28 2010  memory use: 376.5 MB
Wed Feb 03 12:40:28 2010  reading all ideals from disk
Wed Feb 03 12:40:29 2010  memory use: 325.4 MB
Wed Feb 03 12:40:30 2010  commencing in-memory singleton removal
Wed Feb 03 12:40:31 2010  begin with 18466177 relations and 19220046 unique ideals
Wed Feb 03 12:40:45 2010  reduce to 6455367 relations and 5038610 ideals in 23 passes
Wed Feb 03 12:40:45 2010  max relations containing the same ideal: 35
Wed Feb 03 12:40:46 2010  reading ideals above 100000
Wed Feb 03 12:40:46 2010  commencing singleton removal, initial pass
Wed Feb 03 12:42:09 2010  memory use: 172.3 MB
Wed Feb 03 12:42:09 2010  reading all ideals from disk
Wed Feb 03 12:42:10 2010  memory use: 243.1 MB
Wed Feb 03 12:42:11 2010  keeping 6384888 ideals with weight <= 200, target excess is 34254
Wed Feb 03 12:42:12 2010  commencing in-memory singleton removal
Wed Feb 03 12:42:12 2010  begin with 6455422 relations and 6384888 unique ideals
Wed Feb 03 12:42:23 2010  reduce to 6425662 relations and 6354844 ideals in 12 passes
Wed Feb 03 12:42:23 2010  max relations containing the same ideal: 200
Wed Feb 03 12:42:27 2010  removing 294090 relations and 278548 ideals in 15542 cliques
Wed Feb 03 12:42:27 2010  commencing in-memory singleton removal
Wed Feb 03 12:42:28 2010  begin with 6131572 relations and 6354844 unique ideals
Wed Feb 03 12:42:37 2010  reduce to 6120276 relations and 6064962 ideals in 10 passes
Wed Feb 03 12:42:37 2010  max relations containing the same ideal: 199
Wed Feb 03 12:42:41 2010  removing 209229 relations and 193687 ideals in 15542 cliques
Wed Feb 03 12:42:41 2010  commencing in-memory singleton removal
Wed Feb 03 12:42:42 2010  begin with 5911047 relations and 6064962 unique ideals
Wed Feb 03 12:42:48 2010  reduce to 5905047 relations and 5865256 ideals in 8 passes
Wed Feb 03 12:42:48 2010  max relations containing the same ideal: 196
Wed Feb 03 12:42:50 2010  relations with 0 large ideals: 92
Wed Feb 03 12:42:50 2010  relations with 1 large ideals: 76
Wed Feb 03 12:42:50 2010  relations with 2 large ideals: 937
Wed Feb 03 12:42:50 2010  relations with 3 large ideals: 13691
Wed Feb 03 12:42:50 2010  relations with 4 large ideals: 100818
Wed Feb 03 12:42:50 2010  relations with 5 large ideals: 435458
Wed Feb 03 12:42:50 2010  relations with 6 large ideals: 1127437
Wed Feb 03 12:42:50 2010  relations with 7+ large ideals: 4226538
Wed Feb 03 12:42:50 2010  commencing 2-way merge
Wed Feb 03 12:42:56 2010  reduce to 3252343 relation sets and 3212556 unique ideals
Wed Feb 03 12:42:56 2010  ignored 4 oversize relation sets
Wed Feb 03 12:42:56 2010  commencing full merge
Wed Feb 03 12:45:14 2010  memory use: 99.4 MB
Wed Feb 03 12:45:14 2010  found 18741 cycles, need 670454
Wed Feb 03 12:45:14 2010  too few cycles, matrix probably cannot build

Frnky's suggestion of minrel=22 million for lpr/a=28 seems like a good estimate.

Mini-Geek · 2010-02-03, 13:57

Quote:

Originally Posted by tmorrow

My latest c132 just failed, using factmsieve.py 0.44. log fragment below.

Code:

...
Wed Feb 03 12:45:14 2010  too few cycles, matrix probably cannot build

If you do more sieving it should work.

tmorrow · 2010-02-03, 20:04

Quote:

Originally Posted by Mini-Geek

If you do more sieving it should work.

Yes, another 1/2 hour sieving was sufficient - thanks.

Brian Gladman · 2010-02-03, 22:42

From your result it seems that the current minrels estimate is a lot lower than it should be for a c132 - it was at 126% and still needed more.

Brian

fivemack · 2010-02-05, 00:29

I've got a script for doing GNFS on largish aliquot numbers, and have been running it on a quad-core for a month, so I've got a little experience accumulated about the 85-120 digit range.

For 95-105 digits, I use lpb=24 alim=1000000, the 12e siever, and minrels=25000*{digits}-600000 looks to fit the trend reasonably.

105-115 I use lpb=25 alim=2000000 and the 12e siever but I don't have information to recommend other than a flat minrels=3800000; certainly 25 with 12e is better than 26 with 13e in this range.

Don't have any terribly good confirmation of where the 26/27 borderline lies, I have a suspicion it's around 125 digits (using 13e for both); looks as if 13e beats 14e up to at least C135.

I believe you can estimate the duplication percentage pretty well as a function of the number of digits for a given siever and lpb (that is, a plot of duplication-percentage against digits is composed of a set of what look like quite well-fit-with-straight-lines blocks; for 95-105 digits, where I've got most data, unique% (=number of unique rels when msieve starts working / number of rels at that point) fits 98% of the time within 0.04 of 2.31 - 0.0141*digits); so I'd be tempted to estimate minrels by estimating min_unique_rels and dividing by an estimated unique%

xilman · 2010-02-07, 16:24

Brian: do you have an easily-digestible list of the architectural differences between your Python script and the Perl script from which it was developed?

I ask because I have access to a rather nice RedHat EL5 system but that version of RH has only Python 2.4 and your script requires a later version. It can't easily be upgraded (it's not my system for a start) and, unlike you, I find Perl rather more portable and much easier to program than Python.

By "architectural differences" I mean the the nature and/or order of binaries to be run, command line arguments, configuration parameters and the like.

If possible, I'd like to upgrade the Perl script so that those who find Perl more congenial can continue to use it.

Paul

EdH · 2010-02-07, 17:25

Paul,

I noticed an earlier posting about Portable Python and am about to see if it will work for my bootable CD/USB project. Have you possibly explored this already?

I will provide more info, if this does work for me.

Alternately, I would be willing to help with a project to update the Perl script, although my knowledge base is rather limited. This would provide me an opportunity to expand it...

Take Care,
Ed

2010-02-03, 10:37	#213
Brian Gladman May 2008 Worcester, United Kingdom 532₁₀ Posts	Thanks to everyone for the information they have provided on required relations (and bugs in factmsieve.py). We now have a lot of data for lpbr/a = 26 and 27 and the results for the relations needed for N decimal digits are: Code: lpbr/a rels (M) data fit range 26 4 + 0.900 * (N - 98) 98 <= N < 109 27 7 + 0.175 * (N - 109) 109 <= N < 130 The data below 98 and above 130 is too limited to draw sensible conclusions at the moment. I hence suggest that, for lpbr/a values of 26 and 27, I use 95% of the above values for minrels. I would hope we can collect data for lpbr/a = 25 quite quickly. Brian

2010-02-05, 00:29	#218
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	some thoughts on parameter choice I've got a script for doing GNFS on largish aliquot numbers, and have been running it on a quad-core for a month, so I've got a little experience accumulated about the 85-120 digit range. For 95-105 digits, I use lpb=24 alim=1000000, the 12e siever, and minrels=25000{digits}-600000 looks to fit the trend reasonably. 105-115 I use lpb=25 alim=2000000 and the 12e siever but I don't have information to recommend other than a flat minrels=3800000; certainly 25 with 12e is better than 26 with 13e in this range. Don't have any terribly good confirmation of where the 26/27 borderline lies, I have a suspicion it's around 125 digits (using 13e for both); looks as if 13e beats 14e up to at least C135. I believe you can estimate the duplication percentage pretty well as a function of the number of digits for a given siever and lpb (that is, a plot of duplication-percentage against digits is composed of a set of what look like quite well-fit-with-straight-lines blocks; for 95-105 digits, where I've got most data, unique% (=number of unique rels when msieve starts working / number of rels at that point) fits 98% of the time within 0.04 of 2.31 - 0.0141digits); so I'd be tempted to estimate minrels by estimating min_unique_rels and dividing by an estimated unique% Last fiddled with by fivemack on 2010-02-05 at 00:36

2010-02-07, 16:24	#219
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 10,753 Posts	Diffs from factMsieve.pl Brian: do you have an easily-digestible list of the architectural differences between your Python script and the Perl script from which it was developed? I ask because I have access to a rather nice RedHat EL5 system but that version of RH has only Python 2.4 and your script requires a later version. It can't easily be upgraded (it's not my system for a start) and, unlike you, I find Perl rather more portable and much easier to program than Python. By "architectural differences" I mean the the nature and/or order of binaries to be run, command line arguments, configuration parameters and the like. If possible, I'd like to upgrade the Perl script so that those who find Perl more congenial can continue to use it. Paul

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve & ggnfs on MacOS	xilman	Msieve	8	2017-05-20 00:12
Factorizing with MSIEVE, GGNFS & Factmsieve.py	Romuald	Msieve	24	2015-11-09 20:16
Infinite loop for ggnfs or msieve	Greebley	Aliquot Sequences	4	2013-02-06 19:28
Error running GGNFS+msieve+factmsieve.py	D. B. Staple	Factoring	6	2011-06-12 22:23
A new driver? (or type of driver?)	10metreh	Aliquot Sequences	3	2010-02-15 15:57

2010-02-02, 21:01	#210
Brian Gladman May 2008 Worcester, United Kingdom 2²·7·19 Posts	Yes - drop the _1 in the miller_rabin def statement. I had three versions of miller_rabin that I tested agianst each other in a separate program but I forgot to remove the '_1' when I pasted the selected version into the script. Brian

2010-02-03, 22:42	#217
Brian Gladman May 2008 Worcester, United Kingdom 532₁₀ Posts	From your result it seems that the current minrels estimate is a lot lower than it should be for a c132 - it was at 126% and still needed more. Brian

2010-02-07, 17:25	#220
EdH "Ed Hall" Dec 2009 Adirondack Mtns 11×347 Posts	Paul, I noticed an earlier posting about Portable Python and am about to see if it will work for my bootable CD/USB project. Have you possibly explored this already? I will provide more info, if this does work for me. Alternately, I would be willing to help with a project to update the Perl script, although my knowledge base is rather limited. This would provide me an opportunity to expand it... Take Care, Ed