2LM Table

[R.D. Silverman]

Originally Posted by Raman

It seems that you have reserved up dozens of numbers with Prof. Sam Wagstaff? Thus, how many computers do you save so for sieving, and then finally also for doing up with the Linear Algebra too?

My matrix step for 6,343+ has just started up simply, and that msieve tells that it will have 5329870 rows. It's running up within the safe mode under the /3GB virtual memory switch.

How many special-q's will I need to sieve so for (say) 6,335+ or 6,340+? These are quartics, when compared to those sextics 10,339+, 7,393+, 7,396+ because the exponents, they are multiples of 5, rather than the latter ones, which are that multiples of 3.

I think that I will prefer so to do a quartic, for my next number, rather than a sextic, because of the fact that - although a quartic needs so with more sieving time than a sextic does - the matrix at the end, I believe so will be smaller. Because of the fact that the SNFS difficulty is lesser for a quartic, by around 20 or 25, it takes so more time for the sieving process, to accumulate up the relations (because the coefficients on the rational side are larger). This anyway takes up lesser memory space. At the end, the number of relations totally will be lesser, so that I think so that the overall matrix size will be lesser, with lower number of relations, in all, so that it would well accommodate up certainly within the 2 GB of RAM size, at the end. So, am I right?

No, you are not correct. The matrix size depends on 3 things: the
size of the factor base, the large prime bounds, and the amount of
oversieving. It has nothing to do with the degree of the polynomial.

And your belief about quartics being easier is false as well. For
numbers with SNFS difficulty above 190, a number factored with a
quartic will be much harder than an equivalent sized number done with a sextic. And it gets worse as the composites get bigger.
Quartics are distinctly sub-optimal.

2,865+ required just under 5 million special q's using a sieve region of
area 128 x 10^6 per q. [from -8K to +8K, from 0 to 8K]. A Larger sieve
region would require fewer special q, but more memory.

[bdodson]

Originally Posted by Raman

It seems that you have reserved up dozens of numbers with Prof. Sam Wagstaff? ...

Do you mean more than 1.0*(1 dozen)? I count 14 for Batalov+Dodson,
which will drop to 13 as soon as Sam gets

factorization of 2, 1642L C191:

>  prp73 factor: 1114404962447069351651510873273409827476273598943279186006740523095719801
>   prp119 factor: 15965363586264291494628224506300120126039963053196835338867449245806612320778760457
> 812721805655896095714497945885207209 

Batalov+Dodson snfs.

We'll drop back to 1.0*(1 dozen) soon, when the c169 gnfs finishes. -Bruce

(nowhere near two dozens...)

[Andi47]

After a filtering attempt (51M raw rels, 44.2M unique), I got this:

Mon Sep 14 20:32:28 2009  Msieve v. 1.42
Mon Sep 14 20:32:28 2009  random seeds: a19a0840 4e475588
Mon Sep 14 20:32:28 2009  factoring 228177525389586273638690339431177745823876548936193399336166213513134791320999468488116782236199109864672970596636889473352811891080481904411966784365801 (153 digits)
Mon Sep 14 20:32:30 2009  searching for 15-digit factors
Mon Sep 14 20:32:31 2009  commencing number field sieve (153-digit input)
Mon Sep 14 20:32:31 2009  R0: -123068542008272408063341696798
Mon Sep 14 20:32:31 2009  R1:  32545837753591997
Mon Sep 14 20:32:31 2009  A0: -210217628742759011847051033170606625
Mon Sep 14 20:32:31 2009  A1:  691865081823429884957346608055
Mon Sep 14 20:32:31 2009  A2:  7389222372719222769566031
Mon Sep 14 20:32:31 2009  A3: -15710647975218134519
Mon Sep 14 20:32:31 2009  A4: -42401104350982
Mon Sep 14 20:32:31 2009  A5:  8082360
Mon Sep 14 20:32:31 2009  skew 1.00, size 7.128831e-015, alpha -6.486866, combined = 5.447557e-014
Mon Sep 14 20:32:31 2009  
Mon Sep 14 20:32:31 2009  commencing relation filtering
Mon Sep 14 20:32:31 2009  estimated available RAM is 2046.1 MB
Mon Sep 14 20:32:31 2009  commencing duplicate removal, pass 1
Mon Sep 14 20:34:28 2009  error -11 reading relation 7844009
Mon Sep 14 20:34:37 2009  error -15 reading relation 8475744
Mon Sep 14 20:44:35 2009  found 8000084 hash collisions in 51345071 relations
Mon Sep 14 20:46:20 2009  added 121883 free relations
Mon Sep 14 20:46:20 2009  commencing duplicate removal, pass 2
Mon Sep 14 20:51:15 2009  found 7174730 duplicates and 44292224 unique relations
Mon Sep 14 20:51:15 2009  memory use: 213.2 MB
Mon Sep 14 20:51:15 2009  reading ideals above 47775744
Mon Sep 14 20:51:15 2009  commencing singleton removal, initial pass
Mon Sep 14 21:03:25 2009  memory use: 596.8 MB
Mon Sep 14 21:03:25 2009  reading all ideals from disk
Mon Sep 14 21:03:26 2009  memory use: 719.8 MB
Mon Sep 14 21:03:31 2009  commencing in-memory singleton removal
Mon Sep 14 21:03:36 2009  begin with 44292223 relations and 39333520 unique ideals
Mon Sep 14 21:04:34 2009  reduce to 23725150 relations and 16114675 ideals in 19 passes
Mon Sep 14 21:04:34 2009  max relations containing the same ideal: 34
Mon Sep 14 21:04:42 2009  reading ideals above 720000
Mon Sep 14 21:04:42 2009  commencing singleton removal, initial pass
Mon Sep 14 21:15:38 2009  memory use: 532.8 MB
Mon Sep 14 21:15:38 2009  reading all ideals from disk
Mon Sep 14 21:16:51 2009  memory use: 843.7 MB
Mon Sep 14 21:17:00 2009  keeping 21720936 ideals with weight <= 200, target excess is 134953
Mon Sep 14 21:17:06 2009  commencing in-memory singleton removal
Mon Sep 14 21:17:13 2009  begin with 23725161 relations and 21720936 unique ideals
Mon Sep 14 21:18:33 2009  reduce to 23605038 relations and 21600693 ideals in 12 passes
Mon Sep 14 21:18:33 2009  max relations containing the same ideal: 200
Mon Sep 14 21:19:03 2009  removing 2913507 relations and 2513507 ideals in 400000 cliques
Mon Sep 14 21:19:05 2009  commencing in-memory singleton removal
Mon Sep 14 21:19:12 2009  begin with 20691531 relations and 21600693 unique ideals
Mon Sep 14 21:20:04 2009  reduce to 20459244 relations and 18850121 ideals in 9 passes
Mon Sep 14 21:20:04 2009  max relations containing the same ideal: 187
Mon Sep 14 21:20:31 2009  removing 2169713 relations and 1769713 ideals in 400000 cliques
Mon Sep 14 21:20:32 2009  commencing in-memory singleton removal
Mon Sep 14 21:20:38 2009  begin with 18289531 relations and 18850121 unique ideals
Mon Sep 14 21:21:19 2009  reduce to 18134461 relations and 16922433 ideals in 8 passes
Mon Sep 14 21:21:19 2009  max relations containing the same ideal: 173
Mon Sep 14 21:21:43 2009  removing 1931331 relations and 1531331 ideals in 400000 cliques
Mon Sep 14 21:21:44 2009  commencing in-memory singleton removal
Mon Sep 14 21:21:50 2009  begin with 16203130 relations and 16922433 unique ideals
Mon Sep 14 21:22:26 2009  reduce to 16060688 relations and 15245888 ideals in 8 passes
Mon Sep 14 21:22:26 2009  max relations containing the same ideal: 163
Mon Sep 14 21:22:47 2009  removing 1808296 relations and 1408296 ideals in 400000 cliques
Mon Sep 14 21:22:48 2009  commencing in-memory singleton removal
Mon Sep 14 21:22:53 2009  begin with 14252392 relations and 15245888 unique ideals
Mon Sep 14 21:23:24 2009  reduce to 14109378 relations and 13691337 ideals in 8 passes
Mon Sep 14 21:23:24 2009  max relations containing the same ideal: 147
Mon Sep 14 21:23:43 2009  removing 1229204 relations and 967709 ideals in 261495 cliques
Mon Sep 14 21:23:44 2009  commencing in-memory singleton removal
Mon Sep 14 21:23:48 2009  begin with 12880174 relations and 13691337 unique ideals
Mon Sep 14 21:24:13 2009  reduce to 12805098 relations and 12647324 ideals in 7 passes
Mon Sep 14 21:24:13 2009  max relations containing the same ideal: 141
Mon Sep 14 21:24:35 2009  relations with 0 large ideals: 462
Mon Sep 14 21:24:35 2009  relations with 1 large ideals: 368
Mon Sep 14 21:24:35 2009  relations with 2 large ideals: 7091
Mon Sep 14 21:24:35 2009  relations with 3 large ideals: 71041
Mon Sep 14 21:24:35 2009  relations with 4 large ideals: 393648
Mon Sep 14 21:24:35 2009  relations with 5 large ideals: 1306909
Mon Sep 14 21:24:35 2009  relations with 6 large ideals: 2736082
Mon Sep 14 21:24:35 2009  relations with 7+ large ideals: 8289497
Mon Sep 14 21:24:35 2009  commencing 2-way merge
Mon Sep 14 21:25:00 2009  reduce to 8282034 relation sets and 8124260 unique ideals
Mon Sep 14 21:25:00 2009  commencing full merge
Mon Sep 14 21:28:51 2009  memory use: 863.1 MB
Mon Sep 14 21:28:53 2009  found 4410364 cycles, need 4388460
Mon Sep 14 21:28:53 2009  weight of 4388460 cycles is about 307216457 (70.01/cycle)
Mon Sep 14 21:28:53 2009  distribution of cycle lengths:
Mon Sep 14 21:28:53 2009  1 relations: 557603
Mon Sep 14 21:28:53 2009  2 relations: 561632
Mon Sep 14 21:28:53 2009  3 relations: 552260
Mon Sep 14 21:28:53 2009  4 relations: 496234
Mon Sep 14 21:28:53 2009  5 relations: 447760
Mon Sep 14 21:28:53 2009  6 relations: 382911
Mon Sep 14 21:28:53 2009  7 relations: 326922
Mon Sep 14 21:28:53 2009  8 relations: 267176
Mon Sep 14 21:28:53 2009  9 relations: 213722
Mon Sep 14 21:28:53 2009  10+ relations: 582240
Mon Sep 14 21:28:53 2009  heaviest cycle: 21 relations
Mon Sep 14 21:28:56 2009  commencing cycle optimization
failed to reallocate 163840000 bytes

