Running GGNFS
 

[QUOTE=jbristow;119001]Andi - I use the Pentium 4 Windows binaries from the ggnfs sourceforge site to start. That package has a lattice siever (Franke's) and gnfs polynomial selection tools.[/QUOTE]

Do you mean from [URL="http://sourceforge.net/projects/ggnfs"]here[/URL]? I only see a linux version (which also runs in MinGW - if one is better skilled in linux than me) on this site.

Please point out the windows binary to me.

[quote=Andi47;119036]Do you mean from [URL="http://sourceforge.net/projects/ggnfs"]here[/URL]? I only see a linux version (which also runs in MinGW - if one is better skilled in linux than me) on this site.

Please point out the windows binary to me.[/quote]

From that page, click on the Download tab, then click on the ggnfs-snapshots package, then click on ggnfs-0.77.1-20060513-win32-pentium4.exe. Hope this helps.

[QUOTE=jbristow;119042]From that page, click on the Download tab, then click on the ggnfs-snapshots package, then click on ggnfs-0.77.1-20060513-win32-pentium4.exe. Hope this helps.[/QUOTE]

Thanks. I have now downloaded and installed it.
When I have got a number in a file, how do I start poly selection and sieving?

Most simply would be to get the factlat.pl script to work.
That would involve getting perl to run, activePerl is the right thing to go for, I think.

Have fun trying to get it to work!

[QUOTE=michaf;119156]Most simply would be to get the factlat.pl script to work.
That would involve getting perl to run, activePerl is the right thing to go for, I think.

Have fun trying to get it to work![/QUOTE]

Does the factlat.pl script need an already existing polynomial?

I tried typing "factlat.pl inputfile.txt" where inputfile.txt contains a c144 number to factor.
It complains then that it doesn't find specified math lib(s) and falls back to math::bigint::fastcalc.
Then it complains about some integer overflows in hexadecimal numbers in factlat.pl lines 239, 242, 279, 279
and then it complains that it doesn't find the polynomial file.

What am I doing wrong?

If you have a poly, put it in a file called xxx.poly (in proper GGNFS format).

If you want to search for a poly, put a line like the following in a file called xxx.n
[CODE]n: 12345678980111112223344567891[/CODE]

In both cases, start factlat.pl as follows[CODE]factlat.pl xxx[/CODE]

Make sure you have the def-nm-params.txt and def-par.txt files in the directory where your executables are (as defined by $GGNFS_BIN_PATH= ) in factlat.pl.

Also, make sure you have a windows version of cat.exe available for factlat.pl

[QUOTE=smh;119160]If you have a poly, put it in a file called xxx.poly (in proper GGNFS format).

If you want to search for a poly, put a line like the following in a file called xxx.n
[CODE]n: 12345678980111112223344567891[/CODE]

In both cases, start factlat.pl as follows[CODE]factlat.pl xxx[/CODE]

Make sure you have the def-nm-params.txt and def-par.txt files in the directory where your executables are (as defined by $GGNFS_BIN_PATH= ) in factlat.pl.

Also, make sure you have a windows version of cat.exe available for factlat.pl[/QUOTE]

Thanks.

Some more questions:

First: Where do I get the windows version of cat.exe?

Second: When my GGNFS directory is f:\wissenschaft\mathe\ggnfs - am I right to enter it as f:/wissenschaft/mathe/ggnfs into the factlat.pl script?

Third: I am still getting complaints about couldn't load specified math lib(s) and I am now getting "the system couldn't find the specified path" errors during poly selection. Is this because of a mistyped path for $GGNFS_BIN_PATH= in factlat.pl, or because of the still missing cat.exe?

I've kept the paths relative in factlat.pl

My directory structure looks something like this:

..\GGNFS
..\GGNFS\BIN
..\GGNFS\TESTS
..\GGNFS\TESTS\C120

I've put all executables in the BIN directory and the factlat.pl and input files in the c120 directory.

My factlat.pl looks like:

$GGNFS_BIN_PATH="../../bin";
$SYS_BIN_PATH="../../bin";


The first path is for GGNFS executables, the second for system executables (like cat, gzip etc).

I use unix utilities from [url]http://sourceforge.net/projects/unxutils[/url]

[QUOTE=smh;119176]I've kept the paths relative in factlat.pl

My directory structure looks something like this:

..\GGNFS
..\GGNFS\BIN
..\GGNFS\TESTS
..\GGNFS\TESTS\C120

I've put all executables in the BIN directory and the factlat.pl and input files in the c120 directory.

My factlat.pl looks like:

$GGNFS_BIN_PATH="../../bin";
$SYS_BIN_PATH="../../bin";


The first path is for GGNFS executables, the second for system executables (like cat, gzip etc).

I use unix utilities from [url]http://sourceforge.net/projects/unxutils[/url][/QUOTE]

I have now structured my ggnfs directory like yours and put the lines

[code]$GGNFS_BIN_PATH="F:/Wissenschaft/Mathe/GGNFS/BIN";
$SYS_BIN_PATH="F:/Wissenschaft/Mathe/GGNFS/BIN";[/code]

into my factlat.pl file. I have also downloadet the linux utilities and copied the /usr/local/wbin directory to ...\GGNFS\BIN.

When I now type "factlat.pl 8_7_193-_c144.n", I get this:

[code]-> ___________________________________________________________
-> | This is the factLat.pl script for GGNFS. |
-> | This program is copyright 2004, Chris Monico, and subject|
-> | to the terms of the GNU General Public License version 2.|
-> |__________________________________________________________|
-> This is client 1 of 1
-> Working with NAME=8_7_193-_c144...
-> Error: Polynomial file 8_7_193-_c144.poly does not exist!
-> Found

n=431027695698612937534496344880801488918751557911180817931633515810874500631792439453992649830908272231949419700198659639102396998648753286

696443.
-> Attempting to run polyselect...
-> Selected default polsel parameters for 144 digit level.
-> Selected default factorization parameters for 126 digit level.
-> Selected lattice siever: F:/Wissenschaft/Mathe/GGNFS/BIN/gnfs-lasieve4I14e.exe
-> Searching leading coefficients from 1 to 1000.
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51m0b.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -p 6 -n 1.07E+022 -a 0 -A 1 >

8_7_193-_c144.polsel.Andreas.2316.log
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51opt.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -n 1.76E+020 -N 5.74E+017 -e 7.33E-012 >

8_7_193-_c144.polsel.Andreas.2316.log

Das System kann den angegebenen Pfad nicht finden
Das System kann den angegebenen Pfad nicht finden

-> =====================================================
-> Best score so far: 0.000000e+000 (goodScore=7.330000e-012)
-> =====================================================

-> Searching leading coefficients from 1001 to 2000.
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51m0b.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -p 6 -n 1.07E+022 -a 1 -A 2 >

8_7_193-_c144.polsel.Andreas.2316.log
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51opt.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -n 1.76E+020 -N 5.74E+017 -e 7.33E-012 >

8_7_193-_c144.polsel.Andreas.2316.log

Das System kann den angegebenen Pfad nicht finden
Das System kann den angegebenen Pfad nicht finden

-> =====================================================
-> Best score so far: 0.000000e+000 (goodScore=7.330000e-012)
-> =====================================================

-> Searching leading coefficients from 2001 to 3000.
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51m0b.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -p 6 -n 1.07E+022 -a 2 -A 3 >

8_7_193-_c144.polsel.Andreas.2316.log
=> "F:/Wissenschaft/Mathe/GGNFS/BIN/pol51opt.exe" -b 8_7_193-_c144.polsel.Andreas.2316 -v -v -n 1.76E+020 -N 5.74E+017 -e 7.33E-012 >

8_7_193-_c144.polsel.Andreas.2316.log

Das System kann den angegebenen Pfad nicht finden
Das System kann den angegebenen Pfad nicht finden
[/code]

("Das System kann den angegebenen Pfad nicht finden" translates to "The system can't find the specified path.")

Something is still wrong... :help:

Edit: Thanks for moving the ggnfs postings to a ggnfs thread.

I haven't tried using factlat.pl, but from what I hear, it's the easiest way to "fire and forget" on smaller numbers.

I'm still learning, but here's what I'm doing. For GNFS factorizations, I start with pol51m0b and pol51opt. There are suggested parameters for composites of various size in one of the text files included in the ggnfs source. After running these, you'll have some candidate polynomials. For a smaller factorization, I'll just use the one with the best Murphy Score, but for a larger factorization you may want to test-sieve a few.

Once you have a polynomial (either from using the GNFS tools above or constructing a SNFS polynomial), you can create an input file and run gnfs-lasieve4I13e (or 4I12e or 4I14e depending on the size of the number). There are suggested sieving parameters in a ggnfs text file, and that's a good place to start. When you get more comfortable with the program, it's good to play around with these parameters to see what impact they have and how can improve them. The siever will create spairs.out files containing partial relations.

When I have enough relations, I let msieve to do the postprocessing.

Here are some sample input files I have lying around for the various stages. They're all for different numbers. Be sure to use parameters appropriate for the number you're trying to factor.

GNFS Polynomial Selection (I specify the important parameters on the command line):

[code]n: 416955224390051909645766344571335335970454057745625070613351672491273631395040877044447543182712012172092594092483453878327809
name: InputNumber
deg: 5[/code]

Sieving:
[code]name: 7+4,208
n: 330920012486087349080109790318551271465360626325705572458597079001254847296470672859765423189021129535027618816154932964775467328815332193
deg: 6
c6: 1
c5: -1
c4: -5
c3: 4
c2: 6
c1: -3
c0: -1
Y1: 142734349946674946768896
Y0: -1104427692690664720014850817
skew: 1
type: snfs
rlim: 4500000
alim: 4500000
lpbr: 27
lpba: 27
mfbr: 53
mfba: 53
rlambda: 2.4
alambda: 2.4
q0: 4500001
qintsize: 10000000[/code]

msieve:
[code]N 21794540430563178925786277073735013833408459289340429954014220820936319062595028718005767254056951658089778749214084436566370814330793743233518175202183
R0 -129934811447123020117172145698449
R1 1350851717672992089
A0 3
A1 0
A2 0
A3 0
A4 0
A5 7
FRMAX 4500000
FAMAX 4500000
SRLPMAX 134217728
SALPMAX 134217728
SRTFBITS 52
SATFBITS 52[/code]

Probs with ggnfs on Windows
 

(First off, if there's a more appropriate place to take these question, please tell me where to go.)

Background: I've been running the Franke lattice siever since long before the invention of ggnfs. I've been running ggnfs on "small" numbers for some time as it's a convenient fire&forget tool, but only ever on Unix-like systems. Both ggnfs and the original siever have been real pigs at times to build and run, especially on x86-64 platforms, but I've tools that now work well.

My wife recently acquired a nice box (quad-core Intel, 2G RAM) running Vista. Sadly, it's 32-bit Vista because that's what it was shipped with, for compatability reasons presumably. It would be really nice if I could use it for sieving a 516-bit general number which started on a couple of other machines almost a week ago. (It's a Cunningham composite, in case Bob is reading this).

Pulling over ggnfs-0.77.1-20060513-win32-pentium4.exe from SourceForge and then a quick RTFM of the general ggnfs package allowed me to find some relations. Unfortunately, it was finding one relation every ten seconds, whereas my AMD64-3500+ finds them at ten relations per second. I know that the Intel box will not be anywhere near as efficient per cpu as the AMD (for instance, running 32-bit code, having only the 14e version of the siever instead of 15e), but a factor of a hundred is rather depressing.

Attempting to build the ggnfs snapshot from source under Cygwin was a dismal failure. Lots of complaints about missing files and what not.

Any suggestions on how to procede from here?

Thanks in advance,[INDENT]Paul[/INDENT]
P.S. If I get the siever working at a reasonable rate there will probably be follow-up questions about data formats, but we'll leave that one in abeyance for the time being.

[quote]My wife recently acquired a nice box (quad-core Intel, 2G RAM) running Vista. Sadly, it's 32-bit Vista because that's what it was shipped with, for compatability reasons presumably.[/quote]
This [I]may[/I] help, depending on what kind of license you have.

[url]http://www.microsoft.com/windowsvista/1033/ordermedia/[/url]

[QUOTE=Xyzzy;120170]This [I]may[/I] help, depending on what kind of license you have.

[url]http://www.microsoft.com/windowsvista/1033/ordermedia/[/url][/QUOTE]Thanks for the link. As it turns out, I've a copy of Ultimate anyway which includes the 64-bit version (it helps to have contacts inside MS Research :smile:) but it's not at all clear to me that the other software my wife wants and/or needs will run on a 64-bit OS. Finding out by experiment would be lengthy and disruptive...

Paul

[QUOTE=xilman;120154]Unfortunately, it was finding one relation every ten seconds, whereas my AMD64-3500+ finds them at ten relations per second. [/QUOTE]

A stab in the dark here... What's your rational polynomial? In particular, for Y1 x + Y0, is |Y1| < |Y0|? Not sure why, but Franke's source as packaged in GGNFS has been modified to assume that.

Greg

[QUOTE=frmky;120192]A stab in the dark here... What's your rational polynomial? In particular, for Y1 x + Y0, is |Y1| < |Y0|? Not sure why, but Franke's source as packaged in GGNFS has been modified to assume that.

Greg[/QUOTE]It is. The complete polynomial data is:

[code]
# BEGIN POLY #skewness 110322.87 norm 7.95e+21 alpha -6.84 Murphy_E 2.26e-12
118712091342021588844551391224983466219472825777062442260235956048963333118873331031954358817043620119241862884145836257143600744584924535114573561887470661
X5 6763456800
X4 -395072857519820
X3 -283736888636875406448
X2 4843227440564246376944509
X1 905999524978115311017408127172
X0 -27454379309543633644049032931393445
Y1 17375840997103391
Y0 -111909060020623260787928087972
M 52992360536337362244606905134124738467589762040137638374213827713699645902092270935967090899191588243743867448048204950726335414144026835944804504933976770
[/code]

Paul

[QUOTE=xilman;120217]It is. The complete polynomial data is:

Paul[/QUOTE]

I'm not sure what sieve parameters you're using, but I assumed 28-bit large primes and FB limits of 20M on each side. With these gnfs-lasieve4I14e was taking 0.75 sec/rel on a 1.7 GHz Pentium M. The Intel quad-core should take half that time per relation per core. Below is the poly file I used.

[CODE]name: paul
type: gnfs
n: 118712091342021588844551391224983466219472825777062442260235956048963333118873331031954358817043620119241862884145836257143600744584924535114573561887470661
c5: 6763456800
c4: -395072857519820
c3: -283736888636875406448
c2: 4843227440564246376944509
c1: 905999524978115311017408127172
c0: -27454379309543633644049032931393445
Y1: 17375840997103391
Y0: -111909060020623260787928087972
skew: 110322.87
alim: 20000000
rlim: 20000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56[/CODE]

Or, if you don't want to use the perl script, you can just run it directly as
gnfs-lasieve4I14e -k -o spairs.out -v -n0 -a paul.job
with the following job file, with q0 and qintsize appropriately adjusted.
[CODE]n: 118712091342021588844551391224983466219472825777062442260235956048963333118873331031954358817043620119241862884145836257143600744584924535114573561887470661
m:
c5: 6763456800
c4: -395072857519820
c3: -283736888636875406448
c2: 4843227440564246376944509
c1: 905999524978115311017408127172
c0: -27454379309543633644049032931393445
Y1: 17375840997103391
Y0: -111909060020623260787928087972
skew: 110322.87
rlim: 20000000
alim: 20000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.5
alambda: 2.5
q0: 21000000
qintsize: 5000
#q1:21005000
[/CODE]

Greg

[QUOTE=frmky;120241]I'm not sure what sieve parameters you're using, but I assumed 28-bit large primes and FB limits of 20M on each side. With these gnfs-lasieve4I14e was taking 0.75 sec/rel on a 1.7 GHz Pentium M. The Intel quad-core should take half that time per relation per core. Below is the poly file I used.[/QUOTE]Thanks Greg. I was actually using 30-bit large primes , rational base to 45M and algebraic base starting at 20M and raising as sieving progresses. Whether these values are appropriate or not is a separate question, because I was using exactly the same values with Franke's original code on the AMD64 system. The ratio was, as stated earlier, 10 per second or 1 every ten seconds. My job file looked very similar to yours -- the major difference bbeing my lambda was 2.1.

I'll see what happens

Paul

[QUOTE=xilman;120269]Thanks Greg. I was actually using 30-bit large primes , rational base to 45M and algebraic base starting at 20M and raising as sieving progresses. Whether these values are appropriate or not is a separate question, because I was using exactly the same values with Franke's original code on the AMD64 system. The ratio was, as stated earlier, 10 per second or 1 every ten seconds. My job file looked very similar to yours -- the major difference bbeing my lambda was 2.1.[/QUOTE]

The 32-bit sieve in GGNFS shouldn't be much slower than Franke's original code. With 30-bit large primes, raise mfbr/a to 60 or 61.

Greg

[QUOTE=frmky;120286]The 32-bit sieve in GGNFS shouldn't be much slower than Franke's original code. With 30-bit large primes, raise mfbr/a to 60 or 61.[/QUOTE]Not had chance to re-run the tests on my wife's machine (she's been using it) but I'll not that both mfbr and mfba are 60.

Paul

I've done a few small tests with the windows P4 executables from sourceforge on my dual core 2,1 GHz laptop.

[QUOTE=frmky;120241][CODE]name: paul
type: gnfs
n: 118712091342021588844551391224983466219472825777062442260235956048963333118873331031954358817043620119241862884145836257143600744584924535114573561887470661
c5: 6763456800
c4: -395072857519820
c3: -283736888636875406448
c2: 4843227440564246376944509
c1: 905999524978115311017408127172
c0: -27454379309543633644049032931393445
Y1: 17375840997103391
Y0: -111909060020623260787928087972
skew: 110322.87
alim: 20000000
rlim: 20000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56[/CODE][/QUOTE]
-> Selected lattice siever: ../../bin/gnfs-lasieve4I14e.exe
-> Creating param file to detect parameter changes...
=> Could not recover q0: field from job file paul.job!
-> minimum number of FF's: 2797560
-> Q0=10000000, QSTEP=60000.
-> makeJobFile(): q0=10000000, q1=10060000.
-> makeJobFile(): Adjusted to q0=10000000, q1=10060000.
-> Lattice sieving algebraic q-values from q=10000000 to 10060000.
=> "../../bin/gnfs-lasieve4I14e.exe" -k -o spairs.out -v -n0 -a paul.job
FBsize 666719+0 (deg 5), 1270606+0 (deg 1)
total yield: 263, q=10000457 (0.39765 sec/rel)


[QUOTE][CODE]name: paul
type: gnfs
n: 118712091342021588844551391224983466219472825777062442260235956048963333118873331031954358817043620119241862884145836257143600744584924535114573561887470661
c5: 6763456800
c4: -395072857519820
c3: -283736888636875406448
c2: 4843227440564246376944509
c1: 905999524978115311017408127172
c0: -27454379309543633644049032931393445
Y1: 17375840997103391
Y0: -111909060020623260787928087972
skew: 110322.87
alim: 45000000
rlim: 45000000
lpbr: 30
lpba: 30
mfbr: 60
mfba: 60
rlambda: 2.1
alambda: 2.1[/CODE][/QUOTE]-> Q0=22500000, QSTEP=60000.
-> makeJobFile(): q0=22500000, q1=22560000.
-> makeJobFile(): Adjusted to q0=22500000, q1=22560000.
-> Lattice sieving algebraic q-values from q=22500000 to 22560000.
=> "../../bin/gnfs-lasieve4I14e.exe" -k -o spairs.out -v -n0 -a paul.job
FBsize 1421069+0 (deg 5), 2718159+0 (deg 1)
total yield: 303, q=22500323 (0.45410 sec/rel)

With kambda 2.4 i get much better results:

-> Q0=22500000, QSTEP=60000.
-> makeJobFile(): q0=22500000, q1=22560000.
-> makeJobFile(): Adjusted to q0=22500000, q1=22560000.
-> Lattice sieving algebraic q-values from q=22500000 to 22560000.
=> "../../bin/gnfs-lasieve4I14e.exe" -k -o spairs.out -v -n0 -a paul.job
FBsize 1421069+0 (deg 5), 2718159+0 (deg 1)
total yield: 528, q=22500211 (0.14956 sec/rel)

I can do some sieving for you if needed.

[QUOTE=smh;120419]I've done a few small tests with the windows P4 executables from sourceforge on my dual core 2,1 GHz laptop.
...

total yield: 528, q=22500211 (0.14956 sec/rel)

I can do some sieving for you if needed.[/QUOTE]Thanks Sander.

Sieveing per se is not the problem --- I can find up to 20 Athlon boxes to help out --- but discovering why the Vista box steadfastly refuses to give me more that one relation per 10 seconds is of great interest. I'm probably doing something stupid somewhere but will persevere for a while longer before admitting defeat.

Paul

[QUOTE=xilman;120424]Thanks Sander.

Sieveing per se is not the problem --- I can find up to 20 Athlon boxes to help out --- but discovering why the Vista box steadfastly refuses to give me more that one relation per 10 seconds is of great interest. I'm probably doing something stupid somewhere but will persevere for a while longer before admitting defeat.

Paul[/QUOTE]


Have you checked memory usage/paging while it is running?

It sounds WEIRD.

so have u tried the same compilation on another pc

[QUOTE=R.D. Silverman;120449]Have you checked memory usage/paging while it is running?

It sounds WEIRD.[/QUOTE]Yup, checked all the obvious things. It's running on a machiene with 2G physical memory and the VM usages is well in line with Franke's siever running on a Linux box.

I agree, it is weird. If the speed difference was only a factor of 5 I'd shrug and mutter about 64-bit vs 32-bit or Cygwin vs Gentoo Linux, but a factor of 100 is so big that there must be something completly silly I'm overlooking.


Paul

[QUOTE=xilman;120483]Yup, checked all the obvious things. It's running on a machiene with 2G physical memory and the VM usages is well in line with Franke's siever running on a Linux box.

I agree, it is weird. If the speed difference was only a factor of 5 I'd shrug and mutter about 64-bit vs 32-bit or Cygwin vs Gentoo Linux, but a factor of 100 is so big that there must be something completly silly I'm overlooking.


Paul[/QUOTE]

Are you running the p4 executables in cygwin?

[QUOTE=smh;120489]Are you running the p4 executables in cygwin?[/QUOTE]Yes.

That might be the "ah-ha" moment...


Paul

[QUOTE=xilman;120491]Yes.

That might be the "ah-ha" moment...


Paul[/QUOTE]
I don't have cygwin installed, so can't test this for you.

[QUOTE=smh;120489]Are you running the p4 executables in cygwin?[/QUOTE]Made no discernible difference when runing under cmd.exe:sad:

Thanks, everyone, for all your help. I think I'll abandon this approach for the time being and see whether I can get a lattice siever built from source (either Franke's original or ggnfs) under Cygwin.

Paul

the def-nm-params.txt file i have got it only has params for =>98 digits which means testing numbers lower than that take ages because of poly selection being too high
does anyone one have parameters for <98 digits

thanks henryzz

If you have to cut down a large tree would you use a chain saw or table knife for the job?

If you have made yourself a nice steak for dinner, would you use use a chain saw or a table knife for the job?


Morale: Use an appropriate tool for the job at hand [HINT: Is the Number Field Sieve the best tool for the inputs you specify]?

--
Cheers,
Jes

i really want them for learning to use ggnfs but currently poly selection is taking similar time to running msieve for the whole factorization

[QUOTE=henryzz;121029]i really want them for learning to use ggnfs but currently poly selection is taking similar time to running msieve for the whole factorization[/QUOTE]
What you're seeing is the difference between the ordinary poly selection tools (which are incredibly fast) and the polyselect program in GGNFS. For small inputs you really need degree 4 polynomials, and only polyselect can generate those.

i am using factlat.pl which uses pol51m0b

[QUOTE=henryzz;121053]i am using factlat.pl which uses pol51m0b[/QUOTE]
[code]
if (length($N)<98) { $USE_KLEINJUNG_FRANKE_PS=0; }
$psTime=time;
if ($USE_KLEINJUNG_FRANKE_PS) {
runPol5;
} else {
runPolyselect;
}
[/code]

thanks i will try that now

[QUOTE=jbristow;119193][code]N 21794540430563178925786277073735013833408459289340429954014220820936319062595028718005767254056951658089778749214084436566370814330793743233518175202183
R0 -129934811447123020117172145698449
R1 1350851717672992089
A0 3
A1 0
A2 0
A3 0
A4 0
A5 7
FRMAX 4500000
FAMAX 4500000
SRLPMAX 134217728
SALPMAX 134217728
SRTFBITS 52
SATFBITS 52[/code][/QUOTE]

Just curios: What was the source of this number?

Edit: Just found out - it was 7^191+3^191

[QUOTE=jasonp;154913]There's nothing wrong with the polynomial chosen, sometimes a polynomial has excellent size properties but only moderately good root properties. What matters is how well both work together.

The problem is that this polynomial wants a sieving region skewed by a factor of about 30000, meaning the 'a' values in relations average 30k times larger than the 'b' values. It also means that the polynomial will generate a huge number of relations as long as 'b' is very small, but will stop doing so once 'b' starts to get larger. The line sieve in msieve has no idea that this is happening.

Luigi, while I appreciate the vote of confidence, there is no substitute for the lattice siever in GGNFS. Using it would make the difference between taking forever and being done very quickly.[/QUOTE]

Thank you for your answer, Jason. It seems that I'll have to study HOW-TO install and run GGNFS on my linux64 box after all... :-)

Keeping the post-sieving section on msieve.


If someone has a pointer, I'll check it during Christmas holidays... :smile:

Luigi

[quote=ET_;154914]Thank you for your answer, Jason. It seems that I'll have to study HOW-TO install and run GGNFS on my linux64 box after all... :-)[/quote]

Have you used GGNFS on another OS before?

[QUOTE=10metreh;154921]Have you used GGNFS on another OS before?[/QUOTE]

Never.

But I have Windows XP boxes (boxen?) as well, if the installation procedeure is easier.

Luigi

There are precompiled versions for the P4 and Athlon [URL="http://sourceforge.net/projects/ggnfs/"]here[/URL]. To make your factoring easier, here is factLat.pl with a .txt extension. You will need to install Perl, resave the file as just "factLat.pl" (no .txt) and edit the path in line 3 to the path of the folder where you put the binaries.
You put the poly from msieve in a file called "<name>.poly" where <name> is anything you want. Change the R's to Y's and the A's to c's. Put colons at the end of R0, R1 etc. Change N to n:, make sure you have a line "skew: xxx" where xxx is the skew and include the line "type: gnfs". Then execute "factLat.pl <name>" where <name> is the name of the poly file. It does everything in order:
Lattice siever
Relation processor
Matrix builder, which checks if there are enough relations
Lattice siever etc.
This pattern is broken when there are enough relations. At that point, close the command prompt if you want to use msieve for postprocessing. Now, so I can post two attachments, I will move onto my next post.
There are lots of details in the threads "Running GGNFS" and "New GGNFS problem", both in Factoring.

Make sure you have msieve in the same folder as ggnfs. Do the same thing with nfs2ms.pl (attached) as you did with factLat.pl, but do not edit the paths. Then execute "nfs2ms.pl". This will pack all the relations into one file then use msieve for the postprocessing.

Good luck, and check the two threads I mentioned if you have problems. If you cannot find your problem, post to "New GGNFS problem".

[QUOTE=10metreh;154929]Make sure you have msieve in the same folder as ggnfs. Do the same thing with nfs2ms.pl (attached) as you did with factLat.pl, but do not edit the paths. Then execute "nfs2ms.pl". This will pack all the relations into one file then use msieve for the postprocessing.

Good luck, and check the two threads I mentioned if you have problems. If you cannot find your problem, post to "New GGNFS problem".[/QUOTE]

Thank you very much for your help! :bow:

Now I have a good starting point to work on.

One last question: should the PC stay on all the time during sieving, or there are automatic checkpoints for restart?

Luigi

[quote=ET_;154934]Thank you very much for your help! :bow:

Now I have a good starting point to work on.

One last question: should the PC stay on all the time during sieving, or there are automatic checkpoints for restart?

Luigi[/quote]

The lattice siever gives the output "total yield: xxxxx, q=xxxxxx" or something similar. q goes gradually upwards. For the 104-digit level, the siever sieves q-values in batches of 100000. After that it runs procrels and matbuild. There is a file called "xxx.job" where xxx is the name of the poly. This has values q0 (the starting value of q), qintsize (100000 in this case) and q1 (the finishing value of q, q0+100000 in this case) in it. Every time matbuild finishes, the old q1 becomes the new q0 and a new q1 is calculated (the new q0+100000 in this case). This appears as "MakeJobFile(): q0=xxxxxx, q1=yyyyyy" on the screen. This is where you can close down. Restarting will now use the new values of q0 and q1 from the .job file.

[QUOTE=ET_;154934]Thank you very much for your help! :bow:

Now I have a good starting point to work on.

One last question: should the PC stay on all the time during sieving, or there are automatic checkpoints for restart?

Luigi[/QUOTE]

You can find some instructions, also what to do when the computer crashes or is restarted for some reason, in [URL="http://www.mersenneforum.org/showthread.php?t=9772"]this thread[/URL].

The input file for GGNFS should look like this, given as a textfile, for example named yournumber.poly (example given for a c165 number, you need to change the parameters for smaller numbers, see below):

[code]n: 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489
skew: 210886.76
c5 11472718320
c4 -3795305047120954
c3 -2612363701552248486716
c2 107677876784557388243547221
c1 33277562211750204806364306268284
c0 547440910672314203689898814059115360
Y1 2391424041494417171
Y0 -7253635851193924156735160443739
rlim: 50000000
alim: 50000000
lpbr: 31
lpba: 31
rlambda: 2.6
alambda: 2.6
mfbr: 62
mfba: 62[/code]

do the sieving with this input in your dos window:

[code]gnfs-lasieve-4I1<2,3,4,5>e -a <input file.poly> -o <output file> -f <start of sieving range> -c <length of sieving range>[/code]

use gnfs-lasieve-4I12e for numbers from ~c100 to ~c115(?)
use gnfs-lasieve-4I13e for numbers from ~c115(?) to ~c130 (the crossover is somewhere between c125 and c130)
use gnfs-lasieve-4I14e for numbers from ~c130 to ~c160
use gnfs-lasieve-4I15e for numbers >~c160

Hint: Start your range to sieve at the alim value. You may want to sieve a part of your range somewhat below the alim value - in this case you have to lower the alim value to the start of your range. (only for the range below alim - that means you can sieve any range above the original alim using the original alim.)

The Y0 and Y1 values are the R0 and R1 values given in the poly found by msieve; c0 .... c5 are the a0 ... a5 values given by the poly found by msieve. A skew is also given by msieve; dont forget to set a colon after the word skew. GGNFS won't accept a line like "skew 210886.76", but it will accept "skew[b]:[/b] 210886.76"

rlim, alim, lpbr, lpba, rlambda, alambda, mfbr and mfba have to be specified dependent on the size of your composite. You can set these values manually by editing your input file.

I have made up an excel file, which is derived from the factlat.pl script, from various posts here in the forum and from some of my factorizations, which give quite good parameters (rlim, alim, mfbr, mfba, rlambda, alambda, lpbr, lpba) for numbers in a range from ~ c100 to ~c180 - this file is attatched to this posting.

Hint: You may want to do a test sieving with a range length of ~5000 (specify -c 5000) to get an idea how many relations you get per range length. This will take only a couple of minutes.

Hint 2: It is easy to parallelize sieving: Just split your sieving ranges into a number of subranges and distribute them between your computers.

After collecting an appropriate number of relations, you need to convert your files back to msieve format. ([B]Feature request for msieve: Please make it read GGNFS outputs, and make up an option to output polynomials in GGNFS format![/B]):

1.) Make up a file named "worktodo.ini" which contains the number you want to factor.
2.) make up a file named "msieve.fb", which should look like this:

