GNFS - Factor Base

Golem86 · 2007-07-16, 11:56

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

VolMike · 2007-07-16, 13:05

Use factlat.pl -perl script, which automatically makes all steps of factorization from creating factor-base file to square rooting.

fivemack · 2007-07-16, 13:10

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.

Golem86 · 2007-07-16, 16:39

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

R.D. Silverman · 2007-07-16, 16:46

Quote:

Originally Posted by Golem86

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.

Golem86 · 2007-07-16, 18:01

So I have to do more sieving?

Kind regards

R.D. Silverman · 2007-07-16, 18:16

Quote:

Originally Posted by Golem86

So I have to do more sieving?

Kind regards

More? You've only done between 5 and 10 percent of the necessary sieving.

smh · 2007-07-16, 20:18

Quote:

Originally Posted by fivemack

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.

Golem86 · 2007-07-16, 20:56

@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

smh · 2007-07-17, 06:01

Quote:

Originally Posted by Golem86

@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.

Golem86 · 2007-07-17, 14:16

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

2007-07-16, 11:56	#1
Golem86 Jul 2007 2·3 Posts	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

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

2007-07-16, 13:05	#2
VolMike Jun 2007 Moscow,Russia 205₈ Posts	Use factlat.pl -perl script, which automatically makes all steps of factorization from creating factor-base file to square rooting.

2007-07-16, 13:10	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7·911 Posts	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.

2007-07-16, 16:39	#4
Golem86 Jul 2007 2·3 Posts	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

2007-07-16, 18:01	#6
Golem86 Jul 2007 2·3 Posts	So I have to do more sieving? Kind regards

2007-07-16, 20:56	#9
Golem86 Jul 2007 2×3 Posts	@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

2007-07-17, 14:16	#11
Golem86 Jul 2007 2×3 Posts	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