Large small factor

[Joe O]

Originally Posted by JHansen

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

Thanks for your reply. If you have Athlon optimized binaries, I would appreciate them. I am running Windows XP on an AMD64. I find that SSE2 optimized binaries do not run as well unless they are optimized for the Pentium M. My email is factrange at yahoo dot com.

[Mystwalker]

Am I right with the assumption that you try to do a GNFS factorization with a 305 digit (~1016 Bit) number?
If yes, I really doubt this is sensible. After all, the current record factorization is 200 digits - and it took already very long. In the next years, there most likely will be a Kilobit factorization attempt - but using SNFS and a promising number to factor.
Even it is was possible, I'm sure ggnfs is not able to handle it yet.

[JHansen]

Originally Posted by Joe O

My email is factrange at yahoo dot com.

Email sent. The attached zip-file is 2.62MB.

--
Cheers,
Jes

[Zeta-Flux]

Jes,

Thanks for trying to help. Even when unzipping the 0.77.0 version there were errors. I went to the ggnfs website and registered, and sent an email out for help. Later, I realized that now that I was registered I could click on the "files" link. So I downloaded the latest zip file for a P4 computer. Now all I need to do is know where to unzip the files, and how to run them.

In other words, I need help:
1) knowing where to put the unzipped files.
2) knowing where to put that text file you were talking about.
3) anything else I don't know about, like which program to run, etc...

[JHansen]

Originally Posted by Zeta-Flux

In other words, I need help:
1) knowing where to put the unzipped files.
2) knowing where to put that text file you were talking about.
3) anything else I don't know about, like which program to run, etc...

1) Anywhere you choose. I use c:\ggnfs

2) Same place. All files must be in the same folder. In my ggnfs directory I have the following files: cat.exe, def-nm-params.txt, def-par.txt, factLat.pl, gnfs-lasieve4I12e.exe, gnfs-lasieve4I13e.exe, gnfs-lasieve4I14e.exe, gzip.exe, makefb.exe, matbuild.exe, matsolve.exe, pol51m0b.exe, pol51opt.exe, polyselect.exe, procrels.exe, sieve.exe and sqrt.exe. Phew!

3) If you want to use the perl script (recomended if you are unsure of what the different programs do) you must install ActivePerl. It's free, just Google for it

--
Cheers, Jes

[Joe O]

Originally Posted by Mystwalker

Am I right with the assumption that you try to do a GNFS factorization with a 305 digit (~1016 Bit) number?
If yes, I really doubt this is sensible. After all, the current record factorization is 200 digits - and it took already very long. In the next years, there most likely will be a Kilobit factorization attempt - but using SNFS and a promising number to factor.
Even it is was possible, I'm sure ggnfs is not able to handle it yet.

Trust you to count the digits, and recognize the number.<G>
This is just a learning experience. I don't have a smaller number that I am interested in. If I did, I would certainly use it to learn with. I just want to get to the point that I have everything working. Then I will see if I can compute how long it will take. Right now, I'm just interested in the polynomial selection phase, comparing the various methods.
By the way, this number lends itself to SNFS.

[akruppa]

Even with SNFS there's no hope for you to factor this number now. Try ECM, or wait a couple more years until home PCs are more powerful or possibly a better factoring method is discovered.

Alex

[R.D. Silverman]

Originally Posted by akruppa

Even with SNFS there's no hope for you to factor this number now. Try ECM, or wait a couple more years until home PCs are more powerful or possibly a better factoring method is discovered.

Alex

Indeed. It will also require only 64 bit machines because 32 bit machines
do not have enough address space. Nor are there many machines with > 4G
of real memory.


And I don't think current implementations
allow larger than 32 bit primes in the factor base, nor have the extended
128-bit integer routines that would be required.

Doing (say) R311 or M1061 with SNFS would be a massive, massive effort
for the sieving, and I doubt whether the capability exists anywhere for
solving the matrix. I estimate (very roughly) a minimum of 500 million rows
would be in the matrix (for SNFS; GNFS would be much bigger).
RSA-200 had 64 million rows.

[smh]

I never tried mingw, but compiling GGNFS under CYGWIN is easy.
Bolds are commands in cygwin, the rest can be done under windows.

Goto www.cygwin.com and click install or update now.

Use Unix for the default text type and make sure you install at least gcc, make (under Devel.), perl (under Interperters) and bc, gmp, gnuplot (under math).

Start cygwin for the first time to create the user home directory.

Download GGNFS to your homedirectory and on the cygwin command line type:

tar zxf ggnfs-0.77.1.tar.gz

Followed by:

cd ggnfs

to get into the ggnfs directory.

Under windows you'll have to edit makefile.athlon (in the src folder) and uncomment (remove #) your cpu type.

In cygwin, type:

make

(now i always rename the ggnfs folder to one with the version number in it).

In the test folder there is a file called factlat.pl

Open this file in your favourite text editor and uncomment the following line:

$GGNFS_BIN_PATH="../../src";

put a comment (#) before the other paths.

Create a new folder under test where all the files for the factorization will be in. Lets say, c100
Copy the factlat.pl file into this folder and create a new text file with the .n extension. Lets say, number.n
In this file place the following lines:

n: <number to factor>
type: gnfs

I'm not sure this last line is still needed.

Under cygwin, now change to the directory which you just created.

cd tests
cd c100

and start the perl script:

./factlat.pl number

Thats it for a general number. For special numbers, check the examples in test folder. Once sieving starts, you can intterupt anytime with ctrl-c and resume where you left of with the same command. The script nows where it was before it was interupted.

General numbers upto 110-115 digits work fine with the default parameters, for larger factorizations you might want to get some experience with the program and change some defaults.

[Mystwalker]

Originally Posted by JHansen

1) Anywhere you choose. I use c:\ggnfs

2) Same place. All files must be in the same folder. In my ggnfs directory I have the following files: cat.exe, def-nm-params.txt, def-par.txt, factLat.pl, gnfs-lasieve4I12e.exe, gnfs-lasieve4I13e.exe, gnfs-lasieve4I14e.exe, gzip.exe, makefb.exe, matbuild.exe, matsolve.exe, pol51m0b.exe, pol51opt.exe, polyselect.exe, procrels.exe, sieve.exe and sqrt.exe. Phew!

3) If you want to use the perl script (recomended if you are unsure of what the different programs do) you must install ActivePerl. It's free, just Google for it

One more step:
You have to adjust the bin path in the beginning of factLat.pl:
$GGNFS_BIN_PATH="<path>";

I forgot it two or three times...

Originally Posted by Joe O

Trust you to count the digits, and recognize the number.<G>

Actually, I didn't. But I do now, of course.

Well, it's quite hard to find small composites nowadays, thanks to msieve and ggnfs

I think the smallest composites can be found here. There should be composites with ~100 digits, which take maybe a day with ggnfs.

[akruppa]

The Factorizations of Cyclotomic Numbers page by Hisanori Mishima (http://www.asahi-net.or.jp/%7EKC2H-MSM/cn/index.htm) has lots of SNFS candidates, including easier ones that'd be excellent for learning the ways of SNFS.

Alex