Msieve / lattice siever with degree 7/8 poly

[Batalov]

Just out of curiosity and a proof-of-concept I made a small factorization with a septic polynomial. Not a stinky septic , a seventh degree poly (added for the forum search engine purposes). Notably, for this number this was a highly suboptimal poly. Septics might be marginally useful somewhere in the future.

A few trivial code changes are easily added to gnfs/ffpoly.c and gnfs/poly/polyutil.c in msieve (patch attached). And in the Kleinjung/Franke siever code just find '6' and replace by '7' in input-poly.c.

As well as it could have been expected, everything worked.

Number: 79999_112
SNFS difficulty: 112 digits.
Divisors found:
r1=10422340853038410236015043584682186702615256189871 (p50)
r2=86245155207367245150415449691190682483270759676962191576656921 (p62)
Version: Msieve v. 1.38
Scaled time: 0.00 units (timescale=2.941).
Factorization parameters were as follows:
n: 898876404494382022471910112359550561797752808988764044943820224719101123595505617977528089887640449438202247191
# = 79999...9999 / 89
# = (8.10^112-1) / 89
Y1: 1
Y0: -10000000000000000
c7: 8
c0: -1
skew: 1
type: snfs
Factor base limits: 600000/800000
Large primes per side: 3
Large prime bits: 25/25
Max factor residue bits: 46/46
Sieved algebraic special-q in [400000, 1300001)
Primes: rational ideals reading, algebraic ideals reading, 
Relations: 2.2M relations 
Max relations in full relation-set: 
Initial matrix: 
Pruned matrix : 148020 x 148268
Total sieving time: 0.00 hours.
Total relation processing time: 0.00 hours.
Matrix solve time: 0.00 hours.
Time per square root: 0.00 hours.
Prototype def-par.txt line would be:
snfs,112,7,0,0,0,0,0,0,0,0,600000,800000,25,25,46,46,2.4,2.4,50000
total time: 0.00 hours.
--------- CPU info (if available) ----------
Memory: 33030820k/34078720k available (1920k kernel code, 522988k reserved, 885k data, 196k init)
Calibrating delay using timer specific routine.. 5609.80 BogoMIPS (lpj=11219618)
#...
using 32 quadratic characters above 33553658
building initial matrix
memory use: 64.6 MB
read 149220 cycles
matrix is 148964 x 149220 (45.0 MB) with weight 14401141 (96.51/col)
sparse part has weight 10151407 (68.03/col)
filtering completed in 3 passes
matrix is 148068 x 148268 (44.8 MB) with weight 14328356 (96.64/col)
sparse part has weight 10105939 (68.16/col)
read 148268 cycles
matrix is 148068 x 148268 (44.8 MB) with weight 14328356 (96.64/col)
sparse part has weight 10105939 (68.16/col)
saving the first 48 matrix rows for later
matrix is 148020 x 148268 (42.4 MB) with weight 11011942 (74.27/col)
sparse part has weight 9644544 (65.05/col)
matrix includes 64 packed rows
using block size 43690 for processor cache size 1024 kB
commencing Lanczos iteration
memory use: 38.6 MB
linear algebra completed 147720 of 148268 dimensions (99.6%, ETA 0h00m) 
lanczos halted after 2342 iterations (dim = 148018)
recovered 48 nontrivial dependencies
elapsed time 00:04:28
=>nice -n 19 msieve -s 79999_112.dat -l ggnfs.log -i 79999_112.ini -v -nf 79999_112.fb -t 1 -nc3
 
Msieve v. 1.38
Thu Sep 25 15:11:13 2008
random seeds: eaf2e21a 00142c80
factoring 898876404494382022471910112359550561797752808988764044943820224719101123595505617977528089887640449438202247191 (111 digits)
searching for 15-digit factors
commencing number field sieve (111-digit input)
R0: -10000000000000000
R1: 1
A0: -1
A1: 0
A2: 0
A3: 0
A4: 0
A5: 0
A6: 0
A7: 8
size score = 3.531074e-04, Murphy alpha = 0.845874, combined = 2.858033e-04
commencing square root phase
reading relations for dependency 1
read 74127 cycles
cycles contain 310407 unique relations
read 310407 relations
multiplying 248202 relations
multiply complete, coefficients have about 5.28 million bits
initial square root is modulo 1190029
prp50 factor: 10422340853038410236015043584682186702615256189871
prp62 factor: 86245155207367245150415449691190682483270759676962191576656921
elapsed time 00:01:09

P.S. of course, I won't be surprised if it had been done before.

--Serge

[jasonp]

Originally Posted by Batalov

Just out of curiosity and a proof-of-concept I made a small factorization with a septic polynomial. Not a stinky septic , a seventh degree poly (added for the forum search engine purposes). Notably, for this number this was a highly suboptimal poly. Septics might be marginally useful somewhere in the future.

...

P.S. of course, I won't be surprised if it had been done before.

