mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-07-16, 11:56   #1
Golem86
 
Jul 2007

2·3 Posts
Default GNFS - Factor Base

Hi!
i started to factor a c138 a few days ago, and i've finished the polynomial selection with GGNFs now. How can i choose the factor base parameters?

Kind regards
Golem86 is offline   Reply With Quote
Old 2007-07-16, 13:05   #2
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

2058 Posts
Default

Use factlat.pl -perl script, which automatically makes all steps of factorization from creating factor-base file to square rooting.
VolMike is offline   Reply With Quote
Old 2007-07-16, 13:10   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7·911 Posts
Default

c138 you'll want LP bound either 2^28 or 2^29, SP bound probably around 10^7.

I tend to sieve an appropriately-chosen range (for your size of number probably Q=15 million) of length 1000 with a variety of LP and SP bounds, and see how long it takes per relation, then assume that you need 16M relations for LP bound 2^28 and 32M for 2^29 and see how long the whole thing will take. If you want, sieve around 15M, around 20M, around 25M to see if the rate of generation is dropping off too fast.

Don't use factLat.pl: it doesn't have sensible parameters for numbers this big.
fivemack is offline   Reply With Quote
Old 2007-07-16, 16:39   #4
Golem86
 
Jul 2007

2·3 Posts
Default

Thanks, I made such a factorbase and I'm in the sieving step now. But i have another question:
I have another c138 (C138_147_75 for XYYXF) and I have 853779 relations and 1869192 primes in my relation set.

ggnfs.log says:

[...]
minimum number of FF's: 838743
[...]

But when I run matbuild, there are only 9935 (full) relations and I need 748910.
What can I do to get more full relation sets (sieving with gnfs-lasieve4I13e only brings less then 50 new full relation sets)?

Kind regards
Golem86 is offline   Reply With Quote
Old 2007-07-16, 16:46   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Golem86 View Post
What can I do to get more full relation sets (sieving with gnfs-lasieve4I13e only brings less then 50 new full relation sets)?

Kind regards
Collect enough partial relations, then combine them together. That is what
the filtering process does.
R.D. Silverman is offline   Reply With Quote
Old 2007-07-16, 18:01   #6
Golem86
 
Jul 2007

2·3 Posts
Default

So I have to do more sieving?

Kind regards
Golem86 is offline   Reply With Quote
Old 2007-07-16, 18:16   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Golem86 View Post
So I have to do more sieving?

Kind regards

More? You've only done between 5 and 10 percent of the necessary sieving.
R.D. Silverman is offline   Reply With Quote
Old 2007-07-16, 20:18   #8
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
Originally Posted by fivemack View Post
Don't use factLat.pl: it doesn't have sensible parameters for numbers this big.
Factlat.pl works fine once you've set the correct parameters in the .poly file.

I extended my own parameter file a bit so i can run numbers in batches, but i agree, when doing a factorization this large you should spend some time testing. For a c110 or c120 i won't take the trouble.
smh is offline   Reply With Quote
Old 2007-07-16, 20:56   #9
Golem86
 
Jul 2007

2×3 Posts
Default

@Silverman:
Oh no, i think this will take a while!

@smh:
I think factLat.pl is good if you use SNFS, but although its parameters seem to be better than mine.

Kind regards
Golem86 is offline   Reply With Quote
Old 2007-07-17, 06:01   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
Originally Posted by Golem86 View Post
@smh:
I think factLat.pl is good if you use SNFS, but although its parameters seem to be better than mine.
It's as good for GNFS as for SNFS. The script reads the parameters from a text file. The file is easy to edit your self.
smh is offline   Reply With Quote
Old 2007-07-17, 14:16   #11
Golem86
 
Jul 2007

2×3 Posts
Default

I think if you use SNFS you have a better polynomial which results in a faster factorisation. This speed increase compensates the bad choices of the script.

Kind regards
Golem86 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why can't I start factmsieve.py with a poly file, but no factor base? EdH Factoring 25 2018-03-26 15:59
Base-6 speed for prime testing vs. base-2 jasong Conjectures 'R Us 36 2010-08-03 06:25
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
Algebraic factor issues base 24 michaf Conjectures 'R Us 18 2008-05-21 10:08
Quadratic Sieve - How large should the factor base be? hallstei Factoring 5 2005-04-19 11:58

All times are UTC. The time now is 09:47.

Tue Jan 19 09:47:00 UTC 2021 up 47 days, 5:58, 0 users, load averages: 1.35, 1.75, 2.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.