*grrrr*

I will retry -nc1 with 1.38 and see if it swaps or aborts. If it aborts, I'll try filtering on my (a bit slower) P4 (3 GB RAM available) - or is there a trick to force msieve 1.42 to use swap instead of aborting with with "failed to reallocate xy bytes"?

[Batalov]

a small quartic with no previously known factors
2,2094M c210 = p92 . p119

p92 = 19657681165969603557219187243003321749273455802601598904262946663319721006141051366816994929
p119 = 66896698765448213521324984376509886004228325964295120994894490766034340579242578036357051829886756590059740051576400529


Batalov+Dodson, snfs 30/28-bit, ~72M unique relns, 4.05M² matrix

[Andi47]

2,1766M c153 - my first cunningham factorization - is done, the factors are:

Sun Sep 20 23:36:20 2009  prp67 factor: 1576370469903203279973040031491663414039828010968075560583660537453
Sun Sep 20 23:36:20 2009  prp87 factor: 144748667744072540197095153836730132162311404874692206021273640791263948199818616404717
Sun Sep 20 23:36:20 2009  elapsed time 72:19:25

msieve logfile is attached.

To whom should I email the factors?
________

Congratulations, well done!
Email goes to http://homes.cerias.purdue.edu/~ssw/cun/ see the bottom link.