[code]N 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489
R0 -7253635851193924156735160443739
R1 2391424041494417171
A0 547440910672314203689898814059115360
A1 33277562211750204806364306268284
A2 107677876784557388243547221
A3 -2612363701552248486716
A4 -3795305047120954
A5 11472718320
[/code]

(N is the number you want to factor, R0, R1, A0 ... A5 is the polynomial - you can use the format of the output of msieve's polynomial search.)

3.) you need to merge the files which contain the relations. The first line of the merged file should contain the number in the form

[code]N <your number>[/code]

(I am not sure if msieve really needs this line - Jasonp??)

In windows (Dos window) you can do this by:

3a) create a new folder and copy all your relations files (but nothing else) into this folder.

3b) In the new relations folder create a file which's name begins with _0 (to make shure that it is copied first) which contains "N <your number>"

3c) In the Dos window type:

[code]copy *.* msieve.dat[/code]

4) Move the files named msieve.dat, worktodo.ini and msieve.ini to your msieve folder

5) in the dos window change to your msieve folder and type:

[code]msieve -p -v -nc -t <number of processors available in your machine>[/code]

-p will make msieve run in idle mode (you need not wait ages for e.g. a wordfile to open).
-v is verbose mode, meaning that you will see in the dos window what msieve is currently doing.
-nc is the command for "do GNFS postprocessing"
-t <number of threads> does multithreaded postprocessing; specify as many threads as you have processors available in your machine.

