mersenneforum.org Amazing!!!
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-24, 16:37 #1 R.D. Silverman     "Bob Silverman" Nov 2003 North of Boston 23×3×311 Posts Amazing!!! In case anyone hasn't noticed, Aoki et.al just set a new record both for NFS size/difficulty and penultimate factor size. They did a 274 digit number. Yes. 274 digits ~ 907 bits.!!!!!!!!! Holy !! So much for our doing 2,857-....... They did 6,353- C274. Fantastic.
2006-01-24, 18:08   #2
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

This is their announcement, from Paul Zimmermann's page:

Quote:
 Date: Tue, 24 Jan 2006 16:05:56 +0900 (JST) Subject: SNFS274 From: Kazumaro Aoki Hello! Factoring people, (Sorry for omitting email addresses due to the privacy law) We are pleased to announce the factorization of the 274-digit(911-bit) number which is labeled as 6,353- in the Cunningham table. We used SNFS to factor it. The factorization is: c274 = (6^353-1)/5 = 97369150518441644256595898307653103810177469944544 60344424676734039701450849424662984652946941878917 94816051886144204066226423206167081784681898063663 68550930451357370697905234613513066631782316112426 01530501649312653193616879609578238789980474856787 874287635916569919566643 = p120 * p155 p120 = 13509526133011265183077504963559080738112103111138 27323183908467597440721656365429201433517381980576 36666351316191686483 p155 = 72074438111130193764393586402902539161389086709970 78170498495662717857340748450948116108762737328670 41786794660514517682420730722427836886613902736846 23521 =====Statistics===== We used the abbreviation k as 10^3, M as 10^6, and G as 10^9. [Polynomial selection] The following polynomial pair was used: algebraic side: f(x) = x^6 - 6 rational side: g(x) = x - 6^59 [Sieving] We started the sieving on September 10, 2005 and completed on November 16. For a small special-Q, the sieving program requires at most 512MB main RAM, it needs 1GB for a larger special-Q. Environment: We used many PentiumIII(1.0GHz) and Pentium4(2.6-3.4GHz) located at Rikkyo University, NTT and Fujitsu Laboratories. Time: Total sieving time is scaled to about 16.6 Pentium4(3.2GHz) years. (also scaled to about 17.3 Athlon64(2.0GHz) years.) We only used lattice sieving. special-Q: only for rational side. 5M < Q < 200M (about 10.7M Qs) factor base bound: about 0.95Q for rational side, 150M for algebraic side large prime bound: 16G for both sides (We set the parameters optimal for 16G and collected the relations with large primes up to 128G) sieve area: 512M points for small special-Q (about 4.9M Qs) 1G points for large special-Q (about 5.8M Qs) sieving rectangle form is dependent on the special-Q Yields: 2 497 019 540 relations Note: 2 large primes were accepted for both sides. [Filtering] Algorithm: partially implemented Cavallar algorithm up to 24-way merge Environment: We used various PCs for each filtering stage. 2 x Opteron 2.0GHz (4GB RAM) are used for the heaviest stage. Time: 14 days (without unused trials using different parameters) 2 497 019 540 raw relations from sieve (including 47 error relations) 2 208 187 490 unique relations 2 576 689 745 effective factor base 15 653 157 # of free relations 84 078 616 relations after singleton and clique operation 84 078 359 its effective factor base [Linear algebra] Input matrix: 19 591 108 x 19 590 832 (total weight 4 498 603 077) Algorithm: block Lanczos with 256-bit block length Environment: 25 x Pentium 4 (3.2GHz) with 2GB RAM and GbE full-duplex located at NTT Time: 34.64 days (without maintenance period) We firstly removed heavy 224 rows from the matrix. The weight was reduced to 3 938 362 368. We started block Lanczos program on December 5, 2005 and finished on January 19, 2006. After we got 256 block Lanczos solutions, we recovered actual 34 solutions. We then adjusted the unit parts of 32 solutions (subset of these 34 solutions) with the help of quadratic characters. Finally, we got 30 quadratic equations modulo c274. [Square root] Algorithm: Nguyen algorithm adjusted for parallel environment Time and Environment: 50 minutes (1 x Pentium 4 [3.6GHz] located at NTT) + 3.2 hours (25 x Pentium 4 [3.2GHz] located at NTT) We found the factor by the 1st solution on January 23, 2006. All programs were written by ourselves. K.Aoki Y.Kida T.Shimoyama H.Ueda