[Andi47]

Originally Posted by Batalov

Congratulations, well done!
Email goes to http://homes.cerias.purdue.edu/~ssw/cun/ see the bottom link.

Thanks, mail to Sam Wagstaff is out.

BTW: When an answer is edited into the "previous" post, it is very easily missed, as the forum does not show it as a new post in the subforum resp. in the thread.

[R.D. Silverman]

Originally Posted by Andi47

Another one.

.

Here is 2,1694M c170 = p74.p96

p74 = 93482176145308518782106472614623228828649287462023235510999355448300543057
p96 = 649020123227726012084109135827124600837468052666952390075372537243991130317277003243150566745273

2,1119+ is about 45% sieved.

[Batalov]

Ok, in the attached log one may find a few unusual features:
• an 8th-degree polynomial
• initial square root modulo 17 (sic!)
but in the end a very satisfying factorization using KF sievers and slightly modified msieve 1.43 (SVN 119):

2,2190L c163 = p75 . p89
p75=260388090213152722245485411960014340275503208289295000550325920282114359301
p89=15883115150267559641161772963772260999831424911221235519197362273575462453226350957559061

Because of this number's properties (2190 is divisible by 3 and 5), the alternatives to the difficulty 175 octic (which is a reciprocally reduced 16-th degree poly after dividing out both 2,730M and 2,438M) were a quartic of difficulty 220 or gnfs-163. Both were tested to be slower than the octic (left as an excercise to the reader); the gnfs polynomial for comparison is available upon request.

Batalov+Dodson snfs
with special thanks to Jason P. for stimulating discussions and msieve.

You may find early preliminary discussions here and here.

[Andi47]

Originally Posted by Batalov

Ok, in the attached log one may find a few unusual features:
• an 8th-degree polynomial
• initial square root modulo 17 (sic!)
but in the end a very satisfying factorization using KF sievers and slightly modified msieve 1.43 (SVN 119):

2,2190L c163 = p75 . p89
p75=260388090213152722245485411960014340275503208289295000550325920282114359301
p89=15883115150267559641161772963772260999831424911221235519197362273575462453226350957559061

According to the logfile, duplication removal has been done beforehand (so it can't be seen in the file ("found 0 duplicates and 40M unique relations")) - what was the approx. overall duplication rate?

[Batalov]

Correct. Greg and Bruce have a filtering program which is very helpful to reduce FTP time.

The earlier removed duplicate count was (I don't have exact numbers)
~53.2M raw -
~14.6M duplicates (Greg and Bruce have a filtering program)
= 38.54M unique (which was ftp'd)
+ then msieve added some free relations.

Our target was 34-38M unique. When Bruce reported the initial stats from ~80% done, and we were hitting around 34M in projection, I've asked to extend the region by 10% and he had resources to do it. That turned out to be safe.

This was a 28/29 project. For 27/28, expect to need 17-19M, unique, and if the duplicates would be similar, ~26M raw relations.

B+D

[Batalov]

Just in time before NFS@Home clears 2,1678L,M (in a few days),
the 2,1646L and 2,1654L are now factored with straightforward sextics.
2,1646L c208 = p91 . p118
2,1654L c195 = p67 . p128

Thanks to Bruce!