Running GGNFS - Page 26

unconnected · 2009-07-21, 14:48

Don't know why there are so many duplicates.
I restart again with another polynomial (takes ~1hour to generate) and it works ok this time.

axn · 2009-07-21, 15:00

Quote:

Originally Posted by 10metreh

I notice it is p51*p52 in the database. Unconnected, was that you or someone else?

that'd be me.

wreck · 2009-08-08, 13:22

I want to sieve relations using msieve.exe for factoring 136^73-1,but it seems too slow,after about 52 hours I collect 7.37 million relations,the msieve.fb is something like

Code:

N 4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
SKEW 1.00
R0  25178139429992821256026738130944
R1 -1
A0 -289
A1  0
A2  0
A3  0
A4  0
A5  16

FRNUM 1620337
FRMAX 25928569
FANUM 1620387
FAMAX 25928569
SRLPMAX 536870912
SALPMAX 536870912
SLINE 58571429

2 0
3 1
5 4
7 5
11 3
...

Then I try to use gnfs-lasieve4I14e to sieve relations,but I didn't install ggnfs this time,the c151.poly is

Code:

n: 4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
c5: 16
c0: -289
Y1: -1
Y0: 25178139429992821256026738130944
skew: 1.78
type: snfs
rlim: 50000000
alim: 50000000
lpbr: 31
lpba: 31
rlambda: 2.6
alambda: 2.6
mfbr: 62
mfba: 62

Since phi.exe doesn't create the parameter of rlim,alim,etc.
I copy them from some of the c16x's from mersenneforum.
Now I have collect about 42m relations,but it still say not enough relations,
is there any problem from me?I notice that the latest team sieving of c150's rlim is 20000000,is that matter?

And here is some log:

Code:

Sat Aug 08 19:29:19 2009  Msieve v. 1.41
Sat Aug 08 19:29:19 2009  random seeds: c3300900 04d60516
Sat Aug 08 19:29:19 2009  factoring 4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789 (151 digits)
Sat Aug 08 19:29:21 2009  searching for 15-digit factors
Sat Aug 08 19:29:25 2009  commencing number field sieve (151-digit input)
Sat Aug 08 19:29:25 2009  R0:  25178139429992821256026738130944
Sat Aug 08 19:29:25 2009  R1: -1
Sat Aug 08 19:29:25 2009  A0: -289
Sat Aug 08 19:29:25 2009  A1:  0
Sat Aug 08 19:29:25 2009  A2:  0
Sat Aug 08 19:29:25 2009  A3:  0
Sat Aug 08 19:29:25 2009  A4:  0
Sat Aug 08 19:29:25 2009  A5:  16
Sat Aug 08 19:29:25 2009  skew 1.00, size 3.954213e-011, alpha 0.564133, combined = 7.005650e-010
Sat Aug 08 19:29:25 2009  
Sat Aug 08 19:29:25 2009  commencing relation filtering
Sat Aug 08 19:29:25 2009  commencing duplicate removal, pass 1
Sat Aug 08 19:29:26 2009  error -9 reading relation 2933
Sat Aug 08 19:34:22 2009  error -15 reading relation 12759290
Sat Aug 08 19:35:53 2009  error -9 reading relation 18263192
Sat Aug 08 19:38:19 2009  error -11 reading relation 26446399
Sat Aug 08 19:38:54 2009  error -15 reading relation 27194298
Sat Aug 08 19:40:44 2009  error -5 reading relation 30206080
Sat Aug 08 19:42:10 2009  error -15 reading relation 35569001
Sat Aug 08 19:42:19 2009  error -15 reading relation 36140517
Sat Aug 08 19:43:59 2009  found 3107245 hash collisions in 42180439 relations
Sat Aug 08 19:45:48 2009  added 115912 free relations
Sat Aug 08 19:45:48 2009  commencing duplicate removal, pass 2
Sat Aug 08 19:49:12 2009  found 158947 duplicates and 42137404 unique relations
Sat Aug 08 19:49:12 2009  memory use: 157.2 MB
Sat Aug 08 19:49:12 2009  reading rational ideals above 20119552
Sat Aug 08 19:49:12 2009  reading algebraic ideals above 20119552
Sat Aug 08 19:49:12 2009  commencing singleton removal, pass 1
Sat Aug 08 20:02:37 2009  relations with 0 large ideals: 464138
Sat Aug 08 20:02:37 2009  relations with 1 large ideals: 2919405
Sat Aug 08 20:02:37 2009  relations with 2 large ideals: 8887253
Sat Aug 08 20:02:37 2009  relations with 3 large ideals: 13933711
Sat Aug 08 20:02:37 2009  relations with 4 large ideals: 11082658
Sat Aug 08 20:02:37 2009  relations with 5 large ideals: 3632105
Sat Aug 08 20:02:37 2009  relations with 6 large ideals: 1190231
Sat Aug 08 20:02:37 2009  relations with 7+ large ideals: 27903
Sat Aug 08 20:02:37 2009  42137404 relations and about 51431473 large ideals
Sat Aug 08 20:02:37 2009  commencing singleton removal, pass 2
Sat Aug 08 20:17:44 2009  found 22656165 singletons
Sat Aug 08 20:17:44 2009  current dataset: 19481239 relations and about 20271629 large ideals
Sat Aug 08 20:17:44 2009  commencing singleton removal, pass 3
Sat Aug 08 20:25:41 2009  relations with 0 large ideals: 464138
Sat Aug 08 20:25:41 2009  relations with 1 large ideals: 2298762
Sat Aug 08 20:25:41 2009  relations with 2 large ideals: 5368957
Sat Aug 08 20:25:41 2009  relations with 3 large ideals: 6286543
Sat Aug 08 20:25:41 2009  relations with 4 large ideals: 3692526
Sat Aug 08 20:25:41 2009  relations with 5 large ideals: 924334
Sat Aug 08 20:25:41 2009  relations with 6 large ideals: 440798
Sat Aug 08 20:25:41 2009  relations with 7+ large ideals: 5181
Sat Aug 08 20:25:41 2009  19481239 relations and about 24798160 large ideals
Sat Aug 08 20:25:41 2009  commencing singleton removal, pass 4
Sat Aug 08 20:33:14 2009  found 11220281 singletons
Sat Aug 08 20:33:14 2009  current dataset: 8260958 relations and about 9094138 large ideals
Sat Aug 08 20:33:14 2009  commencing singleton removal, pass 5
Sat Aug 08 20:37:05 2009  found 3879831 singletons
Sat Aug 08 20:37:05 2009  current dataset: 4381127 relations and about 4153799 large ideals
Sat Aug 08 20:37:05 2009  commencing singleton removal, pass 6
Sat Aug 08 20:40:20 2009  found 1686492 singletons
Sat Aug 08 20:40:20 2009  current dataset: 2694635 relations and about 2110375 large ideals
Sat Aug 08 20:40:20 2009  commencing singleton removal, pass 7
Sat Aug 08 20:43:48 2009  found 777454 singletons
Sat Aug 08 20:43:48 2009  current dataset: 1917181 relations and about 1216008 large ideals
Sat Aug 08 20:43:48 2009  commencing singleton removal, pass 8
Sat Aug 08 20:46:47 2009  found 356169 singletons
Sat Aug 08 20:46:47 2009  current dataset: 1561012 relations and about 827143 large ideals
Sat Aug 08 20:46:47 2009  commencing singleton removal, final pass
Sat Aug 08 20:49:18 2009  memory use: 18.7 MB
Sat Aug 08 20:49:18 2009  commencing in-memory singleton removal
Sat Aug 08 20:49:18 2009  begin with 1561012 relations and 890772 unique ideals
Sat Aug 08 20:49:18 2009  reduce to 1089274 relations and 387294 ideals in 11 passes
Sat Aug 08 20:49:18 2009  max relations containing the same ideal: 92
Sat Aug 08 20:49:19 2009  reading rational ideals above 720000
Sat Aug 08 20:49:19 2009  reading algebraic ideals above 720000
Sat Aug 08 20:49:19 2009  commencing singleton removal, final pass
Sat Aug 08 20:51:14 2009  keeping 2865849 ideals with weight <= 20, new excess is 124855
Sat Aug 08 20:51:16 2009  memory use: 66.6 MB
Sat Aug 08 20:51:16 2009  commencing in-memory singleton removal
Sat Aug 08 20:51:16 2009  begin with 1205256 relations and 2865849 unique ideals
Sat Aug 08 20:51:16 2009  reduce to 3638 relations and 22 ideals in 6 passes
Sat Aug 08 20:51:16 2009  max relations containing the same ideal: 2
Sat Aug 08 20:51:16 2009  filtering wants 423645 more relations
Sat Aug 08 20:51:16 2009  elapsed time 01:21:57