Not to my knowledge, thanks for the patch.

[Batalov]

Actually septic polynomials are rather useless, so why not just extend to octics? Octics naturally come out from a lot of algebraic factorizations (10LM, and some L/Ms divided a smaller L/M, etc, etc); septics - never.

Octic patch is attached. (There was also a typo in the previous patch.)
I am rerunning the same toy number with an octic overnight, just looking for errors.

For the siever code: one needs to increase the size of the *A and *B arrays (from 8 to 9), not just change '6' to '8' a few lines below this chunk, obviously...

  *A = xmalloc(9*sizeof(**A)); /* plenty o' room. */
  *B = xmalloc(9*sizeof(**B));
  for (i=0; i<9; i++) {
    mpz_init_set_ui((*A)[i], 0);
    mpz_init_set_ui((*B)[i], 0);
  }
//...
      } else if ((token[0]=='c') && (token[1] >= '0') && (token[1] <= '8')) {
        mpz_set_str((*A)[token[1]-'0'], value, 10);
        *adeg = MAX(*adeg, token[1]-'0');
      } else if ((token[0]=='Y') && (token[1] >= '0') && (token[1] <= '8')) {
        mpz_set_str((*B)[token[1]-'0'], value, 10);
        *bdeg = MAX(*bdeg, token[1]-'0');

--Serge

[miklin]

Originally Posted by jasonp

Not to my knowledge, thanks for the patch.

I here too have not understood a trick of this plot.
But here I have too supervision can certainly not on a theme.
If to return to primary source GGNFS.
The situation following a polynom under different systems windows and linux different result, also is all with the same code.
Thus on Linux result correct. It is easy for checking up on an example which to be in GGNFS Example.
Also we will receive different results.
And if still to take as well to try a polynom from a folder Experimental that result also differs from Linux.
I can give set of keys Rsa154 (real and not beaten) and so to receive a polynom for many of them very difficult.

RSA512:

N 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897

We assume that a file rsa512.data exists. The following should produce a
good polynomial for this number:

$ ./pol51m0 -b rsa512 -v -v -p 7 -n 6e22 -a 28000 -A 29000
Parameters: number: 1.094e+154, norm_max: 6.000e+22, a5: 2.800e+07 - 2.900e+07
Accected a5-range: 1.000000 - 123897297399046.968750 
Searching in subinterval: 28000020 - 29000000
..........................28172400 207899046817573037944003980721 1431689581421081
490457424114402 207899046817571298429701341940
......28200000 207858335743926583066618629796 14507315380338583
2513405668036628 207858335743889845727447842295
.............................................................................................................28788360 207001685830582539787623092532 277876585108001
67319283658787 207001685830581576549075927732
..................................Statistics:
a5-values: 16673, suitable for 7 primes: 3913
raw checks of (a5,p): 1945962 (1089573),  fine checks of (a5,p): 0
polynomials computed: 547,  survivors: 3
Total number of checked polynomials: 152028281250
success

--------------------------------------
This should have taken around 3 minutes on an 1GHz PIII.
Now a file rsa512.51.m containing the lines:
28172400 1431689581421081 207899046817573037944003980721
28200000 14507315380338583 207858335743926583066618629796
28788360 277876585108001 207001685830582539787623092532
should have been created. After:

$ ./pol51opt -b rsa512 -v -v -n 5e21 -N 2e19 -e 2e-12
28172400 137407314866185 -95421350700438998987 -146557736431495680250776677 40051849155435036583483365067795 20635075642866534027509737103227346009 
1431689581421081 207899045420998506886437834408

area: [-1003520,1003519]x[-100,100]
norm: 1.051e+22  alpha_proj: -1.635  skewness: 825977.864
limit: 8.832998, lim0: 50.707062   cut: 8833
.........................................................................................................................................................................................................28200000 -32490562539851 -9988621726698864150 3602085041663164063242149 441712338043438681590088699558 -52709848224323990818583861168440497 
14507315380338583 207858339086847266158038310486

area: [-1003520,1003519]x[-100,100]
norm: 4.982e+20  alpha_proj: -1.290  skewness: 265718.305
limit: 6.128939, lim0: 47.657574   cut: 6129
..................................................................f...............ffffPff.......f..f.....ff.ffPffffffffffffffffffffffff.ffPfff.fffff.fffffffffffffffff.ffff.fffffPfffffffffffffffffffffffffffPfffffffPfPfffffPffffffffPffffffffffffffffffffffffPffffffffffffffffffPfffffffffffffffffffffffffffffffffffffPffffPffffPfffPfffffffPfffffffffffffffffffffffffffffffffffffffffffffffPfffffffffffffffffffffffffffffff.fffffffffff.fPff..ffffPffffPff....f..Pf..........................................................................................28788360 -38461665456103 341536155051745850040 302940605370508202796022 -1145741667441318786745339894842 -301776673333039763066096285541808 
277876585108001 207001685904831996958236283735

area: [-480658,477805]x[-7,100]
norm: 7.031e+21  alpha_proj: -1.142  skewness: 63688.236
limit: 8.923309, lim0: 50.304673   cut: 8923
............................................................................................................

------------------------------------------
(ca. 4min on 1GHz PIII) a file rsa512.cand with 21 polynomial should exist. 
Among them:
BEGIN POLY #skewness 316769.74 norm 7.82e+20 alpha -5.04 Murphy_E 2.55e-12
X5 28200000
X4 -28360813539851
X3 -13553173634695647906
X2 2564268902978149419168456
X1 415989256480951014687269907996
X0 -28294692934494412681458239834080920
Y1 14507315380338583
Y0 -207858338661942505983301552999
M 3360535699488068065188616076918604440700798249780305704017974532022544629934677045714592688052709846153098285633372058200144914970580706639105648340708817
END POLY

Sergey Miklin

[xilman]

Originally Posted by Batalov

Actually septic polynomials are rather useless, so why not just extend to octics? Octics naturally come out from a lot of algebraic factorizations (10LM, and some L/Ms divided a smaller L/M, etc, etc); septics - never.

Because they are hopelessly inefficient for numbers of the size presently amenable to SNFS.

Exercise: for an integer from one of the classes you describe, with SNFS difficulty 300 digits or under, compare the norms of the linear and octic sides for a typical sieving point. Post your results here.


Paul

[Batalov]

Yes, it is true; I know what you mean. They are inefficient at least until 250+ (septics) and 300+ (octics). At least.

What I was trying to say was "why not extend the code to octics if we are adding septics, in one sweep". Just wanted to see (and tested) that it works, even though quite slow, but nothing breaks. Not that either addition could be used every day. I've looked at a lot of numbers in the Appendix C that will not benefit from either of these. There's an awful lot of quartic candidates there; I was just thinking that anything might be better than a quartic.

I think quartics should be renamed into yech septics.

[jasonp]

Originally Posted by miklin

I here too have not understood a trick of this plot.
But here I have too supervision can certainly not on a theme.
If to return to primary source GGNFS.
The situation following a polynom under different systems windows and linux different result, also is all with the same code.
Thus on Linux result correct. It is easy for checking up on an example which to be in GGNFS Example.
Also we will receive different results.

The polynomial selection is sensitive to roundoff error and the level of optimization used when compiling. pol51m0b will not work if you compile with optimization and use the assembler code; other systems (64-bit etc) cannot use the assembly code at all, but will work if you compile with optimization. That is what generates different results.

I have also experimented with changes to pol51opt, and the initial phases perform a numerical optimization that is quite tricky, and gets stuck in local minima quite easily.

[Batalov]

(thinking aloud)
"What would make some sense in a near future is pol61m0 and pol61opt ..."




_______
Yes, but it is not trivial. Optimization becomes a yet one dimension higher problem, and it was not a piece of cake even for the "5/1" class problem.

For the pol51*, incidentally, I have an immediate idea for anyone: use the X5 coefficients divisible by 120. All of my recent searches had the X5|120. So one can just awk/perl the *.m file before running pol51opt (if they cannot mess with the code, and if they can - this idea is truly below their level. With this idea I was aiming for the lowest hanging fruit.)

[miklin]

Originally Posted by Batalov

(thinking aloud)
"What would make some sense in a near future is pol61m0 and pol61opt ..."

So it already was necessary yesterday. And Latsieve for the company it is necessary to do, and that considers slowly as that death.

Sergey Miklin

[miklin]

Originally Posted by jasonp

The polynomial selection is sensitive to roundoff error and the level of optimization used when compiling. pol51m0b will not work if you compile with optimization and use the assembler code; other systems (64-bit etc) cannot use the assembly code at all, but will work if you compile with optimization. That is what generates different results.

I have also experimented with changes to pol51opt, and the initial phases perform a numerical optimization that is quite tricky, and gets stuck in local minima quite easily.

Yes I too tried to present this code (Latsieve, Pol50b) to mathematics. I did it on MAPLE. But a little that has turned out. Here my modest attempts.

Sergey Miklin

[miklin]

Originally Posted by jasonp

The polynomial selection is sensitive to roundoff error and the level of optimization used when compiling. pol51m0b will not work if you compile with optimization and use the assembler code; other systems (64-bit etc) cannot use the assembly code at all, but will work if you compile with optimization. That is what generates different results.

I have also experimented with changes to pol51opt, and the initial phases perform a numerical optimization that is quite tricky, and gets stuck in local minima quite easily.

Yes I have tried to collect 64 bit. Really works. By the way as a result all has turned out well. Example Example_512 has fulfilled as it is necessary. And as to the assembler without it all too perfectly works I collected the project 32dit without the assembler also correct result. The assembler can be thrown out safely from the project.