Python Driver for GGNFS and MSIEVE - Page 53

warut · 2011-04-28, 16:42

Mini-Geek, thanks so much for your detailed solution. It worked perfectly, and I already got the factors.

10metreh · 2011-04-29, 17:31

Clearly the relations file did get wiped (but the first line which only contains the input number was left), so it was lucky that spairs.save.gz was there.

Has anyone ever looked for the source of this bug? It's been around for a while but hasn't been fixed.

Walter Nissen · 2011-05-01, 11:57

Quote:

Originally Posted by 10metreh

Has anyone ever looked for the source of this bug? It's been around for a while but hasn't been fixed.

Is it possible the bug was fixed between Version 0.72 and 0.76 ?
( I don't know if this info is online . )

Karl M Johnson · 2011-05-04, 10:59

Using factmsieve.py v0.76 .
Got this polynomial using latest release of msieve:

Code:

name: skewered
n: 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851
Y0: -1297771518994183945943
Y1:  271016798477
c0: -1814973293353740202067064
c1: -624244968121919918
c2: -32994656214283
c3: -21914360
c4:  10200
skew: 155575.03
type: gnfs

It stops with the following errors:

Code:

C:\Program Files (x86)\msieve\ggnfs\example>factmsieve.py skewered.poly
-> ________________________________________________________________
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support. It is Copyright, 2010, Brian Gladman and is |
-> | a conversion of factmsieve.pl that is Copyright, 2004, Chris |
-> | Monico.    Version 0.76 (Python 2.6 or later) 10th Nov 2010. |
-> |______________________________________________________________|
-> This is client 1 of 1
-> Running on 4 Cores with 1 hyper-thread per Core
-> Working with NAME = skewered
Traceback (most recent call last):
  File "C:\Program Files (x86)\msieve\ggnfs\example\factmsieve.py", line 2049, in <module>
    read_parameters(fact_p, poly_p, lats_p)
  File "C:\Program Files (x86)\msieve\ggnfs\example\factmsieve.py", line 1246, in read_parameters
    fact_p, pols_p, lats_p, clas_p)
  File "C:\Program Files (x86)\msieve\ggnfs\example\factmsieve.py", line 551, in load_default_parameters
    clas_p['cl_a'] = int(tu[o + 18])
IndexError: list index out of range

C:\Program Files (x86)\msieve\ggnfs\example>pause
Press any key to continue . . .

Any advice ?

Andi_HB · 2011-05-04, 12:12

Why do you try to do this small number with factmsieve?
Yafu is much faster for this job and do this number in less then 30 seconds.

Code:

05/04/11 14:06:33 v1.25 @ LAPPIE, ****************************
05/04/11 14:06:33 v1.25 @ LAPPIE, Starting factorization of 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851
05/04/11 14:06:33 v1.25 @ LAPPIE, ****************************
05/04/11 14:06:33 v1.25 @ LAPPIE, rho: x^2 + 1, starting 1000 iterations on C89
05/04/11 14:06:33 v1.25 @ LAPPIE, rho: x^2 + 3, starting 1000 iterations on C89
05/04/11 14:06:33 v1.25 @ LAPPIE, rho: x^2 + 2, starting 1000 iterations on C89
05/04/11 14:06:33 v1.25 @ LAPPIE, pp1: starting B1 = 20K, B2 = gmp-ecm default on C89
05/04/11 14:06:33 v1.25 @ LAPPIE, pp1: starting B1 = 20K, B2 = gmp-ecm default on C89
05/04/11 14:06:34 v1.25 @ LAPPIE, pp1: starting B1 = 20K, B2 = gmp-ecm default on C89
05/04/11 14:06:34 v1.25 @ LAPPIE, pm1: starting B1 = 100K, B2 = gmp-ecm default on C89
05/04/11 14:06:34 v1.25 @ LAPPIE, prp22 = 6551232298747279617361
05/04/11 14:06:35 v1.25 @ LAPPIE, Finished 25 curves using Lenstra ECM method on C67 input, B1 = 2K, B2 = gmp-ecm default
05/04/11 14:06:38 v1.25 @ LAPPIE, Finished 22 curves using Lenstra ECM method on C67 input, B1 = 11K, B2 = gmp-ecm default
05/04/11 14:06:38 v1.25 @ LAPPIE, Finished 1 curves using Lenstra ECM method on C67 input, B1 = 50K, B2 = gmp-ecm default
05/04/11 14:06:38 v1.25 @ LAPPIE, pp1: starting B1 = 200K, B2 = gmp-ecm default on C67
05/04/11 14:06:39 v1.25 @ LAPPIE, starting SIQS on c67: 4416415577418151065093947608792288540863487078676650877168898846091
05/04/11 14:06:39 v1.25 @ LAPPIE, random seeds: 2011615933, 3424345267
05/04/11 14:06:39 v1.25 @ LAPPIE, ==== sieve params ====
05/04/11 14:06:39 v1.25 @ LAPPIE, n = 67 digits, 222 bits
05/04/11 14:06:39 v1.25 @ LAPPIE, factor base: 8736 primes (max prime = 194443)
05/04/11 14:06:39 v1.25 @ LAPPIE, single large prime cutoff: 12638795 (65 * pmax)
05/04/11 14:06:39 v1.25 @ LAPPIE, allocating 4 large prime slices of factor base
05/04/11 14:06:39 v1.25 @ LAPPIE, buckets hold 2048 elements
05/04/11 14:06:39 v1.25 @ LAPPIE, sieve interval: 3 blocks of size 65536
05/04/11 14:06:39 v1.25 @ LAPPIE, polynomial A has ~ 8 factors
05/04/11 14:06:39 v1.25 @ LAPPIE, using multiplier of 1
05/04/11 14:06:39 v1.25 @ LAPPIE, using SPV correction of 20 bits, starting at offset 29
05/04/11 14:06:39 v1.25 @ LAPPIE, using SSE2 for trial division and x64 sieve scanning
05/04/11 14:06:39 v1.25 @ LAPPIE, trial factoring cutoff at 76 bits
05/04/11 14:06:39 v1.25 @ LAPPIE, ==== sieving started ( 4 threads) ====
05/04/11 14:07:00 v1.25 @ LAPPIE, trial division touched 571474 sieve locations out of 8256356352
05/04/11 14:07:00 v1.25 @ LAPPIE, 9013 relations found: 4379 full + 4634 from 43570 partial, using 20997 polys (314 A polys)
05/04/11 14:07:00 v1.25 @ LAPPIE, on average, sieving found 2.28 rels/poly and 2265.16 rels/sec
05/04/11 14:07:00 v1.25 @ LAPPIE, trial division touched 571474 sieve locations out of 8256356352
05/04/11 14:07:00 v1.25 @ LAPPIE, ==== post processing stage (msieve-1.38) ====
05/04/11 14:07:00 v1.25 @ LAPPIE, begin with 47949 relations
05/04/11 14:07:00 v1.25 @ LAPPIE, reduce to 13041 relations in 2 passes
05/04/11 14:07:00 v1.25 @ LAPPIE, recovered 13041 relations
05/04/11 14:07:00 v1.25 @ LAPPIE, recovered 9719 polynomials
05/04/11 14:07:00 v1.25 @ LAPPIE, attempting to build 9013 cycles
05/04/11 14:07:00 v1.25 @ LAPPIE, found 9013 cycles in 1 passes
05/04/11 14:07:00 v1.25 @ LAPPIE, distribution of cycle lengths:
05/04/11 14:07:00 v1.25 @ LAPPIE,    length 1 : 4379
05/04/11 14:07:00 v1.25 @ LAPPIE,    length 2 : 4634
05/04/11 14:07:00 v1.25 @ LAPPIE, largest cycle: 2 relations
05/04/11 14:07:00 v1.25 @ LAPPIE, matrix is 8736 x 9013 (1.0 MB) with weight 238335 (26.44/col)
05/04/11 14:07:00 v1.25 @ LAPPIE, sparse part has weight 238335 (26.44/col)
05/04/11 14:07:00 v1.25 @ LAPPIE, filtering completed in 4 passes
05/04/11 14:07:00 v1.25 @ LAPPIE, matrix is 7810 x 7874 (0.9 MB) with weight 203633 (25.86/col)
05/04/11 14:07:00 v1.25 @ LAPPIE, sparse part has weight 203633 (25.86/col)
05/04/11 14:07:00 v1.25 @ LAPPIE, commencing Lanczos iteration
05/04/11 14:07:00 v1.25 @ LAPPIE, memory use: 1.3 MB
05/04/11 14:07:01 v1.25 @ LAPPIE, lanczos halted after 125 iterations (dim = 7805)
05/04/11 14:07:01 v1.25 @ LAPPIE, recovered 61 nontrivial dependencies
05/04/11 14:07:01 v1.25 @ LAPPIE, prp42 = 751330017694728904140304580860365836886931
05/04/11 14:07:01 v1.25 @ LAPPIE, prp25 = 5878130080532166726744361
05/04/11 14:07:01 v1.25 @ LAPPIE, Lanczos elapsed time = 0.5020 seconds.
05/04/11 14:07:01 v1.25 @ LAPPIE, Sqrt elapsed time = 0.0430 seconds.
05/04/11 14:07:01 v1.25 @ LAPPIE, SIQS elapsed time = 21.7130 seconds.
05/04/11 14:07:01 v1.25 @ LAPPIE, 
05/04/11 14:07:01 v1.25 @ LAPPIE, 
05/04/11 14:07:01 v1.25 @ LAPPIE, Total factoring time = 27.7140 seconds