Very impressive indeed!

The next record will probably be the kilobit factorisation. Not much point in putting so much work into it as will be required to beat this and not claim the grand prize. Makes me wonder what Franke et al. are up to...

For the record, the estimated 17.3 years on 2GHz Opteron translates to about 40 days continuous use of our cluster. That would be very hard to justify with the other users.

Alex

Last fiddled with by akruppa on 2006-01-24 at 18:16

2006-01-25, 19:19   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts

Quote:
 Originally Posted by akruppa This is their announcement, from Paul Zimmermann's page: Very impressive indeed! The next record will probably be the kilobit factorisation. Not much point in putting so much work into it as will be required to beat this and not claim the grand prize. Makes me wonder what Franke et al. are up to... For the record, the estimated 17.3 years on 2GHz Opteron translates to about 40 days continuous use of our cluster. That would be very hard to justify with the other users. Alex

Alex,

Why not put grid computing software on your cluster? You can now set up
sieve jobs so they run only when nothing else is running (or the load is
sufficiently small)? The grid software would automatically submit sieve
ranges to machines as they become available. If a machine becomes
busy while a job is in progress it is put to sleep.

2006-01-25, 19:45   #4
Chris Card

Aug 2004

22×3×11 Posts

I'm trying to understand this bit:
Quote:
 Originally Posted by aoki et al After we got 256 block Lanczos solutions, we recovered actual 34 solutions. We then adjusted the unit parts of 32 solutions (subset of these 34 solutions) with the help of quadratic characters.
Does this mean that the matrix solved by block Lanczos didn't include the quadratic character columns, and that the solutions to this matrix were combined to give solutions to the matrix extended by the qc columns?
I can see how that might work, but I don't see how you would be guaranteed that any combinations of the solutions of the unextended matrix would be in the null space of the extended matrix unless you have more solutions than quadratic characters.
I guess I'm missing something here.

Chris

2006-01-26, 01:59   #5
jasonp
Tribal Bullet

Oct 2004

5×709 Posts

Quote:
 Originally Posted by Chris Card I'm trying to understand this bit: Does this mean that the matrix solved by block Lanczos didn't include the quadratic character columns, and that the solutions to this matrix were combined to give solutions to the matrix extended by the qc columns? I can see how that might work, but I don't see how you would be guaranteed that any combinations of the solutions of the unextended matrix would be in the null space of the extended matrix unless you have more solutions than quadratic characters.
Once you find the wide nullspace vector, solving for the rows ignored by the main run is a gauss elimination problem.

I've never seen it done in code, though, so it's probably trickier than I'm making it out to be.

jasonp

2006-01-26, 09:14   #6
Chris Card

Aug 2004

100001002 Posts

Quote:
 Originally Posted by jasonp Once you find the wide nullspace vector, solving for the rows ignored by the main run is a gauss elimination problem. I've never seen it done in code, though, so it's probably trickier than I'm making it out to be. jasonp
I agree it's Gaussian elimination problem.
Suppose we start with an m x n matrix X (m relations, n primes, with m > p), and we find some of the null space, i.e. an s x m matrix B with BX = 0.
To find the solutions we want we have to extend X with q quadratic character columns, i.e. an m x (n + q) matrix X' = (X Q).
Then BX' = (0 BQ), so we want to find an r x s matrix C such that
CBX' = (0 CBQ) = 0, i.e. C(BQ) = 0.
The matrix BQ is s x q (a small matrix, easy for Gaussian Elimination), so to guarantee a non-trivial solution to C(BQ) = 0 we must have s > q.
aoki et al don't say how many quadratic characters they use, but if their 34 "actual" solutions correspond to B, then q would have to be < 34, which seems unlikely.
However, I reckon they must have done something more subtle, so can anyone explain what they meant by "actual 34 solutions" and "adjusted the unit parts" please?

Chris

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 08:56.

Sat Aug 13 08:56:37 UTC 2022 up 37 days, 3:43, 2 users, load averages: 0.97, 1.12, 1.12