If postprocessing is successful, the factors will show up both in the dos window and in your msieve.log file.

It may occur that you have not sieved enough relations. In this case you will find a line like "filtering wants xxx more relations" near the end of the dos window output and the msieve file. In this case, continue with GGNFS sieving until you have collected enough relations, and then start with postprocessing again.

Some estimations how long sieving will take on a core2duo @2.00 GHz:

c100 - a few hours
c107 - ~7-8 hours
c114 - ~2 days
c125 - ~3 days
c130 - ~5 days
(c131 - 10 days with a poor polynomial)
c136 - ~8 days (with a poly found by msieve)
c165 - ~8 months
c180 - ~5 years
c200 - AFIK that's not yet tested by anyone

For the C104 that Luigi is doing, I would use factLat.pl and nfs2ms.pl rather than going through all the complicated stuff. nfs2ms.pl creates all the files for msieve, too.

For GNFS: What composit length is the crossover between using gnfs-lasieve4I[b]12e[/b] and 13e?

[quote=Andi47;155442]For GNFS: What composit length is the crossover between using gnfs-lasieve4I[B]12e[/B] and 13e?[/quote]
110 digits according to factmsieve.pl

Some more datapoints for lp/siever choice
 

I've been doing a bit of my own tuning for this.

One very obvious observation: starting at Q=alim and going backwards (rather than starting at Q=alim/2 and going forwards as factLat.pl does) seems to get you to a factorisation more quickly.