It takes me about 50 hours to sieve 36M relations using gnfs-lasieve4I14e.

10metreh · 2009-08-08, 13:31

Quote:

Originally Posted by wreck

I want to sieve relations using msieve.exe for factoring 136^73-1,but it seems too slow,after about 52 hours I collect 7.37 million relations,the msieve.fb is something like
<snip>
Then I try to use gnfs-lasieve4I14e to sieve relations,but I didn't install ggnfs this time,the c151.poly is
<snip>
Since phi.exe doesn't create the parameter of rlim,alim,etc.
I copy them from some of the c16x's from mersenneforum.
Now I have collect about 42m relations,but it still say not enough relations,
is there any problem from me?I notice that the latest team sieving of c150's rlim is 20000000,is that matter?

And here is some log:
<snip>
It takes me about 50 hours to sieve 36M relations using gnfs-lasieve4I14e.

Have a go with this poly file:

Code:

n: 4731588299358581392206972814837279876590647809661957400062456689033346472753376261112083650744829144188189893004499029020127140225271052682382194515789
c5: 16
c0: -289
Y1: -1
Y0: 25178139429992821256026738130944
skew: 1
type: snfs
rlim: 4000000
alim: 4000000
lpbr: 27
lpba: 27
mfbr: 54
mfba: 54
rlambda: 2.3
alambda: 2.3

SFNS parameters and GNFS parameters are different for the same size number. The lpbr and lpba values are the main influence on the number of relations: increasing them by 1 will roughly double the number of relations you need.

Andi47 · 2009-08-22, 11:26

I am trying to factor 7^234+5^234 with SNFS (number not yet reserved, just doing some test sieving before I decide to do it), using this poly:

Code:

n: 59637465959020280912357567367209060262303555900277744434999055980903367137477583253307595639414569102520890416866614073
c5: 5
c0: 7
Y1: 710542735760100185871124267578125
Y0: -5243338316756303634461458718861951455543
skew: 1
rlim: 850000
alim: 850000
lpbr: 25
lpba: 25
mfbr: 44
mfba: 44
rlambda: 2.3
alambda: 2.3
type: snfs

gnfs-lasieve4I13e -a 7_5_234+.poly -o test2.out -f 850000 -c 500 gives:

total yield: 10, q=850529 (5.18130 sec/rel)

This rate looks incredibily low to me (I guess even MPQS would be faster

) - what am I doing wrong?

jasonp · 2009-08-22, 12:19

SNFS with 200-digit difficulty needs factor base bounds that are much larger than 850k. As a wild guess, try somewhere between 10M and 15M. You will also need 27 or 28-bit large primes, and a mfbr/mfba of 54-56.

Others here can probably suggest better parameters.

Andi47 · 2009-08-22, 12:37

Quote:

Originally Posted by jasonp

200-digit difficulty

Strange - the Homogeneous cunningham reservation page says that it has difficulty 132...

Is there some trick to reduce the difficulty to 132?

jasonp · 2009-08-22, 12:58

My estimate of the difficulty is (number of digits in R0) * (degree of algebraic poly)

The difficulty is close to a 132-digit GNFS...

Andi47 · 2009-08-22, 13:04

Quote:

Originally Posted by jasonp

My estimate of the difficulty is (number of digits in R0) * (degree of algebraic poly)

The difficulty is close to a 132-digit GNFS...

Aaaah, that's what the page means with "difficulty 131.9"...

Batalov · 2009-08-22, 20:26

Reduce using it being a sum of two cubes.

For this particular difficulty, stay with a bi-quadratic, but above ~160-170, use a sextic (a "tri"-quadratic, take the best cube roots; for some bases, like 8, you get better polynomials than for some others)

For numbers with exponents divisible by 15 or 21, use more algebraic reduction (hint: you will arrive at polynomials that look like {1,1,-4,-4,1} and {1,1,8,8,-6,-6,1}); I've left some of these as an exercise.

Andi47 · 2009-08-23, 05:54

Quote:

Originally Posted by Batalov

