mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2005-01-11, 22:16   #1
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

53058 Posts
Default 12- table

Code:
Size    Base    Index    Mod    Diff    Ratio
335	12	311	-	335.6	0.998
283	12	313	-	337.7	0.837
260	12	319	-	312.9	0.83	/11
290	12	331	-	357.2	0.811
265	12	337	-	363.6	0.727
345	12	347	-	374.4	0.921

Last fiddled with by Batalov on 2021-01-05 at 18:00 Reason: 12,343- is done
garo is offline   Reply With Quote
Old 2005-08-08, 21:07   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

141448 Posts
Default

Here are current curve counts for this table:

12,299- B 11000000 1751
12,299- B 110000000 297
12,227- B 11000000 4522
12,269- B 11000000 4581
12,259- B 11000000 4481
12,259- B 110000000 22
12,247- B 11000000 4616
12,247- B 43000000 6
12,233- B 11000000 4741
12,295- B 11000000 4676
12,271- B 11000000 4668
12,229- B 11000000 4610
12,229- B 43000000 4
12,241- B 11000000 4347
12,241- B 110000000 7
12,257- B 11000000 4472
12,277- B 11000000 3840
12,293- B 11000000 4515
12,293- B 110000000 6
12,281- B 11000000 3665
12,289- B 11000000 4376
12,283- B 11000000 4050

I'm stopping on this now.
rogue is online now   Reply With Quote
Old 2008-02-26, 14:20   #3
hlaiho
 
hlaiho's Avatar
 
Feb 2005

29 Posts
Default 12,229- completed

According to:
http://www.loria.fr/%7Ezimmerma/records/c120-355

CWI has completed 12^229-1 by SNFS , the second largest factor is

5614625825187525959903363633922994959000986456830889529904105379

Last fiddled with by hlaiho on 2008-02-26 at 14:21
hlaiho is offline   Reply With Quote
Old 2008-02-28, 12:51   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default Filtering Weirdness

I encountered something strange when filtering 2,776+.

Sieving is nearly done and I ran a trial filtering pass
last night. The first pass was done with mergelevel 2 and
filtmin = 18.8million (corresponding to 1.2 million ideals
per polynomial below 18.8M).

Some duplicates had already been removed. Here is the output
from the first pass.
========================================================
Maximum number of shrinkage passes executed.
Start final pass at Mon Feb 25 18:43:31 2008 after 10061.053 seconds.
15233697 duplicate relations were detected.
58419 relation-sets were discarded because they are too heavy.
Output file has 22891386 relations in 21850372 sets.
Another 155388 free relations on large primes available.
There may be additional free relations on factor base primes.
Net 22005760 equations on 13108742 large prime ideals in [18800000, 1000000000].
3924632 relation-sets have exactly 0.0 relations (frees count 0.5).
15276016 relation-sets have exactly 1.0 relations (frees count 0.5).
43507 relation-sets have exactly 1.5 relations (frees count 0.5).
1491504 relation-sets have exactly 2.0 relations (frees count 0.5).
31578 relation-sets have exactly 2.5 relations (frees count 0.5).
529280 relation-sets have exactly 3.0 relations (frees count 0.5).
23328 relation-sets have exactly 3.5 relations (frees count 0.5).
230061 relation-sets have exactly 4.0 relations (frees count 0.5).
17580 relation-sets have exactly 4.5 relations (frees count 0.5).
113312 relation-sets have exactly 5.0 relations (frees count 0.5).
13447 relation-sets have exactly 5.5 relations (frees count 0.5).
60413 relation-sets have exactly 6.0 relations (frees count 0.5).
10027 relation-sets have exactly 6.5 relations (frees count 0.5).
34220 relation-sets have exactly 7.0 relations (frees count 0.5).
7611 relation-sets have exactly 7.5 relations (frees count 0.5).
20788 relation-sets have exactly 8.0 relations (frees count 0.5).
5954 relation-sets have exactly 8.5 relations (frees count 0.5).
12764 relation-sets have exactly 9.0 relations (frees count 0.5).
4350 relation-sets have exactly 9.5 relations (frees count 0.5).

