Amazing!!!

[R.D. Silverman]

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.

[akruppa]

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

Date: Tue, 24 Jan 2006 16:05:56 +0900 (JST)
Subject: SNFS274
From: Kazumaro Aoki <maro@isl.ntt.co.jp>

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

[R.D. Silverman]

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.

[Chris Card]

I'm trying to understand this bit:

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

[jasonp]

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

[Chris Card]

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