Reduce using it being a sum of two cubes.

For this particular difficulty, stay with a bi-quadratic, but above ~160-170, use a sextic (a "tri"-quadratic, take the best cube roots; for some bases, like 8, you get better polynomials than for some others)

For numbers with exponents divisible by 15 or 21, use more algebraic reduction (hint: you will arrive at polynomials that look like {1,1,-4,-4,1} and {1,1,8,8,-6,-6,1}); I've left some of these as an exercise.

So I get:
7^234 + 5^234 = (7^78)^3 + (5^78)^3
= (7^78 + 5^78) * ((7^78)^2 + (7^78)*(5^78) + (5^78)^2) = C * D

Factoring the second algebraic factor D

be A = 7^39 and B = 5^39

so:
D = A^4 + A^2*B^2 + B^4, and

n: <D divided by the small stuff>
c4 = 1
c2 = 1
c0 = 1
Y0 = 7^39
Y1 = -5^39

but with

Code:

skew: 1
rlim: 850000
alim: 850000
lpbr: 25
lpba: 25
mfbr: 44
mfba: 44
rlambda: 2.3
alambda: 2.3
type: snfs

...sieving with 13e from 850k to 850500 still gives

total yield: 0, q=850529 (1.#INF0 sec/rel)

Still behaving like difficulty 200? The algebraic factor should now be difficulty 132, or did I do something wrong?

Edit: whoops, seems I am running into the badshed bug...? (I just see that I have lots of badshed.(something) files in my folder)

2009-08-22, 11:26	#280
Andi47 Oct 2004 Austria 2×17×73 Posts	What am I doing wrong? I am trying to factor 7^234+5^234 with SNFS (number not yet reserved, just doing some test sieving before I decide to do it), using this poly: Code: n: 59637465959020280912357567367209060262303555900277744434999055980903367137477583253307595639414569102520890416866614073 c5: 5 c0: 7 Y1: 710542735760100185871124267578125 Y0: -5243338316756303634461458718861951455543 skew: 1 rlim: 850000 alim: 850000 lpbr: 25 lpba: 25 mfbr: 44 mfba: 44 rlambda: 2.3 alambda: 2.3 type: snfs gnfs-lasieve4I13e -a 7_5_234+.poly -o test2.out -f 850000 -c 500 gives: total yield: 10, q=850529 (5.18130 sec/rel) This rate looks incredibily low to me (I guess even MPQS would be faster ) - what am I doing wrong?

2009-08-22, 12:19	#281
jasonp Tribal Bullet Oct 2004 DD7₁₆ Posts	SNFS with 200-digit difficulty needs factor base bounds that are much larger than 850k. As a wild guess, try somewhere between 10M and 15M. You will also need 27 or 28-bit large primes, and a mfbr/mfba of 54-56. Others here can probably suggest better parameters. Last fiddled with by jasonp on 2009-08-22 at 13:00

2009-08-22, 12:58	#283
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	My estimate of the difficulty is (number of digits in R0) * (degree of algebraic poly) The difficulty is close to a 132-digit GNFS... Last fiddled with by jasonp on 2009-08-22 at 13:01

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Installation of GGNFS	LegionMammal978	Msieve	17	2017-01-20 19:49
Running other programs while running Prime95.	Neimanator	PrimeNet	14	2013-08-10 20:15
Error running GGNFS+msieve+factmsieve.py	D. B. Staple	Factoring	6	2011-06-12 22:23
GGNFS or something better?	Zeta-Flux	Factoring	1	2007-08-07 22:40
ggnfs	ATH	Factoring	3	2006-08-12 22:50

2009-07-21, 14:48	#276
unconnected May 2009 Russia, Moscow 2,593 Posts	Don't know why there are so many duplicates. I restart again with another polynomial (takes ~1hour to generate) and it works ok this time.

2009-08-22, 20:26	#285
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22420₈ Posts	Reduce using it being a sum of two cubes. For this particular difficulty, stay with a bi-quadratic, but above ~160-170, use a sextic (a "tri"-quadratic, take the best cube roots; for some bases, like 8, you get better polynomials than for some others) For numbers with exponents divisible by 15 or 21, use more algebraic reduction (hint: you will arrive at polynomials that look like {1,1,-4,-4,1} and {1,1,8,8,-6,-6,1}); I've left some of these as an exercise.