I test it now with factmsieve.py on my Laptop.
Its running normal till now but with other polynomial.

n: 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851
Y0: -2215905079382191980526
Y1: 218821283789
c0: -34021240132395802295145885
c1: 57303669967062965034
c2: -102496079340637
c3: 197954728
c4: 1200
skew: 564611.13
type: gnfs

Andi_HB · 2011-05-04, 13:31

Number: c89
N = 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851 (89 digits)
Divisors found:
r1=6551232298747279617361 (pp22)
r2=5878130080532166726744361 (pp25)
r3=751330017694728904140304580860365836886931 (pp42)
Version: Msieve v. 1.48
Total time: 0.74 hours.
Factorization parameters were as follows:
n: 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851
Y0: -2215905079382191980526
Y1: 218821283789
c0: -34021240132395802295145885
c1: 57303669967062965034
c2: -102496079340637
c3: 197954728
c4: 1200
skew: 564611.13
type: gnfs
Factor base limits: 600000/600000
Large primes per side: 3
Large prime bits: 25/25
Sieved algebraic special-q in [0, 0)
Total raw relations: 1622824
Relations: 87620 relations
Pruned matrix : 61424 x 61651
Polynomial selection time: 0.11 hours.
Total sieving time: 0.60 hours.
Total relation processing time: 0.01 hours.
Matrix solve time: 0.01 hours.
time per square root: 0.02 hours.
Prototype def-par.txt line would be: gnfs,88,4,56,1500,0.0006,0.3,200,15,10000,500,600000,600000,25,25,43,43,2.2,2.2,10000
total time: 0.74 hours.
x86 Family 6 Model 23 Stepping 6, GenuineIntel
Windows-Vista-6.0.6002-SP2
processors: 2, speed: 2.09GHz

factmsieve.py works fine for me.

Karl M Johnson · 2011-05-04, 13:54

I generated that number, so I did know the factors and their sizes

I just have no hunch about why this poly doesnt work.

My poly did not want to be accepted?

Karl M Johnson · 2011-05-04, 14:06

False alarm! I've updated to newer GNFS binaries from Jeff's website(ty!) and it worked.

EdH · 2011-05-20, 18:10

I'm running a c127 that won't stop sieving. I ran it on a linux box and it finally crashed with a 255 error. This winXP machine just keeps going:

Code:

Found 21636614 relations, 129.4% of the estimated minimum (16720000).
-> msieve -s ..\ggnfs_8845424710899977815163938063336156710467852144650354456276
554838704070938061544223956879363372317220791203448437149670370751897\test.dat -
l ..\ggnfs_884542471089997781516393806333615671046785214465035445627655483870407
0938061544223956879363372317220791203448437149670370751897\test.log -i ..\ggnfs_
88454247108999778151639380633361567104678521446503544562765548387040709380615442
23956879363372317220791203448437149670370751897\test.ini -nf ..\ggnfs_8845424710
89997781516393806333615671046785214465035445627655483870407093806154422395687936
3372317220791203448437149670370751897\test.fb -t 1 -nc1
read 10M relations
-> making sieve job for q = 7350000 in 7350000 .. 7450000 as file test.job.T0
-> Lattice sieving algebraic q from 7350000 to 7450000.
-> gnfs-lasieve4I13e -k -o spairs.out.T0 -v -n0 -a test.job.T0
FBsize 421101+0 (deg 5), 419245+0 (deg 1)
total yield: 467310, q=7450007 (0.04344 sec/rel)
6312 Special q, 17523 reduction iterations
reports: 1887503623->271103548->242309077->43773595->36821294->33206369
Number of relations with k rational and l algebraic primes for (k,l)=:

Total yield: 467310
0/0 mpqs failures, 304782/140685 vain mpqs
milliseconds total: Sieve 10533648 Sched 0 medsched 1078766
TD 3934825 (Init 102757, MPQS 680210) Sieve-Change 3409347
TD side 0: init/small/medium/large/search: 30648 303007 63861 200504 1081906
sieve: init/small/medium/large/search: 143614 2995559 161753 2238305 418605
TD side 1: init/small/medium/large/search: 25090 254574 66339 193034 1611210
sieve: init/small/medium/large/search: 106542 1833562 172171 2212542 250995
appending spairs.out.T0 to spairs.out
appending spairs.out to test.dat
compressing spairs.out to spairs.save.gz
Found 22103924 relations, 132.2% of the estimated minimum (16720000).
-> msieve -s ..\ggnfs_8845424710899977815163938063336156710467852144650354456276
554838704070938061544223956879363372317220791203448437149670370751897\test.dat -
l ..\ggnfs_884542471089997781516393806333615671046785214465035445627655483870407
0938061544223956879363372317220791203448437149670370751897\test.log -i ..\ggnfs_
88454247108999778151639380633361567104678521446503544562765548387040709380615442
23956879363372317220791203448437149670370751897\test.ini -nf ..\ggnfs_8845424710
89997781516393806333615671046785214465035445627655483870407093806154422395687936
3372317220791203448437149670370751897\test.fb -t 1 -nc1
read 10M relations
-> making sieve job for q = 7450000 in 7450000 .. 7550000 as file test.job.T0
-> Lattice sieving algebraic q from 7450000 to 7550000.
-> gnfs-lasieve4I13e -k -o spairs.out.T0 -v -n0 -a test.job.T0
FBsize 421101+0 (deg 5), 419245+0 (deg 1)
total yield: 467987, q=7550017 (0.04343 sec/rel)
6339 Special q, 17654 reduction iterations
reports: 1893388555->271472886->242619998->43877213->36877792->33259743
Number of relations with k rational and l algebraic primes for (k,l)=:

Total yield: 467987
0/0 mpqs failures, 304727/140325 vain mpqs
milliseconds total: Sieve 10564799 Sched 0 medsched 1086150
TD 3909819 (Init 100856, MPQS 672362) Sieve-Change 3418793
TD side 0: init/small/medium/large/search: 31100 302898 60696 198887 1073686
sieve: init/small/medium/large/search: 147553 3015202 163705 2238352 418620
TD side 1: init/small/medium/large/search: 26311 255289 68040 190772 1599263
sieve: init/small/medium/large/search: 107456 1841160 174392 2210424 247935
appending spairs.out.T0 to spairs.out
appending spairs.out to test.dat
compressing spairs.out to spairs.save.gz
Found 22571911 relations, 135.0% of the estimated minimum (16720000).
-> msieve -s ..\ggnfs_8845424710899977815163938063336156710467852144650354456276
554838704070938061544223956879363372317220791203448437149670370751897\test.dat -
l ..\ggnfs_884542471089997781516393806333615671046785214465035445627655483870407
0938061544223956879363372317220791203448437149670370751897\test.log -i ..\ggnfs_
88454247108999778151639380633361567104678521446503544562765548387040709380615442
23956879363372317220791203448437149670370751897\test.ini -nf ..\ggnfs_8845424710
89997781516393806333615671046785214465035445627655483870407093806154422395687936
3372317220791203448437149670370751897\test.fb -t 1 -nc1
read 10M relations
-> making sieve job for q = 7550000 in 7550000 .. 7650000 as file test.job.T0
-> Lattice sieving algebraic q from 7550000 to 7650000.
-> gnfs-lasieve4I13e -k -o spairs.out.T0 -v -n0 -a test.job.T0
FBsize 421101+0 (deg 5), 419245+0 (deg 1)
total yield: 68705, q=7564871 (0.04599 sec/rel)

Am I too oversieved again? Should I break in and manually perform the -nc# operations? And, if so, at what number of relations?

Or, is is it the bolded text above "read 10M relations" that holds the answer and there isn't enough memory? This machine has only 734M, although I could possibly add more temporarily, if that would do it.

Thanks for any/all comments.

Andi47 · 2011-05-20, 18:47

When you look into your test.job.t0 file: What are the values for lpbr and lpba?

if they are 27, then I'd expect that you need approx. 10-12M relations, so I guess your 22M relations would be very oversieved.

