10+ table - Page 8

Raman · 2008-08-09, 12:17

Quote:

Originally Posted by bsquared

skew: 1
c6: 1
c3: 10
c0: 100
Y1: -1
Y0: 100000000000000000000000000000000000000
rlim: 25000000
alim: 25000000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6
alambda: 2.6

Well, I will start up 6,343- with the same parameters on my laptop today.

So, you take 'full 58' for mfbr and mfba? (Checking the cofactor by (e.g. Pollard's Rho) after dividing by the sieve primes, whether it splits up into 29 bit smooth primes). Won't it slow down the siever? Because it is very rare for a 58-bit composite to be split up into two 29 bit primes.

What are alambda and rlambda?

10,375- is going on in my Core 2 Quad desktop, about 16 million rational special-q sieved, so far, to yield around 20 million unique relations (a rough estimate, I haven't verified it though). I need around 65 million, because it uses up with (lpbr=30 / lpba=29) in the GGNFS poly file.

Quote:

Well, I see that 2,1586L and 10,236+ are being untouched for a long time. 2,1586L is going to be the first hole in both GNFS (after 2,2286M is getting completed up) and as well as in the 2LM tables.

And 11,227- 11,229- 11,226+ are remaining as the first holes in the 11 tables for more than 2 years. It is lying as dead, and nobody is willing to touch it up at all?

Somebody is seriously making fun of me up! Analogous to this.

Distributed Computing Projects
and (vs) is similar to
Unsolved Problems in Mathematics

jasonp · 2008-08-09, 15:06

Quote:

Originally Posted by Raman

So, you take 'full 58' for mfbr and mfba? (Checking the cofactor by (e.g. Pollard's Rho) after dividing by the sieve primes, whether it splits up into 29 bit smooth primes). Won't it slow down the siever? Because it is very rare for a 58-bit composite to be split up into two 29 bit primes.

What are alambda and rlambda?

When you get to factorizations of this size, you are doing much more sieving than trial factoring of relations, so that you can afford to make the latter take longer in order to avoid missing promising relations. Bob reports that trial factoring in his implementation takes 1% of the total time, so it helps to make it take twice as long in order to find an extra relation now and then.

Because the sieve contains log values, and these are approximate, when the sieve reports a number as almost smooth then the unfactored part of that number may be a lot smaller than 58 bits. To avoid missing relations because of the approximate nature of adding up logarithms of factor base primes, sieve values whose rational (algebraic) logarithm is smaller than rlambda (or alambda) times lpbr (or lpba) have trial factoring attempted. This is a way to compensate for the sieving not knowing exactly how big all the numbers are; if you do all the trial factoring and find that a remaining cofactor is larger than rlim (or alim) bits then the relation is still rejected.

bsquared · 2008-08-10, 03:52

Agree with Jason. I've experimented with different mfbr/a values for some factorizations, but rarely do anymore. It seems to have such a small impact on the total run time that it's not worth optimizing, so I usually will just set it to 2x the lpbr/a value and call it good enough. This is obviously not a scientific justification, but the job still gets done and I typically don't care if it takes 1% longer.

Raman · 2008-08-10, 15:45

Quote:

Originally Posted by bsquared

Agree with Jason. I've experimented with different mfbr/a values for some factorizations, but rarely do anymore. It seems to have such a small impact on the total run time that it's not worth optimizing, so I usually will just set it to 2x the lpbr/a value and call it good enough. This is obviously not a scientific justification, but the job still gets done and I typically don't care if it takes 1% longer.

Alright regarding the mfbr and mfba values. I can always keep it twice that of lpbr and lpba.

But, how much impact does alim and rlim values have on the (1) total run time and (2) yield of relations (including the rate of yield?)

GGNFS def-par text file gives the value of factor base limits for even a 182 digit quintic as 15M. So, asymptotic to these estimates, I took up the factor base limits for 6,305- as 40M and 7,295- as 80M.

But, your community only take up so for a 210 digit sextic as 20M and 225 digit sextic as 25M within it?

For 10,312+ I took only 20M, but it increased to 40M as I sieved all special-q upto 40M on the algebraic side. To be more clear, for 6,343- I define the factor base limits in my polynomial file as only 25M for both the algebraic and rational sides, but as I sieve the special-q beyond this limit, I have to increase these limits in the job file, like this:

And, on the other side, I will have to keep alim below the special-q value, if I were to sieve the algebraic side, (in the job file), and vice-versa, in the following way:

Code:

m: 134713546244127343440523266742756048896
c6: 1
c5: 1
c4: 1
c3: 1
c2: 1
c1: 1
c0: 1
skew: 1
rlim: 25000000
alim: 10000000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6
alambda: 2.6
q0: 10000001
qintsize: 999999
#q1:11000000

otherwise this following error will be reported:
Special-q value 10000001 below factor base limit of 2.5e+7

PS: For 6,343- it is 400000 relations after 400000 special-q is being sieved so,
in 1 day exactly.

bsquared · 2008-08-14, 15:51

The C172 cofactor of 10,378+ factors by SNFS as:

Code:

prp78 factor: 344410449392555791991391842565560527204857067026484035552706583597118812185729
prp95 factor: 17558859918233971274267353045256604123625708155378236163954582400346807794005623131429977614689

Using ggnfs and msieve 1.36.

- ben.

Raman · 2008-08-16, 14:12

Great! So, what parameters for a SNFS of size 252?

Difficulty 252, right?
$10^{252}-10^{126}+1$

How many special-q you needed to sieve for this one, i.e. range of special-q

How much resources do you have?
This is fast enough for a number of this size!

Code:

My laptop is sieving 6,343- and my desktop is sieving 10,375-.
Just 1.5 million relations (1.6 million algebraic special-q sieved
so far for 6,343-) I have so for 6,343- and I should have
by now > 20 million relations for 10,375- (20 million rational special-q
sieved so far for 10,375-)

frmky · 2008-08-16, 17:50

Quote:

Originally Posted by Raman

Great! So, what parameters for a SNFS of size 252?

Difficulty 252, right?
$10^{252}-10^{126}+1$

No. Considerably easier. Factoring out $10^{36}-10^{18}+1$ leaves $10^{216}+10^{198}-10^{162}-10^{144}+10^{108}-10^{72}-10^{54}+10^{18}+1$ . Now divide by $10^{108}$ and write as a polynomial in $x=10^{18}+10^{-18}$ giving $x^6+x^5-6x^4-6x^3+8x^2+8x+1$ . (Verify this!) Now you have only a difficulty 216 to deal with. Harder than 10,375-, but easier than 6,343-.

For the rational polynomial, you have $x-(10^{18}+10^{-18})$ . Multiply by $10^{18}$ leaving $10^{18}x-(10^{36}+1)$ .

Greg

Raman · 2008-08-17, 06:04

Quote:

Originally Posted by frmky

No. Considerably easier. Factoring out $10^{36}-10^{18}+1$ leaves $10^{216}+10^{198}-10^{162}-10^{144}+10^{108}-10^{72}-10^{54}+10^{18}+1$ . Now divide by $10^{108}$ and write as a polynomial in $x=10^{18}+10^{-18}$ giving $x^6+x^5-6x^4-6x^3+8x^2+8x+1$ . (Verify this!) Now you have only a difficulty 216 to deal with. Harder than 10,375-, but easier than 6,343-.

For the rational polynomial, you have $x-(10^{18}+10^{-18})$ . Multiply by $10^{18}$ leaving $10^{18}x-(10^{36}+1)$ .

Greg

Ha, 375 is a multiple of 15 and 378 is a multiple of 21.

Thanks for your good explanation of reducing the degree of the algebraic side polynomial.
The same thing can also hopefully be applied to 10,375- too.

But, I think that it should be easier than 10,375-.
10,375- uses a quartic and 10,378+ uses a sextic.

ONE IMPORTANT OBSERVATION:
I have started sieving the algebraic side for 10,375- (20 million
rational special-q sieved so far for this number)

When I put mfbr/mfba = twice lpbr/lpba, it tremendously improved
the rate of yield of relations, although the execution time per
special-q did not change so at all!

My advice to newcomers is that to keep always the mfbr/mfba
values as twice that of lpbr/lpba values

bsquared · 2008-08-18, 04:01

Raman, if you're still curious, these were the parameters I used:

Code:

n: 6047454835259897495291763612688187307633783265817592232229921776128879618476797113843402906053007327639026397234531321020396264462376520701053491628306270734047741866573281
skew: 1
c6: 1
c5: 1
c4: -6
c3: -6
c2: 8
c1: 8
c0: 1
Y1: -1000000000000000000
Y0: 1000000000000000000000000000000000001
rlim: 15000000
alim: 15000000
lpbr: 28
lpba: 28 
mfbr: 56 
mfba: 56 
rlambda: 2.6 
alambda: 2.6

fivemack · 2008-10-13, 14:15

Unexciting SNFS (30-bit large primes, small prime bound 50M, sieved 44M-63M both sides)

5hrs for (four) sqrt, 132hrs for matrix prep and Lanczos, about 2700hrs sieving.

Code:

Mon Oct 13 03:13:18 2008  prp58 factor: 3091086674769589337569777240589592264676648718635101423877
Mon Oct 13 03:13:18 2008  prp113 factor: 74941782666871080572139707864851693613852773414268140020183607240075991444673103041682886153162527722083599097543

bsquared · 2009-01-04, 02:54

10,236+ factors as:

Code:

 
prp68 factor: 32394937980403032343941480318880086318307142570248235727782772042697
prp125 factor: 36837015057313006096634536795587748230336921494253255771361450341226561526611901358724245001042863132758337028749847212746321

After about 15k cpu hours sieving using gnfs-lasieveI15e and 265 hrs of linear algebra using msieve 1.38 on 4 cpus on a 9.1M square matrix.

- ben.

2008-08-16, 14:12	#83
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts	Great! So, what parameters for a SNFS of size 252? Difficulty 252, right? $10^{252}-10^{126}+1$ How many special-q you needed to sieve for this one, i.e. range of special-q How much resources do you have? This is fast enough for a number of this size! Code: My laptop is sieving 6,343- and my desktop is sieving 10,375-. Just 1.5 million relations (1.6 million algebraic special-q sieved so far for 6,343-) I have so for 6,343- and I should have by now > 20 million relations for 10,375- (20 million rational special-q sieved so far for 10,375-)

2008-10-13, 14:15	#87
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6422₁₀ Posts	10+259 done Unexciting SNFS (30-bit large primes, small prime bound 50M, sieved 44M-63M both sides) 5hrs for (four) sqrt, 132hrs for matrix prep and Lanczos, about 2700hrs sieving. Code: Mon Oct 13 03:13:18 2008 prp58 factor: 3091086674769589337569777240589592264676648718635101423877 Mon Oct 13 03:13:18 2008 prp113 factor: 74941782666871080572139707864851693613852773414268140020183607240075991444673103041682886153162527722083599097543

2009-01-04, 02:54	#88
bsquared "Ben" Feb 2007 3516₁₀ Posts	10,236+ factors as: Code: prp68 factor: 32394937980403032343941480318880086318307142570248235727782772042697 prp125 factor: 36837015057313006096634536795587748230336921494253255771361450341226561526611901358724245001042863132758337028749847212746321 After about 15k cpu hours sieving using gnfs-lasieveI15e and 265 hrs of linear algebra using msieve 1.38 on 4 cpus on a 9.1M square matrix. - ben. Last fiddled with by bsquared on 2009-01-04 at 02:54

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
5+ table	garo	Cunningham Tables	100	2021-01-04 22:36
7+ table	garo	Cunningham Tables	86	2021-01-04 22:35
6+ table	garo	Cunningham Tables	80	2021-01-04 22:33
5- table	garo	Cunningham Tables	82	2020-03-15 21:47
6- table	garo	Cunningham Tables	41	2016-08-04 04:24

2008-08-10, 03:52	#80
bsquared "Ben" Feb 2007 2²×3×293 Posts	Agree with Jason. I've experimented with different mfbr/a values for some factorizations, but rarely do anymore. It seems to have such a small impact on the total run time that it's not worth optimizing, so I usually will just set it to 2x the lpbr/a value and call it good enough. This is obviously not a scientific justification, but the job still gets done and I typically don't care if it takes 1% longer.