Large small factor

[VJS]

wblipp,

Could you point us to a few good reference regarding nfs or snfs the differences etc. As Zeta-flux said, setting up ecm is easy of course most people would choose the most efficient way of doing things but nfs don't even know where to start. Also alot of people want to do either their own numbers not co-ordinate with a remote server.

Add to this alot of my machiens are no-net or behind firewalls. Other projects run great on them, etc.

Any links setups etc??? Step by step... Most people including myself are Windoze people if you have to compile etc .

Don't mean to throw a wrench in here or poach on a project etc it just seems as though nfs isn't used enough, and people who have it setup keep the programs to themselves.

[JHansen]

GGNFS is your friend! You can find it at http://www.math.ttu.edu/~cmonico/software/ggnfs/

It's a free (i.e. GLP'ed) NFS suite written (mostly) by Chris Monico. It includes Frankes lattice sievers and Kleinjungs polynomial selection tools, and is thus quite fast. SNFS numbers in the range 140-170 are easily handled by this suite as well as GNFS number in the range 100-135 digits.

There is a yahoo group at http://groups.yahoo.com/group/ggnfs.

If you don't want to compile it yourself, you can download the latest version by clicking a link in one of the latest posts in the group.

The Good News (TM): All it takes to factor a number using the general number field sieve (GNFS) is a single text file with one line

n: <number-to-factor>

That's it! Then you start the fully automated perl script (yes, you can run perl scripts in windows too: Google for ActivePerl), which does all the rest of the work for you. All you have to do is sit back and let the script do it's work.

More good news: If you have more than one computer, the script supports multiple clients for sieving.

If you want to do SNFS you still have to construct the polynomials by hand, but hey: That's part of the fun of SNFS!


It's improving all the time and not a bad choice for people who wants to factor numbers and learn a bit about NFS in doing so (eventhough you can easily use the suite without the faintest idea about how NFS works).

--
Cheers,
Jes

[Zeta-Flux]

JHansen,

Could you give me a run-down of how to compile it? I have MingGW and gmp already installed on my computer (Pentium 4, running Windows XP). I'd just like a list of command lines to run.

So, for example, I suppose that the first step is to download the source file and place it in the home directory. Then in the "home" directory, while running MingSys type:

1) gunzip ggnfs-0.77.0.tar.gz
2) tar -xvf ggnfs-0.77.0.tar

Then what do I type?

Thanks,
Pace

[VJS]

Originally Posted by JHansen

GGNFS is your friend! You can find it at http://www.math.ttu.edu/~cmonico/software/ggnfs/

not a bad choice for people who wants to factor numbers and learn a bit about NFS in doing so (eventhough you can easily use the suite without the faintest idea about how NFS works).

Hey Thanks Jes, looks like it could suit me just fine. I'll give it a go within the next few weeks. It's more about the learning curve for me anyways.

[Zeta-Flux]

Anybody out there that can help me? Do I need to get the Pearl script thing first?

[Joe O]

Jes,
Could you help me? About a month ago, I posted this question on the GGNFS forum:

From: "joseph_osiecki" <JMOsiecki@NetScape.Net>
Date: Sat Apr 23, 2005 12:12 pm
Subject: Questions about polyselect output joseph_osiecki

Could someone explain, or point me to an explanation of the following
output:

Initialization done:
Score: 9.407293e-037 (adj. I=175.9845, iteration -308203561,
minStage1=10000.00)

k: -1280835384, log_2(I) = 175.56, sieving... (mTry=0)

Thanks

So far, no one has responded. Any and all information you can supply will be apprecieated
Joe.

[JHansen]

Originally Posted by Zeta-Flux

So, for example, I suppose that the first step is to download the source file and place it in the home directory. Then in the "home" directory, while running MingSys type:

1) gunzip ggnfs-0.77.0.tar.gz
2) tar -xvf ggnfs-0.77.0.tar

Then what do I type?

That's right. After you have done this you need to compile the binaries. MinGW behaves 'almost' like Linux, but I have had trouble with running make. What I did was this:

1) In the src directory delete Makefile ( an empty file) and rename Makefile.x86 (or Makefiel.athlon if you have an Athlon) to Makefile

2) Open this Makefile in a text editor and add the following

-I/usr/local/include -L/usr/local/lib

to one fo the options in the make file. I've added this to the line that starts with ALLOPT.

3) Go into the pol5 directory and open the makefile there. Add the same to one of the lines there. I used the line CFLAGS.