[b]For GNFS[/b]

12/13 crossover does seem to be around 110 digits.

At 144 digits, lp=28 using 13e is worse than lp=29 using 14e, which is itself worse than lp=28 using 14e.

28/13 beats 28/14 at 138 digits, so the crossover there is around 140

29/14 beats 28/14 quite soundly by 150 digits.

[b]For SNFS[/b]

On quartics it makes sense to go to /15 very early on (2^860+1 S208 is helped by using /15)

30/14 appears to be better than 29/14 by about S210, though rather worse at S200.

For 10^263-1, initial small experiments suggests 32/15 and 31/15 are very comparable, and since the linalg for lp=32 takes four times as long I'd use the latter.

Andi47, you put "4.7 million?" for the number of relations needed for a C100 GNFS. According to schickel, it is around 3.8 million. When I did a C100 and oversieved to 5.2 million, msieve had trouble building a matrix.

[QUOTE=10metreh;155778]Andi47, you put "4.7 million?" for the number of relations needed for a C100 GNFS. According to schickel, it is around 3.8 million. When I did a C100 and oversieved to 5.2 million, msieve had trouble building a matrix.[/QUOTE]

Thanks. These 4.7M were more or less a wild guess. I corrected it and attached the new file to this posting.

BTW: Data marked with a "?" are guesses based on interpolations, where I don't have enough / any data yet.

