Questions about GGNFS

[ValerieVonck]

Hi group,

I have been following the discussions here & at the yahoo group for several moths and so I decided to do a small factorization of my own with a C97 already factored with Msieve.

First question: How long should polyselect run? May I stop it beforehand?

Here is the input file of wich the factorization is to be based:

n: 6473505215178210198448635234580512345563700196916507763953780507168677982174813186065451228191421
name: C97
deg: 5
bf: best.poly
maxs1: 58
maxskew: 1500
enum: 8
e0: 1
e1: 1000000000
cutoff: 1.5e-3
examinefrac: 0.25
j0: 220
j1: 15

# type,digits,deg,maxs1,maxskew,goodScore,efrac,j0,j1,eStepSize, 
#       maxTime,rlim,alim,lpbr,lpba,mfbr,mfba,rlambda,alambda,qintsize

#gnfs,100

So after a while (1+ hour) I ended it.
It produced the following best.poly file & all.poly file:

name: C97
n:  6473505215178210198448635234580512345563700196916507763953780507168677982174813186065451228191421
m:  729025966006600964
deg: 5
c5: 31435800
c4: 1595602934
c3: -35326910305229
c2: 58973480284143409
c1: -287043566529644939
c0: -46816359669162186215
skew: 895.848
type: gnfs
# These parameters should be manually set:
rlim: 1800000
alim: 1800000
lpbr: 26
lpba: 26
mfbr: 48
mfba: 48
rlambda: 2.5
alambda: 2.5
qintsize: 100000
q0: 1800000

Then I proceded to sieving step (from the pdf file)
The siever produced about 580K lines in 60M file:

gnfs-lasieve4I12e -k -o spairs.out -v -a best.poly

Next step (following the pdf from the Yahoo! group) makefb

C:\...\ggnfs>makefb.exe -of c97.fb -rl 1800000 -al 1800000 -lpbr 26 -lpba 29 -3p -if best.poly
Making factor base...Generating AFB with norms upto 1800000...
Making algebraic factor base.
Checking p=1583539...(total=120000)
Elapsed time: 7 seconds.
Factor base sucessfully created.

C:\....\ggnfs>

Next step is procrels

procrels -fb snfs.fb -newrel spairs.out -maxrelsinff 40

This produced rels.bin.0

Next step matbuild

C:\...\ggnfs>matbuild -fb c97.fb -prel rels.bin

It stated that it need much more relations!

.......
mkLT: There appear to be no large primes in the specified range.
* There are now 6288 full relations.
After keepFulls(), R->numFields = 6288
More columns needed (current = 6288, min = 270287)

Can anyone pleae give me a kind of documented manual on how to work with ggnfs (no perl script please)
and point out what I have done wrong?

And how to correct it?

Thank you.

Ps. Sorry for the long post
PPs. I am not very good @ maths

[smh]

Originally Posted by CedricVonck

First question: How long should polyselect run? May I stop it beforehand?

Don't use polyselect. There's a much better poly selection tool in the latest versions. It can be found under ..\src\pol5

Originally Posted by CedricVonck

Next step matbuild

C:\...\ggnfs>matbuild -fb c97.fb -prel rels.bin

It stated that it need much more relations!

.......
mkLT: There appear to be no large primes in the specified range.
* There are now 6288 full relations.
After keepFulls(), R->numFields = 6288
More columns needed (current = 6288, min = 270287)

Can anyone pleae give me a kind of documented manual on how to work with ggnfs (no perl script please)
and point out what I have done wrong?

Sorry, no manual.

But what makes you think you've done something wrong? You just need (a lot) more sieving.

IIRC even a c97 takes a long time with polynomials generated by polyselect.

With the current polyselect tool a c97 takes about as long as (some older version of) msieve on my P4

[ValerieVonck]

Ok tommorow I will play a bit with pol5m0n (?) & pol5opt (included in tha package)

But my question remains, how lonng it usual take to select a decent polynomial?

Will the program end itself when it finds it most perfect one?

How do I tell the siever to sieve much more?

BTW, I use the supplied def-par.txt from the Yahoo! group.

Thank you.

[R.D. Silverman]

Originally Posted by CedricVonck

Ok tommorow I will play a bit with pol5m0n (?) & pol5opt (included in tha package)

But my question remains, how lonng it usual take to select a decent polynomial?

Will the program end itself when it finds it most perfect one?

How do I tell the siever to sieve much more?

BTW, I use the supplied def-par.txt from the Yahoo! group.

Thank you.

You should spend perhaps 5-10% of the total CPU effort
on finding a good polynomial. It does pay off.

There is no such thing as a 'perfect' polynomial.