Row weight Frequency Cum freq Cum wght pct
1 25 25 0.00
2 65 90 0.00

<snip>
========================================================


There seems to be an excess of 8897018 = 22005760 - 13108742 equations at this point.
No doubt some of them arise from duplicate relations, so the next pass was run
with mergelevel 0. Sure enough, it found a fair number of duplicates:

====================================================
# Filter part of Number Field Sieve

<snip>

Initializing hash table (duplicates) with 43875001 entries...
Starting nfs.fin1. 0 relations in 0 sets after 0.152 seconds.
Duplicate relation found: a=-233572, b=13353

<snip>

Read 22728574 relations in 22728574 sets in 384.829 seconds.
Freeing hash table...
5008788 duplicate relations were detected.
0 relation-sets were discarded because they are too heavy.
Output file has 17719786 relations in 17719786 sets.

======================================================


So of the 8897M execess equations, 5008M arise from duplicates.
This is fine, because it still leaves an excess of 8.897 - 5.008 = 3.889M
excess equations. 2.4million are needed to take care of the ideals
BELOW 18.8 million, so it seems that I still have an excess of
3.889-2.400 = 1.489M equations . These get removed with higher
merge level passes.

However, before I do the higher merge levels, I always do another
pass with mergelevel 2 after removing the duplicates. And I got a
BIG SURPRISE:

======================================================
# Filter part of Number Field Sieve
# X86 (Windows) $Revision: 1.44 $ $Date: 2003/05/27 00:20:02 $
# Department of Mathematics, Oregon State University

<snip>

<snip>

Maximum number of shrinkage passes executed.
Start final pass at Mon Feb 25 20:13:24 2008 after 4607.354 seconds.
0 duplicate relations were detected.
220471 relation-sets were discarded because they are too heavy.
Output file has 14360944 relations in 7953642 sets.
Another 102666 free relations on large primes available.
There may be additional free relations on factor base primes.
Net 8056308 equations on 8259014 large prime ideals in [18800000, 1000000000].
=====================================================


I now have a DEFICIT! This final filter pass discarded 220K relations
because they were too heavy, but I thought that I had an excess of 1.489M
to begin with! Where did the excess go???
R.D. Silverman is offline   Reply With Quote
Old 2008-02-28, 12:58   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I encountered something strange when filtering 2,776+.

Sieving is nearly done and I ran a trial filtering pass
last night. The first pass was done with mergelevel 2 and
filtmin = 18.8million (corresponding to 1.2 million ideals
per polynomial below 18.8M).

<snip>

A followup. I gathered another 1.5M relations over the last two days.
After the first filter pass, I had an excess of 9.65million equations.
5.45M of these were duplicates, leaving 4.2million in excess.
Another filter pass with mergelevel 2 then gave 9.2million equations
on 9million ideals over 18.8million; i.e. an excess of 200K.
About 350K relations were discarded during this pass because they were
too heavy. However, 4.2million - 350K = 3.85million. 2.4 million
are needed to take care of the ideals below 18.8 million, so I should
have an excess of 1.45million and not an excess of 200K.

Where did the rest go????
R.D. Silverman is offline   Reply With Quote
Old 2008-02-28, 14:47   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I now have a DEFICIT! This final filter pass discarded 220K relations
because they were too heavy, but I thought that I had an excess of 1.489M
to begin with! Where did the excess go???
Does merge level 2 create relation sets out of relations that have ideals of weight 2? The filtering deleted 220k relation sets, could those sets contain a huge number of relations somehow? Also, when does singleton removal happen in this scheme, and can it be responsible for deleting many more relations than ideals? Finally, 25% duplicates sounds like a lot, maybe you needed to do a lot more sieving and the removed duplicates turned many ideals into singletons.

Last fiddled with by jasonp on 2008-02-28 at 14:48
jasonp is offline   Reply With Quote
Old 2008-02-28, 15:26   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
Does merge level 2 create relation sets out of relations that have ideals of weight 2? The filtering deleted 220k relation sets, could those sets contain a huge number of relations somehow? Also, when does singleton removal happen in this scheme, and can it be responsible for deleting many more relations than ideals? Finally, 25% duplicates sounds like a lot, maybe you needed to do a lot more sieving and the removed duplicates turned many ideals into singletons.

Merge level two only means that at most 2 relations are combined into 1.
Singleton removal happens in the first pass.

Duplicates are only about 20%. I started with about 80M relations.
Some duplicates (5M) were removed prior to the first filtering pass.
15M duplicates got removed in the first pass.
R.D. Silverman is offline   Reply With Quote
Old 2008-02-28, 15:44   #8
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

Quote:
Originally Posted by jasonp View Post
Does merge level 2 create relation sets out of relations that have ideals of weight 2? The filtering deleted 220k relation sets, could those sets contain a huge number of relations somehow? Also, when does singleton removal happen in this scheme, and can it be responsible for deleting many more relations than ideals? Finally, 25% duplicates sounds like a lot, maybe you needed to do a lot more sieving and the removed duplicates turned many ideals into singletons.
Yes, mergelevel n (n>1) creates sets by merging on ideals that appear no more than n times.

Although duplicate and singleton can be, and often are, done before mergelevel 2, they are also done at each pass at the higher levels.

However, consider the effect of merging on "excess".
In the case of a duplicate, you remove one relation and zero ideals, for a net "cost" of 1.
In the case of a singleton, you remove one relation and one (or more) ideals, for a net "cost" of 0 (or, potentially, a net gain)
In the case of a doubleton, you remove 2 relations, 1 ideal and introduce 1 "set", for a net "cost" of 0 (unless the resulting set is discarded as "heavy" - but that is counted separately.)

Thus, the net effect on excess by doing any level merge should be no worse than the sum of the duplicates eliminated + the "heavy" discards.
Wacky is offline   Reply With Quote
Old 2008-02-28, 16:01   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by Wacky View Post

Thus, the net effect on excess by doing any level merge should be no worse than the sum of the duplicates eliminated + the "heavy" discards.
Exactly. Which is why I am puzzled about the disappearing excess.
R.D. Silverman is offline   Reply With Quote
Old 2009-02-04, 17:47   #10
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default updates

Quote:
Originally Posted by garo View Post
Code:
Base	Index	Size	11M(45digits)	43M(50digits)	110M(55digits)	260M(60digits)	Decimal
12	233-	C215	
12	239-	C202	
12	241-	C260	factored  Childers/Dodson/Wackerbarth
12	247-	C209	
12	257-	C269	  p52*c218  
12	269-	C205	
12	271-	C234	
12	277-	C285	
12	281-	C294	
12	283-	C295	==> c244  Nakano+Imaishi+Kawashima+Ohno
12	289-	C248	
12	293-	C293	
12	295-	C228	
12	299-	C174
New p52 = 3210333482150938236735353240875928231167166319686291
from 12,257- C269, found twice overnight, with B1 = 260M. Cofactor starts
c218 = 23231152219465... Likewise, the c244 cofactor of 12,283- starts
448271923276293... The snfs difficulty for 257- is around 276, so the
c218 is still likely easier by snfs (but somewhat less attractive, as a smaller
number). -Bruce

Last fiddled with by bdodson on 2009-02-04 at 17:52 Reason: credit due, twice
bdodson is offline   Reply With Quote
Old 2009-02-04, 18:05   #11
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by bdodson View Post
New p52 = 3210333482150938236735353240875928231167166319686291
from 12,257- C269, found twice overnight, with B1 = 260M. Cofactor starts
c218 = 23231152219465... Likewise, the c244 cofactor of 12,283- starts
448271923276293... The snfs difficulty for 257- is around 276, so the
c218 is still likely easier by snfs (but somewhat less attractive, as a smaller
number). -Bruce
How much ECM had been done on that number at lower levels? A P52 seems rather small for a B1 of 260M.
10metreh is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:48.

Sun Feb 28 13:48:16 UTC 2021 up 87 days, 9:59, 0 users, load averages: 1.35, 1.21, 1.25

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.