[quote=Andi47;155787]Thanks. These 4.7M were more or less a wild guess. I corrected it and attached the new file to this posting.

BTW: Data marked with a "?" are guesses based on interpolations, where I don't have enough / any data yet.[/quote]

In the end I knocked the number of relations down to 4 million and it worked. A tip: never oversieve too much.

I managed to download, compile and run GGNFS on my Linux64 box.

Thank you all for the help! :smile:

Luigi

P.S. is a yield of 0.0077 sec/rel a "good" parameter?:huh:

[QUOTE=ET_;155806]I managed to download, compile and run GGNFS on my Linux64 box.[/QUOTE]

Where did you download the source, what version? I'm having trouble compiling the ggnfs-0.77.1.tar.gz from sourceforge on my Linux64 box getting these errors:

[CODE]echo "#define GGNFS_VERSION \"0.77.1\"" > include/version.h
make -C src
make[1]: Entering directory `/home/jeffg/ggnfs/src'
gcc -I../include -O3 -fomit-frame-pointer -Wall -march=core2 -c
blanczos64.c
blanczos64.c: In function ‘MultB64’:
blanczos64.c:316: warning: pointer targets in initialization differ in
signedness
blanczos64.c: In function ‘MultB_T64’:
blanczos64.c:469: warning: pointer targets in initialization differ in
signedness
/tmp/ccyfRMZS.s: Assembler messages:
/tmp/ccyfRMZS.s:164: Error: `(%rdx,%ecx,2)' is not a valid base/index
expression
/tmp/ccyfRMZS.s:167: Error: `8*1(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:167: Error: `8*2(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:167: Error: `8*3(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:167: Error: `8*4(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:167: Error: `8*5(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:167: Error: `8*6(%rdx,%ecx,2)' is not a valid
base/index expression
/tmp/ccyfRMZS.s:169: Error: `(%rsi,%eax,8)' is not a valid base/index
expression
...
/tmp/ccgdcQdx.s:55976: Error: `8*n(%rbx,%eax,8)' is not a valid
base/index expression
/tmp/ccgdcQdx.s:55976: Error: `8*n(%rbx,%eax,8)' is not a valid
base/index expression
make[1]: *** [blanczos64.o] Error 1
make[1]: Leaving directory `/home/jeffg/ggnfs/src'[/CODE]

So the errors seem to come from the blancsoz64 source file which as
inline assembler. Do I need to so something special with GCC to
assemble this?

Jeff.

Batalov posted in [URL="http://www.mersenneforum.org/showpost.php?p=154007&postcount=71"]another thread[/URL], that he has added a -R (resume) option and an input sanity check to the siever (version 328). Are there win32 binaries (for P4 and/or C2D) available of gnfs-lasieve4I12e .... 4I15e, version 328?

edit: I just got an "issue" myself, which caused a windows error message, and turned out to be a typo in my input:

[code]n 171715153617185465051393022673714527931465270135551225634357302947311904186640760284113383777747947192749639705628979
skew: 261187.54
Y0 -34809139703073288415331
Y1 2359110901579
c0 3824914116375045584368825974840
c1 15238950334340823938379382
c2 -87184131588771861153
c3 -433560750171960
c4 330570356
c5 3360
rlim: 4000000
lim: 4000000
lpbr: 27
lpba: 27
rlambda: 2.6
alambda: 2.6
mfbr: 50
mfba: 50
[/code]

The "a" of alim was missing, thus causing a fatal crash of the siever (this was a version which is (much?) older than 328, so it would be nice if someone could post a (link to a) windows binary of the sievers.)

Edit2: and the colon between n and the number was missing. *grrr* (*wants an option for msieve to output ggnfs-formatted polys*)

Ok so I found the latest trunk code:
[url]http://ggnfs.svn.sourceforge.net/viewvc/ggnfs/[/url]

I was able to compile this code now. Thanks.

Sieving complete. Now what?
 

I completed sieving my C104 with 4,6M relations on spairs.out :smile:

I tried to postprocess the file using Andy43 hints, (and "cat" instead of "copy" on my linux box) and all I got was a list of error-15: can't read relations.

Then I tried 10metreh's nfs2ms.pl file, but it was configured to run on Windows, while my msieve is on linux.

Finally, I tried to let factLat.pl script run on its own to complete factorization on GGNFS, and I got "Failed to open rels.bin.0 for read" (It was the first, the second, the third... run).

Any more hints? :smile:

Luigi

using factlat.pl you will need to rename your data file spairs.add and then delete all the factlat.pl generated files except the poly file and spairs.add and then wait for it to do one short sieving run and then it should do the postprocessing

[quote=ET_;156192]I completed sieving my C104 with 4,6M relations on spairs.out :smile:

I tried to postprocess the file using Andy43 hints, (and "cat" instead of "copy" on my linux box) and all I got was a list of error-15: can't read relations.

Then I tried 10metreh's nfs2ms.pl file, but it was configured to run on Windows, while my msieve is on linux.

Finally, I tried to let factLat.pl script run on its own to complete factorization on GGNFS, and I got "Failed to open rels.bin.0 for read" (It was the first, the second, the third... run).

Any more hints? :smile:

Luigi[/quote]

Here's a script I use. The first argument should be the poly file. Then give it the name of all the data files. For example if your poly file is named gnfs.poly and you have a bunch of gnfs_0.dat, gnfs_1.dat, etc then do:

% perl make_msieve.pl gnfs.poly gnfs*.dat

It will make everything you need to run msieve.

best,
- ben.

oh, and rename the file to .pl

Is there a "run at idle priority" option for gnfs-lasieve4I1*e?

"run at idle priority" is something to be done by the command-line interpreter not the executable:

start /low gnfs-lasieve4I15e ... (in cmd on Windows)
nohup nice -19 gnfs-lasieve4I15e ... (on Unix)

[QUOTE=jasonp;156212]No, they are for unix systems. On windows you can bring up the task manager, right click on the process you want to set to idle, then select idle priority. You have to do that every time you restart the process; no doubt there are other programs that make the choice permanent.[/QUOTE]Actually, I think you;ll find that the start /low variant is for a Windows CMD window.


Paul

[QUOTE=xilman;156225]Actually, I think you;ll find that the start /low variant is for a Windows CMD window.
[/QUOTE]
Oops, I saw the 'nohup' line and stopped reading.

[QUOTE=bsquared;156196]Here's a script I use. The first argument should be the poly file. Then give it the name of all the data files. For example if your poly file is named gnfs.poly and you have a bunch of gnfs_0.dat, gnfs_1.dat, etc then do:

% perl make_msieve.pl gnfs.poly gnfs*.dat

It will make everything you need to run msieve.

best,
- ben.

oh, and rename the file to .pl[/QUOTE]

That worked! thank you very much, Ben!

Luigi

[quote=ET_;156663]That worked! thank you very much, Ben!

Luigi[/quote]

No problem, glad it helped. I think I originally got that script from fivemack when I was first learning how to use GGNFS. Good to see others becoming interested as well.

Happy factoring!

For those using Windows, I have working binaries for 32bit and 64bit Windows available using the latest GGNFS build 329 from SVN compiled with GMP 4.2.4 optimized for Core 2 systems (Visual Studio 2008).

Win32:
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win32-core2.zip[/url]

Win64:
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win64-core2.zip[/url]

Jeff.

[quote=Jeff Gilchrist;157026]For those using Windows, I have working binaries for 32bit and 64bit Windows available using the latest GGNFS build 329 from SVN compiled with GMP 4.2.4 optimized for Core 2 systems (Visual Studio 2008).

Win32:
[URL]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win32-core2.zip[/URL]

Win64:
[URL]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win64-core2.zip[/URL]

Jeff.[/quote]
could you email the links to the ggnfs mailing list
the latest that have been posted there are 322
posting here was a good idea as well though

[QUOTE=Jeff Gilchrist;157026]For those using Windows, I have working binaries for 32bit and 64bit Windows available using the latest GGNFS build 329 from SVN compiled with GMP 4.2.4 optimized for Core 2 systems (Visual Studio 2008).

Win32:
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win32-core2.zip[/url]

Win64:
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-build329-win64-core2.zip[/url]

Jeff.[/QUOTE]

Can you please add gnfs-lasieve4I[i]15[/i]e (and possibly 16e) for those who [URL="http://www.mersenneforum.org/showthread.php?t=11080"]are[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=11240"]doing[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=10781"]huge[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=10267"]factorizations[/URL]?

[QUOTE=henryzz;157033]could you email the links to the ggnfs mailing list
the latest that have been posted there are 322
posting here was a good idea as well though[/QUOTE]

I already did (I think the list is moderated so has to wait approval). I also posted them to the "Files" section of the GGNFS Yahoo Groups web interface.

Jeff.

[QUOTE=Andi47;157036]Can you please add gnfs-lasieve4I[i]15[/i]e (and possibly 16e) for those who [URL="http://www.mersenneforum.org/showthread.php?t=11080"]are[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=11240"]doing[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=10781"]huge[/URL] [URL="http://www.mersenneforum.org/showthread.php?t=10267"]factorizations[/URL]?[/QUOTE]

For some reason the Windows VS Project file didn't have them included so I created my own and have now updated the .zip file at the link above to include 15, 16, and 17 since that is what the Linux makefile will build by default.

17e is my folly :smile: ...it will not work.
I added it to the Makefile (but not to VC projects), but it was wishful thinking onmy part, ...never got the code to work for 17e (the limit is in the use of short ints all over the code; for 17e to work much should be rewritten or some trickery should be used).

16e should work though. I don't know when it will be useful, though.

I will update SVN to 330 soon, because the -R option needs a fix (it's not written quite right; it will not do anything wrong as it is now, but it will leave some regions unploughed). I will remove 17e from Makefile at the same time.

--Serge

[quote=Batalov;157091]17e is my folly :smile: ...it will not work.
I added it to the Makefile (but not to VC projects), but it was wishful thinking onmy part, ...never got the code to work for 17e (the limit is in the use of short ints all over the code; for 17e to work much should be rewritten or some trickery should be used).

16e should work though. I don't know when it will be useful, though.

I will update SVN to 330 soon, because the -R option needs a fix (it's not written quite right; it will not do anything wrong as it is now, but it will leave some regions unploughed). I will remove 17e from Makefile at the same time.

--Serge[/quote]
why is there a limit of 33-bit large primes
is that code limitations or just a manual limit
i would have thought frmky and bdodson will reach that some point soon

[quote=henryzz;157144]why is there a limit of 33-bit large primes
is that code limitations or just a manual limit
i would have thought frmky and bdodson will reach that some point soon[/quote]
The short answer is I don't know. (I only read small parts of the code. It is tougher than the Rubik's cube in some places.)

There are very many interesting tricks in this code and they are not commented at all. Most probably, again, if I'd have to guess, this has to do with the use of short ints (but because primes>2 are odd, one bit is easily saved, and so the limit is not 32 bit, but 33... but after 33 life gets hard and these complications are simply rejected by comparing to 33 and in the code that's the end of story... and no sideline comments).
The structure that holds primes uses diffs between consequitive primes (which are expected to fit in a unsigned byte; ...interesting! and this surely holds because otherwise the code has a practical sanity check and would have complained, want to check where this breaks? the answer is probably easily found on Wolfram or at primes.utm... "where's the first 256-gap in primes"; even if it doesn't hold, more internal tricks can be used, i.e. keep a table of longer jumps, etc etc etc). Anyway, the large parts of the code are simply geared towards int32's, int16's and bytes.

But the 34-bit siever is surely a solved problem (M1039 project used 36 and even 38-bit primes! didn't they?) but not readily solved with this particular public code; they had their own. Many people have their own sievers. My 2 cents. Jason surely knows the guts of the siever much better. Jason?

wolfram [url]http://mathworld.wolfram.com/PrimeGaps.html[/url] has the first >256-gap at ~387 million and the first >512-gap (I can't imagine Kleinjung not taking advantage of the fact that primes are odd!) at ~300 billion; since the iteration-over-primes is over factor-base elements this is not a problem for at all conceivable factorisations.

The 33-bit large prime limit seems entirely arbitrary; I've looked through the source, the large-prime parts only kick in once the sieving has been done, and the cofactors are handled as mpz_t throughout. When I remove it and rerun I get entirely reasonable-looking results, with correct factorisations (checked with the code below).

It is possible that there might be issues either running on a 32-bit machine or using the assembler MPQS, but the case I built (x86_64 build using no assembler) worked.

[code]
use Math::BigInt;

$Y0 = Math::BigInt->new(-1);
$Y1 = Math::BigInt->new(10)->bpow(44);
$c0 = Math::BigInt->new(-10);
$c6 = Math::BigInt->new(1);

open A,"< with-40bitLP";
while (<A>)
{
($ab,$rr,$aa) = split ":",$_;
@rs = split ",",$rr; @as = split ",",$aa;
@r=(); @a=();
for $u (@rs)
{
push @r, Math::BigInt->new('0x'.$u);
}
for $u (@as)
{
push @a, Math::BigInt->new('0x'.$u);
}
($a,$b) = split ",",$ab;
$A = Math::BigInt->new($a); $B=Math::BigInt->new($b);
$rs = $Y0 * $A + $Y1 * $B;
$as = $c6 * $A**6 + $c0 * $B**6;

$frs = 1; for $u (@r) {$frs=$frs*$u;}
$fas = 1; for $u (@a) {$fas=$fas*$u;}

print $A," ",$B," ",abs($rs)-abs($frs)," ",abs($as)-abs($fas),"\n";
}
[/code]

% /scratch/twomack/ggnfs/ggnfs/trunk/bin/gnfs-lasieve4I15e -r 10-263.lp36 -f 125000000 -c 100
total yield: 1038, q=125000149 (0.09768 sec/rel)
% /scratch/twomack/ggnfs/ggnfs/trunk/bin/gnfs-lasieve4I15e -r 10-263.lp31 -f 125000000 -c 100
total yield: 91, q=125000149 (1.07158 sec/rel)
% /scratch/twomack/ggnfs/ggnfs/trunk/bin/gnfs-lasieve4I15e -r 10-263.lp40 -f 125000000 -c 100
total yield: 2661, q=125000149 (0.03668 sec/rel)


I once did a 165-digit SNFS with 32-bit large primes to see what would happen; it needed 80 million relations (versus the 400 million that I'd expect for say a 265-digit SNFS with 32-bit large primes), and took about 48 hours to sieve. It did of course use quite a lot of disc. Highlights of the filtering:

Sat Dec 13 15:31:53 2008 found 1841832 duplicates and 79792599 unique relations
Sat Dec 13 15:31:53 2008 reading rational ideals above 18284544
Sat Dec 13 15:45:11 2008 79792599 relations and about 69673023 large ideals
Sat Dec 13 16:47:54 2008 commencing in-memory singleton removal
Sat Dec 13 16:47:56 2008 begin with 17097017 relations and 14692078 unique ideals
Sat Dec 13 16:48:22 2008 reduce to 9632853 relations and 6720056 ideals in 22 passes
Sat Dec 13 16:54:56 2008 keeping 8418453 ideals with weight <= 20, new excess is 636896
Sat Dec 13 16:56:36 2008 reduce to 4547454 relations and 3808576 ideals in 8 passes
Sat Dec 13 16:56:36 2008 max relations containing the same ideal: 18
Sat Dec 13 16:57:07 2008 found 1168829 cycles, need 1074294
Sat Dec 13 16:57:08 2008 weight of 1074294 cycles is about 75219702 (70.02/cycle)
Sat Dec 13 17:05:32 2008 matrix is 1056743 x 1056991 (304.5 MB) with weight 78205977 (73.99/col)
Sat Dec 13 17:05:32 2008 sparse part has weight 69248923 (65.52/col)
Sat Dec 13 17:05:42 2008 commencing Lanczos iteration
Sat Dec 13 17:05:42 2008 memory use: 288.5 MB
Sat Dec 13 22:00:28 2008 lanczos halted after 16711 iterations (dim = 1056743)

[QUOTE=Batalov;157091]17e is my folly :smile: ...it will not work.
I added it to the Makefile (but not to VC projects), but it was wishful thinking onmy part, ...never got the code to work for 17e (the limit is in the use of short ints all over the code; for 17e to work much should be rewritten or some trickery should be used).

16e should work though. I don't know when it will be useful, though.

I will update SVN to 330 soon, because the -R option needs a fix (it's not written quite right; it will not do anything wrong as it is now, but it will leave some regions unploughed). I will remove 17e from Makefile at the same time.
[/QUOTE]

Does anyone have access to upload changes to the GGNFS SVN repository or do you need to have special access? If you are going to submit a revision 330 soon, can I send you the modified VC project files so that it will at least build the 15e and 16e lasieve binaries as well?

Also, I have now removed the 17e binary from the .zip files and the files on the GGNFS Yahoo Group.

Jeff.

Modifying the siever to use large primes bigger than 32 bits doesn't sound that hard (incidentally, apparently the siever prints 'b' values as signed ints, and for very large SNFS runs this causes msieve to reject the 10-20 relations where b > 2^31). Modifying msieve to behave correctly in the presence of these large primes is a different matter entirely. M1039 used 35-bit large primes, and the lack of >32 bit LP support is a major bottleneck (one of several) preventing msieve from handling larger jobs than it currently does. I have several ideas to implement that efficiently, but supporting GNFS > 190 digits would require changes everywhere.

PS: I've barely looked at the lattice siever in GGNFS at all. I decided to play around with the polynomial selection code first, and make some improvements there, before taking up the larger challenge of deciphering the lattice siever.

[QUOTE=jasonp;157168](incidentally, apparently the siever prints 'b' values as signed ints, and for very large SNFS runs this causes msieve to reject the 10-20 relations where b > 2^31)[/QUOTE]

I think this must be a reflection of some slightly different problem; the 'a' and 'b' values in the siever output, at least in the SVN version of gnfs-lasieve4e.c, are calculated (around line 2222-2234) in mpz_t variables 'g_sr_a' and 'g_sr_b' from the 'true_i' (stored as 32-bit signed) and 'true_j' (stored as 16-bit unsigned) lattice coordinates output by the siever, and dealt with as mpz_t from then on.

It is of course plausible that some of the currently-used siever executables handle a and b differently.

Serge updated GGNFS in SVN to improve the -R resume feature and also added the updated Windows VC project files I made to automatically build lasieve4I15e and lasieve4I16e. Links to download the latest version below:

GGNFS [B]Windows 32bit[/B] revision 331 from SVN compiled with GMP 4.2.4
optimized for [B]Core 2[/B] systems (Visual Studio 2008):
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-svn331-win32-core2.zip[/url]

GGNFS [B]Windows 64bit[/B] revision 331 from SVN compiled with GMP 4.2.4
optimized for [B]Core 2[/B] systems (Visual Studio 2008):
[url]http://gilchrist.ca/jeff/ggnfs/ggnfs-svn331-win64-core2.zip[/url]

Jeff.

Hello Jeff, thank you very much for providing these binaries. I've just tested them out on a small snfs number, and would like to ask you some questions.

I tried the 64-bit version first since I'm running WinXP 64-bit. I ran into 2 problems on my machine. The first was that the msieve.exe binary included would not run either under cygwin or in cmd.exe. Under cygwin it said "permission denied" and under cmd.exe it said "The system cannot execute the specified program." (Not too bad, I just used another msieve that I had lying around, and then it all worked) But then, when it ran the lasieve, there was a lot of extraneous output. During the output where it normally just says q=... (0.005 sec/rel), it was also outputting many extra numbers. I've recently upgraded all the packages in cygwin, including perl, so I thought that maybe this was causing a problem. So, I went back and tried the 64-bit version of svn320 I had, and that did not produce the extra output. I also tried the 32-bit version of svn308 and svn320 I had, and neither of those produced the extra output. So, I'm not quite sure what is going on, but something about the gnfs-lasieve4I12e 64-bit svn331 is producing extra output. Have you noticed this? Or maybe its just something misconfigured on my machine.

Then I tried the 32-bit binary. Again, I was unable to use the msieve that was included in your zip package. (This time it appeared to not recognize some of the command line options) So, I used an msieve I had sitting around. When it got to the lasieve part, it worked just like normal. In fact, it ran faster than the 64-bit version did. (usually getting about 0.0029 sec/rel) Do you know if the 64-bit version should be faster or not than the 32-bit version? Maybe it is because these are optimized for Core2? I have 2 Xeon 5335's. Because of the speed difference on my system, I will be using the 32-bit version.

I want to thank you once again for providing these binaries. I really appreciate it. Hopefully my observations above will be helpful. If you'd like any more information on the above, please let me know, I'd be glad to help.

[QUOTE=WraithX;157551]
I want to thank you once again for providing these binaries. I really appreciate it. Hopefully my observations above will be helpful. If you'd like any more information on the above, please let me know, I'd be glad to help.[/QUOTE]

I'm not sure what is going on with msieve, I don't get any permission problems on my end. I just included that because it gets compiled by the ggnfs project, it is an older version of msieve so using the latest one from the official msieve website is probably better anyways.

As for the extra output, I did notice the same thing. It only seems to happen on the 64bit version, even the 32bit svn331 build does not seem to produce this. I'm not sure why it is doing that but doesn't seem to affect the output of the data as I have done an SNFS and GNFS using those binaries without any problems. It it just uglier to watch that is for sure. But if you find the 32bit version is faster on your machine, then definitely use that, and you get the nicer output as well.

As for my Core2 system, the 64bit version of the siever is also slower for some reason. I thought there were some 64bit optimizations that would improve the speed. It is possible that for whatever reason they are not being activated properly in the Visual Studio Project. Here are my timing results for 1500 q values:

[B]32bit SVN 330[/B]
[CODE]$ time ./gnfs-lasieve4I13e-32.exe -a C129_130_33.job -o 32.out
total yield: 2782, q=5701517 (0.03275 sec/rel)

real 1m34.045s
user 0m0.000s
sys 0m0.015s
[/CODE]

[B]64bit SVN 330[/B]
[CODE]$ time ./gnfs-lasieve4I13e-64.exe -a C129_130_33.job -o 64.out
total yield: 2782, q=5701517 (0.03909 sec/rel)

real 1m53.987s
user 0m0.000s
sys 0m0.000s
[/CODE]

Jeff.

[QUOTE=jasonp;157168]Modifying the siever to use large primes bigger than 32 bits doesn't sound that hard (incidentally, apparently the siever prints 'b' values as signed ints, and for very large SNFS runs this causes msieve to reject the 10-20 relations where b > 2^31). Modifying msieve to behave correctly in the presence of these large primes is a different matter entirely. M1039 used 35-bit large primes, and the lack of >32 bit LP support is a major bottleneck (one of several) preventing msieve from handling larger jobs than it currently does. I have several ideas to implement that efficiently, but supporting GNFS > 190 digits would require changes everywhere.[/QUOTE]

Sounds like you should first try to isolate the small-primes-related segments of code, then modify to use the same half-gap-stored-in-unsigned-byte strategy described above. I had a similar [although probably less extensive in terms of code penetration] issue with my Mersenne trial-factoring engine when I added multiword support recently, and desired to be able to use at least all primes < 2^32 - turned out to be not so hard, and going above 32 bit now would simply need me to to change one variable (current prime, computed on the fly from the next-smaller one) in each of the relevant code snippets from uint32 to uint64. But, as Paul likes to abbreviatize, YMMV.

[QUOTE=ewmayer;157640]Sounds like you should first try to isolate the small-primes-related segments of code, then modify to use the same half-gap-stored-in-unsigned-byte strategy described above. I had a similar [although probably less extensive in terms of code penetration] issue with my Mersenne trial-factoring engine when I added multiword support recently, and desired to be able to use at least all primes < 2^32 - turned out to be not so hard, and going above 32 bit now would simply need me to to change one variable (current prime, computed on the fly from the next-smaller one) in each of the relevant code snippets from uint32 to uint64. But, as Paul likes to abbreviatize, YMMV.[/QUOTE]

Actually, the *sieving phase* is the easy part of these large factorizations,
Handling LP > 32 bits does not require a lot of coding changes in the
siever.

However, as the recent experience of Bruce has shown with M857 and
2,908+, the filtering and LA seems to be major pains in the gluteus
medimus.

For my siever, I would need to do a little bit of extra work; The code
that splits the final two large primes is done via QS and it currently
is set up only to handle 60 bit composites. However, it still would not
be a major deal.

Dealing with the > 32 bit large primes using the CWI filter code would
require [b]major[/b] changes in that code. I could use my (now very old)
sparse matrix code (ala Odlyzko) to filter the data, but it does not
produce very good matrices. I last used that code back in the early
90's.

[QUOTE=R.D. Silverman;157641]Dealing with the > 32 bit large primes using the CWI filter code would
require [b]major[/b] changes in that code. I could use my (now very old)
sparse matrix code (ala Odlyzko) to filter the data, but it does not
produce very good matrices. I last used that code back in the early
90's.[/QUOTE]

Can you give us a sense of roughly how many lines of CWI code would need to be pored over to move to 64-bit?

Most of msieve's filtering code is completely agnostic to the size of large primes; it works with an intermediate representation of relations in which each ideal has been assigned a unique number, and as long as filtering doesn't have to deal with 4 billion [i]ideals[/i] then most of the filtering is unaffected.

I think the biggest change would involve changing the main relation structure to store a runlength-encoded list of bytes, instead of an array of 32-bit words. Most of the access to that structure is sequential anyway, so the additional overhead of reconstructing the primes in the list is negligible. There are other places that would get more complicated too, but the job is not as messy as I thought.

@WraithX: The msieve source in GGNFS is a simplified version of the full library, intended *only* for use with NFS postprocessing. Right now it's one version behind the latest release, because v1.39 had little changes everywhere.

Originally I was using [B]factLat.pl[/B] with a .poly file and then manually setting up sieving ranges on other processors, then converting the relations for msieve to use for post-processing.

I then found out about [B]factMsieve.pl[/B] which supports mutliple-CPUs so I started using that and it seems to be working fine with all 4 cores of my system except that after about a day of sieving, I had to reboot the computer. With [B]factLat.pl[/B] it would just restart where it left off, but with [B]factMsieve.pl[/B] it deleted the msieve.dat file and started over from scratch so I lost all my previous work.

Is that normal behaviour or am I doing something wrong or didn't set something up properly?

This is a known problem with the script; Greg didn't need restart capability when he wrote factMsieve.pl

The script has been needing a maintainer for a while now.

[quote=Jeff Gilchrist;157697]Originally I was using [B]factLat.pl[/B] with a .poly file and then manually setting up sieving ranges on other processors, then converting the relations for msieve to use for post-processing.

I then found out about [B]factMsieve.pl[/B] which supports mutliple-CPUs so I started using that and it seems to be working fine with all 4 cores of my system except that after about a day of sieving, I had to reboot the computer. With [B]factLat.pl[/B] it would just restart where it left off, but with [B]factMsieve.pl[/B] it deleted the msieve.dat file and started over from scratch so I lost all my previous work.

Is that normal behaviour or am I doing something wrong or didn't set something up properly?[/quote]
here are some instructions that hopefully will work:
before restarting the script rename the dat file to spairs.add
restart the script and it it starts sieving from the correct place continue otherwise stop the script again and change the job file to what it needs to be and delete .last_spq0

[QUOTE=henryzz;157735]here are some instructions that hopefully will work:
before restarting the script rename the dat file to spairs.add
restart the script and it it starts sieving from the correct place continue otherwise stop the script again and change the job file to what it needs to be and delete .last_spq0[/QUOTE]

Thanks, I will try that next time it happens. I will first make a backup of my .job and .dat files just in case. ;-)

Jeff.

[quote=Jeff Gilchrist;157765]Thanks, I will try that next time it happens. I will first make a backup of my .job and .dat files just in case. ;-)

Jeff.[/quote]
if that fails i will have an experiment myself but i think that has worked in the past

You need a few little patches.
This (ad hoc) one addresses your non-resume bug:
[code] *** 1270,1276 ****
# Should we resume from an earlier run? #
$resume=-1;
- if ((-e $RELSBIN.".0")||(-e $JOBNAME)) {
+ if ((-e $JOBNAME)[B]||(-e "$JOBNAME.T1")[/B] ) {
+ [SIZE=2]system("\"$CAT\" $JOBNAME.T1 > $JOBNAME")[/SIZE] if (-e "$JOBNAME.T1");
if ($PROMPTS) {
print "-> It appears that an earlier attempt was interrupted in progress. Resume? (y/n) ";
do {
[/code]
(in threaded situation there's no *.job file, so the easiest patch is to make one up. On linux I used [SIZE=2]`cp $JOBNAME.T1 $JOBNAME` if (-e "$JOBNAME.T1"); but I modified it here with Windows in mind.)[/SIZE]
[SIZE=2][/SIZE]
[SIZE=2]Another useful one, I've already posted elsewhere, but doesn't hurt to put it here in one place:[/SIZE]
[code][SIZE=2]*** 1309,1318 ****[/SIZE]
[SIZE=2] close(OF);[/SIZE]

[SIZE=2] open(OF, ">$FBNAME");[/SIZE]
[SIZE=2] print OF "N $N\n";[/SIZE]
[SIZE=2]+ print OF "SKEW $SKEW\n";[/SIZE]
[SIZE=2]+ if(!$COEFHASH{Y1}) {[/SIZE]
[SIZE=2]+ $COEFHASH{Y1}=1;[/SIZE]
[SIZE=2]+ $COEFHASH{Y0}="-".$M;[/SIZE]
[SIZE=2]+ }[/SIZE]
[SIZE=2][SIZE=2] for my $i (reverse 0..$DEGREE) {[/SIZE]
[SIZE=2] print OF "A$i $COEFVALS{$i}\n";[/SIZE]
[SIZE=2] }[/SIZE]
print OF "R1 $COEFHASH{Y1}\n";[/SIZE]
[SIZE=2] print OF "R0 $COEFHASH{Y0}\n";[/SIZE]
[SIZE=2] print OF "FAMAX $ALIM\n";[/SIZE]
[/code]
These [U]do not[/U] solve [U]all[/U] the resume problems. [U]Always[/U] backup before resuming. There's always more unexpected side effects. Example: if you stopped/crashed in the very beginning of -nc2 [B]DO NOT[/B] attempt to resume with the perl script. Instead, do the -nc2, -ncr (if needed) and -nc3 steps manually, from command line, and happiness will be with you.

<S>

P.S. This one also screws up the *.fb file, so move these code lines lower
[CODE][SIZE=2]
*** 1366,1375 ****
my $maxB = 0;
my $lastline = 0;

- open(OF, ">>$FBNAME");
- print OF "SLINE $A\n";
- close(OF);
-
# First, scan the line file and find the largest b-value that was sieved.
my $LINEFILE = $DATNAME.".line";
if (-e $LINEFILE) {
--- 1375,1380 ----
***************
*** 1382,1387 ****
--- 1387,1396 ----
}
if ($maxB < $B0) { $maxB = $B0; }
if ($maxB >= $B1) { return ;}
+ open(OF, ">>$FBNAME");
+ print OF "SLINE $A\n";
+ close(OF);
+
printf "-> Line file scanned: resuming classical sieve from b=$maxB.\n";
$cmd="$NICE \"$MSIEVE\" -s $DATNAME -l $LOGFILE -i $ININAME -v -nf $FBNAME -t $NUM_CPUS -ns $maxB,$B1";
print "=>$cmd\n" if($ECHO_CMDLINE);
[/SIZE][/CODE]

P.S. Since msieve is now integrated to GGNFS tree, I've added factMsieve.pl with the above (and some more) patches to the SVN.
The version is now half-the-beast 333.

[quote=Batalov;157836]The version is now half-the-beast 333.[/quote]

Some people consider the number of the beast to be 616 these days.

[QUOTE=10metreh;157870]Some people consider the number of the beast to be 616 these days.[/QUOTE]

Why 616?

[QUOTE=Batalov;157836]P.S. Since msieve is now integrated to GGNFS tree, I've added factMsieve.pl with the above (and some more) patches to the SVN.
The version is now half-the-beast 333.[/QUOTE]

Thanks for adding it and making the changes, I will try this new updated version on my new run starting tomorrow. It is now up to 334 so I guess you made some more changes and is no longer owned by the beast...

[quote=Andi47;157905]Why 616?[/quote]
Because it appears to be the number used in the earliest surviving fragments of the Book of Revelation. Google "616 number of the beast" for more information.

[QUOTE=Batalov;157836]P.S. Since msieve is now integrated to GGNFS tree, I've added factMsieve.pl with the above (and some more) patches to the SVN.
The version is now half-the-beast 333.[/QUOTE]

So I have tried the SVN334 version of factMsieve.pl and I simulated a crash. And then restarted. The script did restart from the last-Q value that was processed but the spairs.out.T1 .. spairs.out.T4 it seems were deleted so the work that had been completed from the start of the range to the current Q value was lost.

I guess it would be nice if there were spairs.out.T1..Tn files lying around to cat them to the end of the msieve.dat file before deleting them and continuing?

Also, since it is called factMsieve.pl it would be REALLY nice if it could understand how to read msieve polynomial files instead of having to convert them into the GGNFS format first. :cool:

Jeff.

[quote=Jeff Gilchrist;158091]Also, since it is called factMsieve.pl it would be REALLY nice if it could understand how to read msieve polynomial files instead of having to convert them into the GGNFS format first. :cool:

Jeff.[/quote]
the msieve poly selection will be changing a lot in the next version and we dont want to implement it twice

[QUOTE=henryzz;158096]the msieve poly selection will be changing a lot in the next version and we dont want to implement it twice[/QUOTE]

The next version of what, msieve? By a lot do you mean the output file will swap Y with R and A with c so they are both using the same format?

That is fine, but might be nice to put on a ToDo list for the future.