4) Go one step back (to src) and into lasieve4 directory. Delete the empty file called asm and rename the directory Piii to asm. Edit the makefile there and add the same again. I used the line CFLAGS line again.

5) In the lasieve4 directory, inter the renamed asm directory and edit the makefile there. I added the line to the CFLAGS line again.

6) Go back into the src directory. I forgot one more thing about the makefile there. It contains some lines beginning with 'ls ...' under the item polsel. Remove all lines staring with ls.

7) Pad youself on the shoulder for a job well done

8) go way back so that you are in the main directory and type make

9) If all went well, you can collect your binaries from the src, lasieve4 and pol5 directories. Remember also to copy the factlat.pl file from the test directory and the two files def-par.txt and def-nm-params.txt to where you want to place yout new, shiny ggnfs binaries.

Hope that helped. If you get any warnings or errors during compiling I can't help out, since the art of compiling is black magic to me and I always look upon the process in great awe and wonder

Try the ggnfs group I mentioned instead, it's full of people who understands that went wrong and how to fix it.

--
Cheers,
Jes

[JHansen]

Originally Posted by Joe O

Jes,
Could you help me? About a month ago, I posted this question on the GGNFS forum

It doesn't look like the Kleinjung poly selection tool. Try starting again with the newest binaries. I can send them to you if you want. Other that that I wouldn't know what to do

--
Cheers,
Jes

[ixfd64]

Nice oxymoron. :P

Anyways, congratulations. :)

[trilliwig]

Originally Posted by Joe O

From: "joseph_osiecki" <JMOsiecki@NetScape.Net>
Date: Sat Apr 23, 2005 12:12 pm
Subject: Questions about polyselect output joseph_osiecki

Could someone explain, or point me to an explanation of the following
output:

Initialization done:
Score: 9.407293e-037 (adj. I=175.9845, iteration -308203561,
minStage1=10000.00)

k: -1280835384, log_2(I) = 175.56, sieving... (mTry=0)

Thanks

Ah, I remember that post, but I left it to someone who knew Montgomery-Murphy poly selection better to answer. But in the absence of someone fitting that description, I can say this appears to be the polyselect program that Chris Monico wrote. And I don't believe the iteration number or k should be negative in normal operation... generally among the parameters we give polyselect are a polynomial degree d, an initial k0 value, a number of iterations Q to go through, and a k-multiplier, all positive integers.

Polyselect will then generate a polynomial of degree d expressing the number N to be factored with leading coefficient k0 times k-mult, do a little searching to find a polynomial with good root properties, perhaps do some sieving to score it using the Montgomery-Murphy criterion, and then record this polynomial if the score is a current high score or exceeds a specified threshold. It then increments the leading coefficient by k-mult and repeats this Q times. It looks to me that something went wrong in parameter specification, or perhaps this compilation of polyselect was buggy.

--
Sam

[Joe O]

Originally Posted by trilliwig

It looks to me that something went wrong in parameter specification, or perhaps this compilation of polyselect was buggy.

--
Sam

Thanks for your reply.
I used the binaries provided by jeskamstrup in ggnfs-0.73.4 Athlon.zip

MinGW binaries of ggnfs-0.3.4 compiled on an AMD64, so that must make 'em Athlon optimized, eh? :-) This version includes the patched version of procrels to keep memory usage down.

125 CPU hours on an AMD64 2.4MHz gave me the console output that I included in my post, and the following output:

name: unknown
n: 517693523749349506216820125753852827887841227092964547799532292131198709993702048088168912046169305517623230936748285019817469002581460400322168936455700478369002740323880863059299067393413818235615141804531075491540754845960240845920074337097867783823725951696351550002765728018732362221078040255922177
m: 69275185946235975401920817781795086359429419943173055518
deg: 5
c5: 324477233998503505920000
c4: 9107750047406932278176920
c3: 622130271799212637486555054166295676498730179625
c2: -11331828963928813858332777814821853888843363343264078556
c1: -286953360046424551467488394264573948181207409629075873016
c0: -2549394954163534564497751277220800646749169513023999552311
skew: 1635.250
type: gnfs
# adj. I(F,S) = 175.985
# E(F1,F2) = 9.407293e-037
# GGNFS version 0.73.4 polyselect.
# Options were:
# lcd=1, enumLCD=0, maxS1=10000.00000000, seed=1112568783.
# maxskew=2000.0
# These parameters should be manually set:
rlim:
alim:
lpbr:
lpba:
mfbr:
mfba:
rlambda:
alambda:
qintsize: