mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Closed Thread
 
Thread Tools
Old 2009-05-03, 19:05   #12
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Quote:
Originally Posted by frmky View Post
Not much oversieving. I would have expected the matrix to be much bigger. Even our 2,908+ matrix is a bit bigger. And the i7 is fast! That matrix took only a month. The 2,908+ matrix should finish in a couple of weeks, and it will have taken about 3.5 months on a 2GHz Barcelona K10.
Greg
I'd say there was a fair amount of oversieving; initially Bruce sieved 10M-160M on both sides, getting 278146913 unique relations, and the matrix that arrived was noticeably bigger:

Tue Mar 24 21:52:20 2009 matrix is 22586885 x 22587133 (6499.2 MB) with weight 1573087910 (69.65/col)

with an ETA of about 1130 hours.

There seem to be advantages in the linear algebra as well as in sieving yield to having a fairly large small-prime bound; 2+908 had to deal with an enormous duplication rate to get its relations.

The i7 has a very good memory controller, and I think benefits significantly from being in a single-processor system so there's no requirement to check ownership of cache lines with a processor not on the same piece of silicon. I am surprised to have finished before 2+908 did.
fivemack is offline  
Old 2009-05-03, 21:34   #13
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by 10metreh View Post
How much ECM was run? Was the P58 an ECM miss?
The number was C249, diff 270 when Tom found it, so only 2*t50. I added
7*t50, as 11020 curves with B1 = 260M (default B2). Also, Tom reports
Quote:
Taking out the P58 would have left a number probably slightly harder by GNFS than the SNFS was.
perhaps illustrating Bob's point that these large composites aren't very good
candidates for ecm factoring. My recollection (from late Jan/early Feb) is
that this was the last hard number before my adjusting to p59/p60 factors
found in snfs's from Greg and Tom. I'm just finishing c. 14*t50 on Serge's
2, 2068M, at c268 = diff 268. -Bruce
bdodson is offline  
Old 2009-05-04, 10:07   #14
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default Timing and duplication estimates

I re-ran 0.01% of the sieving (Q=k*10^7 .. k*10^7+10^3) on one CPU of the i7 machine and extrapolated up (using per-ideal measures) for the yield and timings.

So I would estimate that the A10-170 R10-260 produced 430 million R-side and 280 million A-side raw relations, for a duplicate rate of near-enough 50% (367M unique), and took about 350 million CPU-seconds: call it a hundred thousand CPU-hours. This is about 30% longer than the C180 GNFS took last year, and rather over twice as long as 109!+1 has taken to sieve.

A10-160 R10-160 would have been about 540 million raw relations (so a duplicate rate still essentially 50%, since 278M unique) in about 250 million CPU-seconds, so we used about 10^8 CPU-seconds on the cluster to save (1130-821)*3600 ~ 10^6 seconds of real-time on the linalg machine. I think the cluster's big enough that this was a saving in terms of total time.

Last fiddled with by fivemack on 2009-05-04 at 10:13
fivemack is offline  
Old 2009-05-04, 10:28   #15
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×1,657 Posts
Default

Congratulations! Very impressive all around, and a very fast job for such a huge matrix!

The 96-96 split is a nice entry for a modern Kunstkammer.
(Sadly, there exists a 97-97 split.) But anyway!

-S
Batalov is offline  
Old 2009-05-04, 14:50   #16
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·7·132 Posts
Default

Finding 14 dependencies in the presence of those zero-character messages is also a relief. The other possibility was that too many quadratic characters generated these messages, so that you would get dependencies from the linear algebra but the square root would fail on all of them (or perhaps just half of them, with complaints that Newton iteration did not converge).

There's a fairly simple workaround to minimize the chance of that happening in the future, and it will become especially important now that jobs with 32-bit large primes are becoming more common.

Last fiddled with by jasonp on 2009-05-04 at 14:50
jasonp is offline  
Old 2009-05-04, 14:57   #17
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by 10metreh View Post
How much ECM was run? Was the P58 an ECM miss?
OK, that was the long version. Here's the short version: if I had
found the p58, it would have been the 2nd largest on the current
top10, after four months of global ecm effort, everyone. Factors
above p57 are a gift, not a computational objective.

On Xilman/Paul's point that ecm pretesting, on hard sieving candidates
with small and medium sized factors removed is less likely to give
a top10 factor, I now have three of these candidates with small factors
p58, p59 and p60. (As well as a bunch with smallest factor p80+.)
I'm still puzzled why untested numbers ought to be any more likely to
give up a p62+ than one of these near-term sieving candidates. -Bruce
bdodson is offline  
Old 2009-05-04, 22:51   #18
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

193616 Posts
Default

One of the four dependencies did give me a 'Newton iteration did not converge' message, which presumably means that half of them would have but that I was lucky.

I may well not understand this correctly, but I thought the quadratic characters were there to kill off the 2-part of the unit group of the underlying number field, and that there's no reason to believe that that 2-part will be terribly large: Aoki's factorisations which say 'we found 64 dependencies and reduced by quadratic characters to 61' presumably mean that the 2-part turned out to have precisely three generators. If the groups are normally that small, I wonder if Aoki's strategy of applying the characters afterwards might not be the right way to go.
fivemack is offline  
Old 2009-05-05, 01:09   #19
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·7·132 Posts
Default

The groups typically are that small; most of the time allocating 5 quadratic characters is enough to guarantee that the square root will work correctly, and using more than the (unkown) minimum just uses up dense matrix rows. But that requires that each quadratic character doesn't divide any of the relations, and if you can't assure that then that charater is useless for guarantee purposes.

The only reasons the quadratic characters are computed at the start of the LA instead of the end are 1) the Lanczos code already has to solve a small Gauss elimination problem and that code would have to be duplicated elsewhere, and 2) the relations are already in memory when the LA starts so they don't have to be read again.

Could you print the p and r values inside the for()-loop on line 210 of gnfs/gf2.c, then exit after the loop finishes? This requires restarting the LA from scratch but only running long enough to read the relations from disk. The fact that you got a Newton failure at all, and a number of dependencies approximately equal to (expected number minus number of quadratic characters) all makes me suspect that only one or two quadratic characters are valid.

Last fiddled with by jasonp on 2009-05-05 at 01:23
jasonp is offline  
Old 2009-05-05, 10:41   #20
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default

What do you mean by a quadratic character dividing a relation? I suppose these are quadratic characters chi_p for some rational prime p and the concern is that p shouldn't appear on either side in any relation, which would explain why it was hard to find one having sieved with 32-bit primes on both sides.

In which case, allowing 64-bit p and working down from 2^64 feels as if it ought to be safe for quite a while ... even Dan Bernstein doesn't propose large primes of more than 40 bits! Or is it terribly slow to compute the values of the character for large p?
fivemack is offline  
Old 2009-05-05, 14:09   #21
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·7·132 Posts
Default

64-bit p would definitely solve the problem; I'm reluctant to go that route because msieve only has optimized code to find roots of polynomials with coefficients modulo 32-bit p. The time needed to compute the characters is not a big concern.

Last fiddled with by jasonp on 2009-05-05 at 14:11
jasonp is offline  
Old 2009-06-01, 12:59   #22
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

2×3×29×43 Posts
Default 6,335-

6,335- c170 = p83.p88

37844794094580139581697623770911579688837081742561513466850889366516267662341180891
1327309015857828899623999948822386264843491918815374735541893912578511688338311537475701
R.D. Silverman is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
7+ table garo Cunningham Tables 87 2022-03-25 19:16
5+ table garo Cunningham Tables 100 2021-01-04 22:36
6+ table garo Cunningham Tables 80 2021-01-04 22:33
3+ table garo Cunningham Tables 150 2020-03-23 21:41
5- table garo Cunningham Tables 82 2020-03-15 21:47

All times are UTC. The time now is 11:22.


Thu Oct 6 11:22:07 UTC 2022 up 49 days, 8:50, 0 users, load averages: 1.22, 1.19, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