GGNFS questions and Answers

[xilman]

Originally Posted by CedricVonck

Hi group,

I am doing my first SNFS factorization.
But I have a question about "degree".

I run the program phi.exe & I choose a polynomial of the 6th degree.
But I can also choose a 4 & 5 degree one!

What is better to choose? a 6 or a 4 degree poly?
Sorry about the st00pid question .... but I try understand it...

Best Regards
C.

Not stupid at all.

The best degree depends on (at least) two things. First is the size of the number being factored. The bigger the number, the larger the degree should be. Roughly speaking, SNFS on 150 digit numbers is probably best with degree 5, but on 200-digit numbers you would probably find degree 6 is better.

Secondly, one degree polynomial may have much smaller coefficients than another. For instance, factoring 11^192+1 you would use a sextic polynomial x^6+1 with root 11^32 rather than either quintic 121*x^5+1 or x^5+1331, either of which has much larger coefficients.

A better measure of quality is the value of the norms of the polynomials at a "typical" point in the sieving rectangle. That is, evaluate the norm at various places and choose the polynomial pair which gives the most nearly equal values for each polynomial norm.

The best way to decide which to choose is to choose all the (plausible) alternatives and perform a little trial sieving to see which gives the beset yield in terms of relations per second. Sometimes, there is only one plausible polynomial, sometimes there are several.

Like a number of things with NFS, polynomial selection is a skill which improves with practice.


Paul

[ValerieVonck]

Wow!!!!! Thanks all for the very friendly answers

Later, I will post my number ,after I have checked it that I did the right one

n: 28203019957754481116944031777820050929945196040491060153342647391345165902581480685618817581940893882839162211584379479097464035839
# Difficulty: 142.24, skewness: 1.00, alpha: 3.10, cost: 5.43773e+014
# est. time: 0.26 GHz days (not accurate yet!) 
skew: 1.000
c6: 1
c5: 1
c4: -5
c3: -4
c2: 6
c1: 3
c0: -1
Y1: -713406215047
Y0: 508948427667686409212210
m: 3841421897930868550415276352096706235148627581292670291673526611085760689977750334119890398174235036333356106961993740360309887446
type: snfs

SNFS difficulty is 143 (as mentioned @ oddPerfect.org)
But when I run GGNFS, I get a difficulty of 777

I am going to try a 5th degree poly....

Is this the right choice?

[ValerieVonck]

Nope with a 5th degree poly:

C:\Documents and Settings\Cedric Vonck\Bureaublad\phi>phi -ggnfs -deg5 13 713406
215047 2820301995775448111694403177782005092994519604049106015334264739134516590
2581480685618817581940893882839162211584379479097464035839
n: 28203019957754481116944031777820050929945196040491060153342647391345165902581
480685618817581940893882839162211584379479097464035839
# Difficulty: 177.80, skewness: 55123.24, alpha: 0.00, cost: 1.89843e+016
# est. time: 9.04 GHz days (not accurate yet!)
skew: 55123.242
c5: 1
c0: -508948427667686409212209
Y1: -1
Y0: 363086971436526015103404415711908823
m: 363086971436526015103404415711908823
type: snfs

[ValerieVonck]

Originally Posted by akruppa

Depends on how large your number is, that is, on the SNFS difficulty. Grossly simplified, for difficulty ~100, degree 4 is optimal, for ~150, degree 5 and for ~240, degree 6. Sometimes the difficulty can be reduced by dividing out algebraic factors. Run phi without -deg4 or -deg6 first and see what difficulty you get. Without a -degx parameter, phi will try to minimise the difficulty by dividing out the largest algebraic factors that can be used.
Then. if your number is very small (difficulty <120) try -deg4, if it is very large (>190) try -deg6. If the difficulty you now get is no (or only marginally) higher than the default one, use -deg4 or -deg6, resp. Otherwise stick with the default.

For composite sizes beginners of SNFS will typically attempt, the default polynomial produced by phi is usually very reasonable.

Alex

Alex,

Without any parameters, I get the 6th degree poly....

[akruppa]

Originally Posted by CedricVonck

Alex,

Without any parameters, I get the 6th degree poly....

Nope, that is fine (so , not !)

The exponent of your number is divisible by 13, so an algebraic factor can be divided out and the rest can be expressed as a degree 6 polynomial. If you force degree 5, the algebraic factor can not be divided out and the difficulty is higher. Phi does not invariably choose degree 5 by default - instead it tries to divide out the largest algebraic factor it can while still being able to express the rest as a degree 4, 5 or 6 polynomial.

