2^772+1 has started
 

Since about 11pm on 25th January, my machine's been sieving on 2^772+1.

So I guess we'll see the factors of 10^229+1 around the end of February.

I notice that people seem to be doing the linear algebra on dual-G5 systems; is the code multi-threaded, or are G5 systems just convenient platforms in which to put enough memory to fit an SNFS matrix?

Once I've convinced Mastercard to smite appropriately the supplier of the Kentsfield system I bought whose PSU exploded after three hours' operation, and who took the machine back and refunded me the price of the PSU (I'm guessing end February for this) I'll have a Kentsfield (quad Core2 2.66GHz); I'd be happy to run LA or filtering on it if it's a useful platform for that, though I appreciate that filtering seems more to require knowledge of the black arts than pure gigaops.

[QUOTE=fivemack;97432]Since about 11pm on 25th January, my machine's been sieving on 2^772+1.

So I guess we'll see the factors of 10^229+1 around the end of February.[/quote]
It's possible, but it would be a rush.

[QUOTE=fivemack;97432]I notice that people seem to be doing the linear algebra on dual-G5 systems; is the code multi-threaded, or are G5 systems just convenient platforms in which to put enough memory to fit an SNFS matrix?[/QUOTE]
"People" in this context is Richard Wackerbarth. I'm using a single-cpu AMD64 3500+ to run linear algebra for NFSNET. The machine is currently about 30% through the matrix for 5,313+ and it should finish in about a week.

The choice of systems is dictated by what we own. It turns out that my box is markedly faster than Richard's for reasons we don't really understand. My guess is that the SSE2 instructions are particularly effective.

[QUOTE=fivemack;97432]Once I've convinced Mastercard to smite appropriately the supplier of the Kentsfield system I bought whose PSU exploded after three hours' operation, and who took the machine back and refunded me the price of the PSU (I'm guessing end February for this) I'll have a Kentsfield (quad Core2 2.66GHz); I'd be happy to run LA or filtering on it if it's a useful platform for that, though I appreciate that filtering seems more to require knowledge of the black arts than pure gigaops.[/QUOTE]
Thanks for the offer. We may well take you up on it.

We'd need to know what OS you'll be running (Linux would be by far the easiest for us, hint, hint :smile: ) and how much memory it has. Unfortunately, linear algebra in particular uses a [b]lot[/b] of memory and at least 2G RAM is needed for the matrices we're now doing. My system has 2.5G and Richard's 4G, I believe.



Paul

I originally ordered the machine with 2G, once I've got my money back I'll order a 4G system. It doesn't seem possible to put more than 4G into an Intel single-socket system (only four slots, and 2GB DDR2 DIMMs appear not to exist), but 4G ought to suffice.

It will run Linux, probably Ubuntu since Canonical seem to have hired half the Cambridge geeks of my acquaintance as Ubuntu developers.

I assume that the linear algebra is done on 128 bit-vectors in parallel using SSE2, so the large Core2 caches aren't going to fit the whole V ... I assume the linalg does all the obvious tiling optimisations so it tries to stay within cache, I don't know how nicely that'll work in the two-shared-caches environment. Will be interesting to find out.

[is the linear algebra routine available as source-code, or is it more tightly licensed like the linesiever executable?]

Ah, I'd inadvertently selected a 'show only affordable memory' option; Crucial [I]can[/I] sell me 2GB DDR2 DIMMs, but they cost four times as much as 1GB DIMMs, and my budget is finite.

[QUOTE=fivemack;97432]Since about 11pm on 25th January, my machine's been sieving on 2^772+1.

[/QUOTE]

What's the current status?

What's next?

Bob,

We are currently nearing 50% of the sieving on 2,772+. It is projected to run until mid June since the U Gent computers are presently busy on another computation and expect to remain so until some time this Summer.

As a result, I have not worried about "what's next" to any great extent.
I know that Paul and Bruce have discussed some possibilities taking Bruce's ECM work into account.

Richard

[QUOTE=Wacky;101653]Bob,

We are currently nearing 50% of the sieving on 2,772+. It is projected to run until mid June since the U Gent computers are presently busy on another computation and expect to remain so until some time this Summer.

Richard[/QUOTE]

Would it be useful for me to run some lattice sieving on 2,772+ (what's the polynomial and the rat/alg bounds?), or would that contend unhelpfully with the line-sievers?

[QUOTE=fivemack;104121]Would it be useful for me to run some lattice sieving on 2,772+ (what's the polynomial and the rat/alg bounds?), or would that contend unhelpfully with the line-sievers?[/QUOTE]

There would be some duplication, but the exact amount would be
almost impossible to predict in advance. I believe that it would be
useful.

next number candidates?
 

[QUOTE=Wacky;101653]We are currently nearing 50% of the sieving on 2,772+. It is projected to run until mid June since the U Gent computers are presently busy on another computation ...

As a result, I have not worried about "what's next" to any great extent.
I know that Paul and Bruce have discussed some possibilities ...[/QUOTE]

Not sure that an email or two qualifies as a continuing discussion, but
among the available More Wanted numbers I reported

[QUOTE]Maybe some of the base-6 or base-7's? [Paul's] surely
familiar with 6,283- (having done the +), fairly easy at 220;
and 6,284+ also easy at 221. We could clean those up.

There are/were four base-7's; 222.26, then -- ah, there's
7, 269- at 227.33 perhaps in the right range? --- and 7,271-
right nearby at 229 --- then 7,268+ at 226.49. All four seem
to still be on the ecmnet input file; any of these look OK? [/QUOTE]

Any interest in these; or alternate suggestions that ought to be
considered? The current number has difficulty 233, which seems to
have been a bit long without the Gent cpus. The wanted/most_wanted
base-2s seem to be harder yet (and will move up on the list to be
more attractive on the next list); we finished the base-5s; and the
remaining base-10s also look harder. [cf. 10,239+/- at (233 -vs 239);
likewise 10,236+ (236), with 10,232 at 232.] -Bruce

[QUOTE=bdodson;105694]Not sure that an email or two qualifies as a continuing discussion, but
among the available More Wanted numbers I reported



Any interest in these; or alternate suggestions that ought to be
considered? The current number has difficulty 233, which seems to
have been a bit long without the Gent cpus. The wanted/most_wanted
base-2s seem to be harder yet (and will move up on the list to be
more attractive on the next list); we finished the base-5s; and the
remaining base-10s also look harder. [cf. 10,239+/- at (233 -vs 239);
likewise 10,236+ (236), with 10,232 at 232.] -Bruce[/QUOTE]

The remaining numbers under 768 bits are:

5,317-, 323-
6,283-
284+, 292+
7,263-, 269-, 271-
268+

[QUOTE=R.D. Silverman;105708]The remaining numbers under 768 bits are:

5,317-, 323-
6,283- 284+, 292+
7,263-, 269-, 271- 268+[/QUOTE]

Six of these nine numbers are the ones I referred to in my post; these
being the base-6 and base-7 ones on the current More Wanted list.
We've already done four base-5's; other things being equal (such
as ease of polyn and sieving range estimation; snfs difficulty),
Cunningham etiquette suggests wanted numbers before unwanted
(even just not-quite-yet wanted ones), yes? That's two of your
nine that I didn't mention (the base 5s), the third one being 6, 292+.
If this were an issue of a vote, I'd vote to pick from the six ones on
the Selfridge-Wagstaff list first, then the other three.

In any case, neither six nor nine is the correct order of magnitude;
the intended question is which two numbers ought to be done next
(three, maybe if the Gent cpus return). In terms of ecm pretesting,
four of the "wanted six" have already had 2*t50, which is the level
I've been working to (since Bob's 6,281- c162 with three factors in
ecm range). Looks like it wouldn't hurt to take the two large base-7's
early (as they're already in the Opteron queue).

Any other suggestions from c190-c233, difficulty 220-229.9, that seem
plausible candidates to be one of the next three? The base-5s are already
done (to 2*t50). I can also do the large base-6 early (just on case
someone decides on that one? Or to see to larger likelihood that it's
going to need sieving, also). There, that covers Bob's new suggestions.
Any others? And which 2-3 should be next (any other candidates?).
-Bruce

[QUOTE=R.D. Silverman;105708]The remaining numbers under 768 bits are:

5,317-, 323-
6,283-
6,284+, 292+
7,263-, 269-, 271-
7,268+[/QUOTE]

The "current" info in my previous post seems to have been a few
months out-of-date, at least relative to hard-copy (or perhaps a
needed cache clearing). Reflecting post-NFSNET base-5 factors,
5, 317- is now 7th on the Most wanted list and 7, 263- is 8th.
The others are also Wanted, except that 6, 283- has been reserved ---
that would be for NFSNET's next.

All of these have had ecm pretests to 2*t50, and checking for factors
by snfs is a lot cheaper than checking ecm pretests on gnfs candidates
(three of these nine are over 200-digits, the smallest ones are
161- 168- and 173-digits; missing a p55 may be tolerable for a
difficulty 220-229 snfs, perhaps for .66*225 = 150 gnfs; but we're
accumulating a collection larger gnfs candidates. Of course, the new
state-of-the-art is 53.2% chance of missing a p70, which translates
into c. t68; or as reported elsewhere, over 3*t65 ... that's for
.66*312 = c208? Translation seems a bit off, believe I heard a
rough equivalent to 700-bit gnfs, which would be 210.7-digits;
close enough ...) OK, three of these nine give a Much cheaper
snfs model for state-of-the-art gnfs difficulty; while even the smaller
composites are measurably above current Smaller-but-Needed size,
if gnfs is the quicker choice (over snfs).

Admittedly, a rather bizarre reason; unlikely to sustain anyone through
several months of computation. Pending continued progress on getting
minimal-stats back up, tracking a larger scale sieving collaboration is
probably a more viable objective. Wonder how many of the c. 800
Cunninghams have snfs difficulty under 300, and how many have already
been sufficiently factored to have gnfs be the method of choice. I'm
still working on an updated view of the 2- list, n < 1200. -Bruce

PS - If M1061 is back on our list of un-spoken-for numbers, and the
M1039 ecm pre-test is an even moderately plausible standard, then
finishing t60 (another 33000 curves at b1=260M?) would seem to be
Very conservative. At difficulty 320, M1061 is nearly twice as hard.
Just meeting the 3*p65 standard used for M1039 would be
3*(70,000); over 200K curves with B1=850M. Still seems to me that
running t55's on the 2- numbers of difficulty above 230, say with
unfactored part above .66*234 = c156 is more likely to find a factor.
Depending upon whether one's ecm objective is finding factors,
versus ecm pre-testing near-term sieving candidates, versus ecm trophy
hunting (on other people's longer-term sieving candidates, or numbers
like Alex's F31, way-out of sieving ... err, gnfs_sieving/snfs_sieving range).

Did you sieve the small factors?

[QUOTE=VolMike;109001]Did you sieve the small factors?[/QUOTE]

Huh?

2^772+1 has 2 small factors:17 and 43464340002838801.
Thus 2^772+1 should be divided on them and then the quotient should be tested by GNFS algorithm.So does GNFS implementation which you use eliminate by dividing these 2 small factors?

[QUOTE=VolMike;109004]2^772+1 has 2 small factors:17 and 43464340002838801.
Thus 2^772+1 should be divided on them and then the quotient should be tested by GNFS algorithm.So does GNFS implementation which you use eliminate by dividing these 2 small factors?[/QUOTE]

Your assumptions are wrong.

(1) 2^772+1 is not being done via GNFS, but by SNFS.
(2) The small prime factors of 2^772+1 are irrelevant.

I see
Thus SNFS applied to 2^772+1 returns results faster then GNFS applied to quotient.

[QUOTE=VolMike;109004]2^772+1 has 2 small factors:17 and 43464340002838801.
Thus 2^772+1 should be divided on them and then the quotient should be tested by GNFS algorithm.So does GNFS implementation which you use eliminate by dividing these 2 small factors?[/QUOTE]

Yes, there are "small factors" that are removed at the appropriate time, whether doing SNFS or GNFS.

However, in a case such as this where the product of the known factors is still only a very small portion of the total number, SNFS will give sufficiently smaller polynomial coefficients that ignoring the known factors will produce relations significantly faster than the best general polynomial which takes them into account.

(It looks as if Bob was saying the same thing while I was composing my response)

[QUOTE]Yes, there are "small factors" that are removed at the appropriate time, whether doing SNFS or GNFS.

However, in a case such as this where the product of the known factors is still only a very small portion of the total number, SNFS will give sufficiently smaller polynomial coefficients that ignoring the known factors will produce relations significantly faster than the best general polynomial which takes them into account.

(It looks as if Bob was saying the same thing while I was composing my response)[/QUOTE]
Thanks for your explanation.
As I see, factorization is not completed?

On 6/14, Paul reported that he was starting the solution of the 5.6M square matrix that he was able to produce. He estimated that that phase would take 19 days. His estimates are usually quite good.

[QUOTE=VolMike;109010]Thanks for your explanation.
As I see, factorization is not completed?[/QUOTE]The linear algebra is progressing nicely. At the moment, it is roughly 3.38/5.54, or 61%, completed. When it has finished, a few hours more will suffice to find the factors.

As Wacky said, the linear algebra started on 14th June. Perform the extrapolation yourself.

Paul

Ok. I understand. Approximately 1 week left.

[QUOTE=R.D. Silverman;101628]What's the current status?[/QUOTE]

Sieving on 6,283- has now reached 67%. At the current production rate, we should finish about July 9.

However, note that a significant number of the sievers are "without supervision" for much of that time. As a result, we may lose their service at any time and not have it restored for some days.

As a result, I would suspect that the projected date is "optimistic".

Out of curiosity, what's the weight of the matrix (after removing the dense rows) for 2+772? Presumably less than 2^29, since it fits in xilman's machine which IIRC has 2GB.

[QUOTE=fivemack;109459]Out of curiosity, what's the weight of the matrix (after removing the dense rows) for 2+772? Presumably less than 2^29, since it fits in xilman's machine which IIRC has 2GB.[/QUOTE]443M set bits after removing the heaviest rows.

Only 200K vectors to go now (out of 5.54M) so should be finished in a day or so.

My machine has 2.5G RAM and the extra 0.5G allows the machine to run other things, such as an operating system, without paging itself to a standstill when running a 2G AVM process. The Lanczos process is taking 1989M AVM and yet the machine is still very responsive as long as long as I don't fire up anything that requires a lot of memory.


Paul

I'm not sure why Paul hasn't posted it here, but Wagstaff is showing the result for 2^772+1 at

[url]http://homes.cerias.purdue.edu/~ssw/cun/page105[/url]

c215 = p107 * p108, a very nice split.

[QUOTE=PBMcL;109747]I'm not sure why Paul hasn't posted it here, but Wagstaff is showing the result for 2^772+1 at

[url]http://homes.cerias.purdue.edu/~ssw/cun/page105[/url]

c215 = p107 * p108, a very nice split.[/QUOTE]Because I'd asked Wacky to do so.


Paul

[QUOTE=xilman;109749]Because I'd asked Wacky to do so.
Paul[/QUOTE]

In fairness, there was a response to Paul's request for
"appropriate announcements to the NFSNET people". Factoring
announcements from all of the other factoring groups include,
not just the matrix and square-root information (the factors!), but
some info on the sieving. On the last several NFSNET factorizations
some two thirds of the relations were found on machines at the
Univ of Gent and at Lehigh. The Gent machines were busy elsewhere
for most of the sieving for 2,772+, so that (perhaps) half of the
relations were found at Lehigh.

I've been suggesting that the official record in the text acompanying
Sam's pages ought to reflect these institutional contributions. I'd
actually be somewhat happier if the first report anyone outside of
NFSNET sees of our factors included everyone supplying 3% or more
of the sieving, for motivation of our contributors, if nothing else. So
the delay in the report may be more my fault than Richard's.

On news of more general interest, sieving for 6, 283- seems near to
being done (early, due to the return of the Gent machines). In particular,
today's project files have started the sieving on the next NFSNET number,
5,317-. As has been our recent practice, polynomials and sieving
parameters are due to Paul, while Richard does the part of filtering
that prunes the data for file transfer. Matrix building (with final merges
in the filtering) is usually done by the person running the matrix; so Paul
for 2,772-.
-bdodson (very glad to have these c10x prime factors out of the
ecmnet/cunningham queue!)