Perhaps if you read some papers on the algorithm, you might
understand it better?

[Kosmaj]

Originally Posted by CedricVonck

How do I tell the siever to sieve much more?

In the best.poly file set, for example
qintsize: 300000
q0: 1900000

Then run lasieve again, followed by procrels and mathbuild. If even more relations are required then repeat the {lasieve, procrels, mathbuild } sequence setting always:
q0 = q0 + qintsize
and qintsize to a certain value between 50000 and 300000 (for this particular case) until you have enough relations.

The supplied perl script is doing exactly the same thing automatically.

[ValerieVonck]

Originally Posted by R.D. Silverman

You should spend perhaps 5-10% of the total CPU effort
on finding a good polynomial. It does pay off.

There is no such thing as a 'perfect' polynomial.

Perhaps if you read some papers on the algorithm, you might
understand it better?

Mr. Silverman,

I have read the "bob.pdf" & the ggnfs manual from the Yahoo! group and also about every topic here & over @ Yahoo!.

But everything about NFS is way beyond my mathematical capabilities.
What I need I some one who explains to me with clear & in low level terms how a factorization is done.

I am only want to learn something new. I know its gonna take some time.
But I know I will arrive there!!

[ValerieVonck]

Originally Posted by Kosmaj

In the best.poly file set, for example
qintsize: 300000
q0: 1900000

Then run lasieve again, followed by procrels and mathbuild. If even more relations are required then repeat the {lasieve, procrels, mathbuild } sequence setting always:
q0 = q0 + qintsize
and qintsize to a certain value between 50000 and 300000 (for this particular case) until you have enough relations.

The supplied perl script is doing exactly the same thing automatically.

Ok will do!

[VJS]

Yes it would certainly be nice to have a step1 step2 step3 etc for the noobie, I learn through example as well.

I tried doing a ggnfs this weekend, using the perlscript... had a logical disk error and lost everything, not sure if the c108 factored or not I'll have to redo obviously.

-------------------------

Regardless does anyone have a direct link to the latest and greatest factlat.pl?
I'm starting from scratch (again) ...
This time I'm starting with the athlon snapshot as opposed to a compile, weird I'm now getting a low 0.013 sec/rel as opposed to 0.018 sec/rel from the c108. Both times I used polyselect.

WHat is the command line for pol51m0b anyways? is it the same

poly51m0b -if number.n

where
number.n contains

name: name
n: the number
deg: 4-5
type: gnfs

I believe the above is the absolute min to start with... other parameters can be entered at this time using def-par.txt?

Anyways this is the .poly files I started an older version of factlat.pl with

name: c109a
n: 3161408079236972418648762395003025398567069728621718592957270452731414521227196914294390930687994503364643777
m: 192672626643261667764
deg: 5
c5: 11906400
c4: 7001524203
c3: -18725523571157238
c2: -293653309905877447
c1: 718961681593150391157
c0: 41684310800435063945965
skew: 327.387
type: gnfs
# adj. I(F,S) = 52.438
# E(F1,F2) = 1.910665e-004
# GGNFS version 0.77.1-20050930-athlon polyselect.
# Options were:
# lcd=1, enumLCD=0, maxS1=61.00000000, seed=1132078922.
# maxskew=2000.0
# These parameters should be manually set:
rlim:
alim:
lpbr:
lpba:
mfbr:
mfba:
rlambda:
alambda:
qintsize:

[VJS]

Maybe an easier question to answer...

Can anyone give a step by step for creating a poly from pol51 and time investment.

According to Dr.Silverman and smh I'm now wondering if I spent enough time running polyselect (2 hours for a c109) or if I should just start again using pol51.

FYI: I'm getting 0.013 sec/rel with a deg:5 on a c109 with a 2.3G barton chip.

[ValerieVonck]

VJS,

You have to put confugre poly5opt with options from the following file.
For the rest I do not know how to run it.

I don't know where to get the latest perl script.

Regards

[VJS]

Thanks,

In my haste to get things working again I missed the two different def-par files. This explains the a5 error...

I'm pretty sure the simplest non-efficient way of getting this started is as follows...

create one file in notepad with the following lines

name: "some simple name c109 etc"
n: the decimal number

example:

name: c109
n: 3161408079236972418648762395003025398567069728621718592957270452731414521227196914294390930687994503364643777

save it as c109.n not c109.n.txt or anthing else.

Then run the perlscript

factlat.pl -if c109.n

It worked!!! Efficently probably not if your Dr. Silverman. Does it work if you don't know where to start, Yes... I think. Personally I'd rather create my own poly file but this way is easy.

I'll attach the perscript I'm using hopefully everything is working now.