6^383+1 by GNFS is complete. Thanks!

[smh]

so the msieve.fb file will look like this?

N 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489
R0 -7253635851193924156735160443739
R1  2391424041494417171
A0  547440910672314203689898814059115360
A1  33277562211750204806364306268284
A2  107677876784557388243547221
A3 -2612363701552248486716
A4 -3795305047120954
A5  11472718320

FRNUM 3001134
FRMAX 49999991
FANUM 3001126
FAMAX 49999991
SRLPMAX 1073741824
SALPMAX 1073741824
SLINE 10000000000

And sieving will be done with:

msieve -ns x,y

where x and y can be used to sieve on multiple cpu's?

Will this produce significantly more relations compared to lattice sieve with a special q > 120M?

[fivemack]

Originally Posted by smh

so the msieve.fb file will look like this?

And sieving will be done with:

msieve -ns x,y

where x and y can be used to sieve on multiple cpu's?

Will this produce significantly more relations compared to lattice sieve with a special q > 120M?

I think you want the S*LPMAX lines to be 2147483648 (2^31) rather than 2^30.

I am running b=1 to 2 at the moment with those parameters, on a P4/3000 which we keep lying in the corner at work. msieve took ~700MB to set up and is running at ~140MB with 'sieving in progress'. It would be very nice to have some kind of progress report beyond 'sieving in progress', particularly since msieve doesn't write relations to files at anything like a uniform rate.

After 36 minutes it had found 1200 relations and wasn't close to completion, as opposed to ~6000 from gnfs-lasieve4I14e on 120M-121M in the same time, so it's a lot slower than the lattice code. My model is that you do line-sieving only to find relations so good that they don't show up in lattice sieving - once it's completed I need to check how many of the relations have an algebraic-side factor between 25M and 140M and so would have been found in the lattice process.

My initial thought is that probably the lines are far too long and a=-1e9 to 1e9 would be more sensible.

[jasonp]

Originally Posted by fivemack

It would be very nice to have some kind of progress report beyond 'sieving in progress', particularly since msieve doesn't write relations to files at anything like a uniform rate.

That output currently happens when switching from one line to the next, which takes forever with b=1 :) I think you're right, the 'a' range needs to be a lot smaller. Relations are batched because a lot of people had trouble with early msieve versions corrupting the relation file

[fivemack]

I am a little confused at the msieve output.

The terminal has said

b = 1, 10671 complete / 442937 batched relations (need 82617706)
b = 2, 16106 complete / 355153 batched relations (need 82617706)
completed b = 2, found 17005 relations
elapsed time 02:53:48

It would be very nice if the progress messages had time-stamps.

The output file has 11921 relations with b=1, 3660 of which would not have appeared from the lattice sieving (IE have no algebraic-side prime factor between 25e6 and 140e6); of those 3660, 1995 had A between -1e9 and 1e9, so the extra ten-fold A range gets you only twice the yield. 940 have A between -1e8 and 1e8.

Also it has 5084 relations with b=2, 1551 of which would have been missed by lattice sieving. So the total number of relations is right, but the '#### complete' messages don't particularly correspond to the output file.

I presume that this is because Bernstein-like batched factorisation buffers do not get flushed at the end of each b, but only at the end of each job, so the extra 1250 relations from B=1 were in the buffer but had not yet been processed at the time B=1 stopped and the stats were printed.

Conclusion It might be sensible to run [-2e8, 2e8] x [1,1000] to get some low-hanging fruit, and indeed I have set that running on a machine here. Otherwise just hammer away with lattice sieving. Three hours to get 18000 relations, 6000 of which are novel, doesn't seem a great use of resources.

[jasonp]

Relations with <= 1 large prime on both sides are output immediately to the savefile, while anything else is buffered. Buffered relations are batch-factored whenever 500k of them have accumulated, or sieving is about to finish, so it's possible to have big piles of relations added at odd times. Especially for larger b, it saves a lot of time to postpone batch factoring until several lines have been sieved.

I agree that it isn't worth spending much time on line sieving. At 2 relations per special-Q, based on the sticky above, would 9000 special-Q really have taken only an hour?

[fivemack]

At 2 relations per special-Q, how long would 9000 special-Q have taken?

I'm getting through 110 special-Q per CPU-minute, so around 80 minutes ... and, whilst there is duplication among lattice-sieved relations, I don't think it's bad enough for only 30% of them to be usable.

[jasonp]

Okay, I suppose that reducing the line size would improve the time per relation to approximate parity with the lattice siever. Too bad that the first 1000 lines wil probably yield only around 100k relations. I guess there's no doubt now that lattice sieving is the wave of the future. It makes me wonder if batch factoring can be profitably applied applied to the GGNFS tools.

[fivemack]

With lines -2e8 to 2e8, I got 41000 relations in an hour, which is rather faster than the lattice siever offers; that's for b=1..35, I'm not quite sure what the form of the fall-off of relation count with B is, but I'm hoping for a million relations in a bit over a day, perhaps 300k of which will be non-duplicate. Nothing to sniff at.

actual result:
sieving in progress (press Ctrl-C to pause)
b = 1000, 650403 complete / 145362 batched relations (need 82617706)
completed b = 1000, found 653421 relations
elapsed time 24:44:51

In comparison, 20 hours lattice-sieving at Q=120M on a faster computer found 211227 relations; so we find a lot of relations very quickly by line-sieving near the origin, but lattice sieving drops off slower.

Is there any way of telling msieve to use A=-5e8 to -2e8, so we can partition AB space into rectangles which aren't the whole width of the axis long?

[jasonp]

Originally Posted by fivemack

Is there any way of telling msieve to use A=-5e8 to -2e8, so we can partition AB space into rectangles which aren't the whole width of the axis long?

Not by default. The following patch file aginst v1.32 adds that capability, just add a SMIN or SMAX line below, or in place of, SLINE within the factor base file.

[fivemack]

As of last night, we have 131051159 relations, 115239485 unique. So we're about two thirds of the way there.

[Andi47]

Originally Posted by Andi47

Just a little statistics:

Update:

relations found so far:                145,956,989
relations found with 14e siever:       133,379,478
completed size of search range:        109 million Q
search range with 14e siever:          104 million Q
Relations per Q (average, 14e siever): 1.778

Range          Size        Relations     Relations/Q
 25M - 28M      3M         12577511      4.192   *with 15e siever
 30M - 55M     25M         49516175      1.981
 55M - 60M      5M          9739894      1.948
 67M - 70M      3M          5513489      1.838
 72M - 75M      3M          5386758      1.796
 75M - 80M      5M          8814348      1.763
 86M - 100M    14M         23176554      1.655
100M - 120M    20M         31232260      1.562