fun with snfs

[masser]

We have 1 candidate in our dat file with n < 200. If anybody wants to try to factor them, please post here so we don't have duplicate efforts occurring.

325846*5^159-1 done: p54*p63 (michaf)
322498*5^163-1 done: p47*p74 (michaf)
177742*5^165-1 done: p59*p63 (konrad127123)
146756*5^172-1 done: p58*p68 (konrad127123)
313126*5^183-1 done: p45*p89 (michaf)
   254*5^186-1 done: p57*p77 (michaf)
146264*5^194-1 done: p56*p85 (michaf)

37714*5^172+1 done: p53*p73 (michaf)
51208*5^176+1 done: p44*p85 (konrad127123)
71098*5^176+1 done: p47*p82 (konrad127123)
24032*5^181+1 reserved      (michaf)
81556*5^184+1 done: p47*p74 (michaf)

Here is the list of all candidates in our dat file with n < 400.

Reservations beyond 200:
53546*5^200-1: konrad127123

[michaf]

doing 37714*5^172+1 at this moment

[michaf]

37714*5^172+1 done:

Number: 37714_5_172p1
N=63000405172760666624090120201344367236022709460176129121835319112085796466367896466811981959210697823436930775642395019531251
( 125 digits)
SNFS difficulty: 124 digits.
Divisors found:
r1=14465582032370667658227372663294106255168415715560083 (pp53)
r2=4355193246409315121729483588897346062978427046592466831662252772288990497 (pp73)
Version: GGNFS-0.77.1-20060513-athlon-xp
Total time: 4.63 hours.

Taking 325846*5^159-1

[konrad127123]

I'll have a go at 322498*5^163-1.

[michaf]

A nice p54 in there:

Number: 325846_5_159m1
N=445905761139047210246302333785826183313621321008491365394486007844094594852399349171889753051800653338432312011718749
( 117 digits)
SNFS difficulty: 117 digits.
Divisors found:
r1=946950638415393627493165185410649986962675544483131457 (pp54)
r2=470885960735203795153789083353972970130329307107530121167440157 (pp63)
Version: GGNFS-0.77.1-20060513-athlon-xp
Total time: 2.57 hours.

Reserving 146264*5^194-1

[mdettweiler]

Where would I find a copy of SNFS to possibly try factoring one of these? Or, would the number field sieve (not the quadratic sieve) included with msieve do fine?

[michaf]

The numbers are still fine for msieve.Ggnfs is a way quicker with the sieving.
(With gnfs the flipover is around 100 digits for my computer, never actually tested that with snfs).

You can check for ggnfs at http://tech.groups.yahoo.com/group/ggnfs/

msieve is obtainable at http://www.boo.net/~jasonp/qs.html

[mdettweiler]

Originally Posted by michaf

The numbers are still fine for msieve.Ggnfs is a way quicker with the sieving.
(With gnfs the flipover is around 100 digits for my computer, never actually tested that with snfs).

You can check for ggnfs at http://tech.groups.yahoo.com/group/ggnfs/

msieve is obtainable at http://www.boo.net/~jasonp/qs.html

Thanks--actually, I already have a copy of the latest version of msieve. I can't quite seem to find where to download ggnfs on the page you listed, though.

Also, how would I go about setting up ggnfs for use with these types of numbers? I've heard it's quite complex and confusing.

[michaf]

Oh, my apologies,

the files can be gotten from
http://sourceforge.net/projects/ggnfs/

It's not very easy to set up, but once you are there, the factlat script has most of the work done for you.

Below are the results of my latest snfs-number, the .poly file needs to contain:

n: ....
upto
Y1: ....

Number: 146264_5_194m
N=582529988224692499618380406247741498832443291651732985315777101149184326567264847130450243590182000941180007203001878224313259124755859374999
( 141 digits)
SNFS difficulty: 141 digits.
Divisors found:
r1=97356790107191842626782568435872836358484589585664856887 (pp56)
r2=5983455160994060256472046195943542849302859922603898311097732575706621446100614038177 (pp85)
Version: GGNFS-0.77.1-20060513-athlon-xp
Total time: 13.57 hours.
Scaled time: 19.43 units (timescale=1.432).
Factorization parameters were as follows:
n: 582529988224692499618380406247741498832443291651732985315777101149184326567264847130450243590182000941180007203001878224313259124755859374999
type: snfs
skew: 0.12786936592
c5: 146264
c0: -5
Y0: -1818989403545856475830078125
Y1: 1
Name: 146264*5^194-1Factor base limits: 1300000/1300000
Large primes per side: 3
Large prime bits: 26/26
Sieved special-q in [650000, 2450001)
Relations: rels:2815184, finalFF:248289
Initial matrix: 200651 x 248289 with sparse part having weight 27234076.
Pruned matrix : 195350 x 196417 with weight 17653842.
Total sieving time: 12.80 hours.
Total relation processing time: 0.11 hours.
Matrix solve time: 0.58 hours.
Time per square root: 0.08 hours.
Prototype def-par.txt line would be:
snfs,141,5,0,0,0,0,0,0,0,0,1300000,1300000,26,26,45,45,2.3,2.3,100000
total time: 13.57 hours.

In short, this is how I got there:
146264*5^194-1
I wanted a degree 5 polynomial for this size numbers:
5*146264*5^194-1 = 146264*5^195-5
now, 146264 is c5 (c5 because it's a degree 5 polynomial
-5 is c0
Y0: - 5^(195/5)
Y1: 1
(I'm still confused about which one needs to be negative, but ggnfs seems to prefer Y1 positive :>)
skew: (c0/c5)^(1/5)

On this forum, and on the ggnfs mailinglist a lot of info can be found on how and what, but the best thing to learn from, is from making errors.

[xilman]

Originally Posted by michaf

On this forum, and on the ggnfs mailinglist a lot of info can be found on how and what, but the best thing to learn from, is from making errors.

Correction: making errors, thinking about the error messages and attempting to work out what went wrong before even thinking of asking for assistance.

If you can show you've made an honest attempt to correct your errors and are still stuck a number of people here will attempt to help you, even (especially) those who don't suffer fools gladly.

Paul

[mdettweiler]

Originally Posted by michaf

Oh, my apologies,

the files can be gotten from
http://sourceforge.net/projects/ggnfs/

It's not very easy to set up, but once you are there, the factlat script has most of the work done for you.

Below are the results of my latest snfs-number, the .poly file needs to contain:

n: ....
upto
Y1: ....



In short, this is how I got there:
146264*5^194-1
I wanted a degree 5 polynomial for this size numbers:
5*146264*5^194-1 = 146264*5^195-5
now, 146264 is c5 (c5 because it's a degree 5 polynomial
-5 is c0
Y0: - 5^(195/5)
Y1: 1
(I'm still confused about which one needs to be negative, but ggnfs seems to prefer Y1 positive :>)
skew: (c0/c5)^(1/5)

On this forum, and on the ggnfs mailinglist a lot of info can be found on how and what, but the best thing to learn from, is from making errors.

Whew. Looks tricky. I think I'll stick with the msieve number field sieve for now, though I'll keep your instructions in mind in case I try it out later--thanks!