if lpbr/a are 28, then 22M relations should be enough (or almost enough, although I'd expect that you would need ~18-20M relations).

What makes me wonder: First your log says something like "Found 21636614 relations...". Then after msieve is invoked, it says "read 10M relations", but it never says "read 20M relations". Is it possible that msieve crashes somewhere halfway through reading the relations?

EdH · 2011-05-20, 22:27

Quote:

Originally Posted by Andi47

When you look into your test.job.t0 file: What are the values for lpbr and lpba?

if they are 27, then I'd expect that you need approx. 10-12M relations, so I guess your 22M relations would be very oversieved.

if lpbr/a are 28, then 22M relations should be enough (or almost enough, although I'd expect that you would need ~18-20M relations).

What makes me wonder: First your log says something like "Found 21636614 relations...". Then after msieve is invoked, it says "read 10M relations", but it never says "read 20M relations". Is it possible that msieve crashes somewhere halfway through reading the relations?

My lpbr/a are at 28, so maybe it does need more, but then, that means the estimate was way off. I'm letting the winXP machine continue, but I've also copied the directory to another (linux) machine with more memory to see what msieve "thinks" on that one.

I did wonder about the 10M relations (why I bolded it). I'll see what turns up with the totally different OS/machine.

Thanks.

2011-05-04, 13:54	#579
Karl M Johnson Mar 2010 19B₁₆ Posts	I generated that number, so I did know the factors and their sizes I just have no hunch about why this poly doesnt work. My poly did not want to be accepted? Last fiddled with by Karl M Johnson on 2011-05-04 at 13:55 Reason: Yes!

2011-05-20, 18:47	#582
Andi47 Oct 2004 Austria 2×17×73 Posts	When you look into your test.job.t0 file: What are the values for lpbr and lpba? if they are 27, then I'd expect that you need approx. 10-12M relations, so I guess your 22M relations would be very oversieved. if lpbr/a are 28, then 22M relations should be enough (or almost enough, although I'd expect that you would need ~18-20M relations). What makes me wonder: First your log says something like "Found 21636614 relations...". Then after msieve is invoked, it says "read 10M relations", but it never says "read 20M relations". Is it possible that msieve crashes somewhere halfway through reading the relations? Last fiddled with by Andi47 on 2011-05-20 at 18:48

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

2011-04-28, 16:42	#573
warut Dec 2009 89 Posts	Mini-Geek, thanks so much for your detailed solution. It worked perfectly, and I already got the factors.

2011-04-29, 17:31	#574
10metreh Nov 2008 2×3³×43 Posts	Clearly the relations file did get wiped (but the first line which only contains the input number was left), so it was lucky that spairs.save.gz was there. Has anyone ever looked for the source of this bug? It's been around for a while but hasn't been fixed.

2011-05-04, 13:31	#578
Andi_HB Mar 2007 Germany 2³·3·11 Posts	Number: c89 N = 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851 (89 digits) Divisors found: r1=6551232298747279617361 (pp22) r2=5878130080532166726744361 (pp25) r3=751330017694728904140304580860365836886931 (pp42) Version: Msieve v. 1.48 Total time: 0.74 hours. Factorization parameters were as follows: n: 28932964375472408051886765779259409234855451658876113961668576291342049987794596910585851 Y0: -2215905079382191980526 Y1: 218821283789 c0: -34021240132395802295145885 c1: 57303669967062965034 c2: -102496079340637 c3: 197954728 c4: 1200 skew: 564611.13 type: gnfs Factor base limits: 600000/600000 Large primes per side: 3 Large prime bits: 25/25 Sieved algebraic special-q in [0, 0) Total raw relations: 1622824 Relations: 87620 relations Pruned matrix : 61424 x 61651 Polynomial selection time: 0.11 hours. Total sieving time: 0.60 hours. Total relation processing time: 0.01 hours. Matrix solve time: 0.01 hours. time per square root: 0.02 hours. Prototype def-par.txt line would be: gnfs,88,4,56,1500,0.0006,0.3,200,15,10000,500,600000,600000,25,25,43,43,2.2,2.2,10000 total time: 0.74 hours. x86 Family 6 Model 23 Stepping 6, GenuineIntel Windows-Vista-6.0.6002-SP2 processors: 2, speed: 2.09GHz factmsieve.py works fine for me.

2011-05-04, 14:06	#580
Karl M Johnson Mar 2010 3×137 Posts	False alarm! I've updated to newer GNFS binaries from Jeff's website(ty!) and it worked.