But if no useful algebraic factors are present it always chooses degree 5 by default. So if your number has difficulty >190 and no algebraic factors, you may wish to give the -deg6 parameter to get degree 6 instead of 5. This is pretty much the only case where you need to override the default choice.

Alex

[ValerieVonck]

Ok, tommorow I see further

[ValerieVonck]

This morning at 3 o'clock I got the following results:

See attachment...

[ValerieVonck]

continued...

Number: 714060279761
N=28203019957754481116944031777820050929945196040491060153342647391345165902581480685618817581940893882839162211584379479097464035839
  ( 131 digits)
SNFS difficulty: 777 digits.
Divisors found:
Version: GGNFS-0.77.1-20050930-pentium4
Total time: 76.93 hours.
Scaled time: 45.85 units (timescale=0.596).
Factorization parameters were as follows:
n: 28203019957754481116944031777820050929945196040491060153342647391345165902581480685618817581940893882839162211584379479097464035839
# Difficulty: 142.24, skewness: 1.00, alpha: 3.10, cost: 5.43773e+014
# est. time: 0.26 GHz days (not accurate yet!) 
skew: 1.000
c6: 1
c5: 1
c4: -5
c3: -4
c2: 6
c1: 3
c0: -1
Y1: -713406215047
Y0: 508948427667686409212210
m: 3841421897930868550415276352096706235148627581292670291673526611085760689977750334119890398174235036333356106961993740360309887446
type: snfs
Factor base limits: 7400000/7400000
Large primes per side: 3
Large prime bits: 27/27
Sieved special-q in [3700000, 4100001)
Relations: rels:6175518, finalFF:1128872
Initial matrix: 1003597 x 1128872 with sparse part having weight 34683666.
Pruned matrix : 930893 x 935974 with weight 26179621.
Total sieving time: 51.93 hours.
Total relation processing time: 0.20 hours.
Matrix solve time: 24.80 hours.
Time per square root: 0.00 hours.
Prototype def-par.txt line would be:
snfs,777,6,0,0,0,0,0,0,0,0,7400000,7400000,27,27,48,48,2.6,2.6,100000
total time: 76.93 hours.
 --------- CPU info (if available) ----------

May I conclude that this number is correctly factored???

Or can anyone send me a small c112 snfs number wich I can factor in about an hour???

[xilman]

Originally Posted by CedricVonck

continued...

Number: 714060279761
N=28203019957754481116944031777820050929945196040491060153342647391345165902581480685618817581940893882839162211584379479097464035839
  ( 131 digits)
SNFS difficulty: 777 digits.
Divisors found:
Version: GGNFS-0.77.1-20050930-pentium4
Total time: 76.93 hours.
Scaled time: 45.85 units (timescale=0.596).
Factorization parameters were as follows:
n: 28203019957754481116944031777820050929945196040491060153342647391345165902581480685618817581940893882839162211584379479097464035839
# Difficulty: 142.24, skewness: 1.00, alpha: 3.10, cost: 5.43773e+014
# est. time: 0.26 GHz days (not accurate yet!) 
skew: 1.000
c6: 1
c5: 1
c4: -5
c3: -4
c2: 6
c1: 3
c0: -1
Y1: -713406215047
Y0: 508948427667686409212210
m: 3841421897930868550415276352096706235148627581292670291673526611085760689977750334119890398174235036333356106961993740360309887446
type: snfs
Factor base limits: 7400000/7400000
Large primes per side: 3
Large prime bits: 27/27
Sieved special-q in [3700000, 4100001)
Relations: rels:6175518, finalFF:1128872
Initial matrix: 1003597 x 1128872 with sparse part having weight 34683666.
Pruned matrix : 930893 x 935974 with weight 26179621.
Total sieving time: 51.93 hours.
Total relation processing time: 0.20 hours.
Matrix solve time: 24.80 hours.
Time per square root: 0.00 hours.
Prototype def-par.txt line would be:
snfs,777,6,0,0,0,0,0,0,0,0,7400000,7400000,27,27,48,48,2.6,2.6,100000
total time: 76.93 hours.
 --------- CPU info (if available) ----------

May I conclude that this number is correctly factored???

Or can anyone send me a small c112 snfs number wich I can factor in about an hour???

You may conclude that it is correctly factored when two circumstances hold. First, you have exhibited factors and, second, when you have verified that their product is equal to the original number.

Paul

[ValerieVonck]

Paul,

I know but what are the odds that of the factors is 1 !!!??
What does it mean? Can some run a doublecheck on this number?

It is located @ www.oddperfect.org

[akruppa]

For some reason sqrt found only trivial factorisations. This might be a bug, perhaps block-Lanczos produces only trivial dependencies due to duplicate rows or something like this. Maybe Sam (trilliwig) can tell more.

Alex