20080925, 22:24  #1 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
3·31·97 Posts 
Msieve / lattice siever with degree 7/8 poly
Just out of curiosity and a proofofconcept 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 inputpoly.c. As well as it could have been expected, everything worked. Code:
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^1121) / 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 specialq in [400000, 1300001) Primes: rational ideals reading, algebraic ideals reading, Relations: 2.2M relations Max relations in full relationset: 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 defpar.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 15digit factors commencing number field sieve (111digit input) R0: 10000000000000000 R1: 1 A0: 1 A1: 0 A2: 0 A3: 0 A4: 0 A5: 0 A6: 0 A7: 8 size score = 3.531074e04, Murphy alpha = 0.845874, combined = 2.858033e04 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 Serge Last fiddled with by jasonp on 20080927 at 02:55 Reason: Fixed a typo in the patch; at 56 views, it's the most popular msieve patch ever 
20080926, 01:08  #2  
Tribal Bullet
Oct 2004
2·3·587 Posts 
Quote:


20080926, 07:55  #3 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
10001100111101_{2} Posts 
...and octics, too
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... Code:
*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'); 
20080926, 08:43  #4 
Nov 2007
3·5^{2} Posts 
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. Code:
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 a5range: 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: a5values: 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 2e12 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.55e12 X5 28200000 X4 28360813539851 X3 13553173634695647906 X2 2564268902978149419168456 X1 415989256480951014687269907996 X0 28294692934494412681458239834080920 Y1 14507315380338583 Y0 207858338661942505983301552999 M 3360535699488068065188616076918604440700798249780305704017974532022544629934677045714592688052709846153098285633372058200144914970580706639105648340708817 END POLY Last fiddled with by miklin on 20080926 at 09:02 
20080926, 08:57  #5  
Bamboozled!
May 2003
Down not across
23410_{8} Posts 
Quote:
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 

20080926, 09:45  #6 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
3×31×97 Posts 
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. 
20080926, 13:18  #7  
Tribal Bullet
Oct 2004
2×3×587 Posts 
Quote:
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. 

20080926, 21:07  #8 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3
3·31·97 Posts 
as long as the thread was already hijacked...
(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 X5120. 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.) Last fiddled with by Batalov on 20080926 at 21:36 Reason: (answer inline) 
20080926, 21:16  #9 
Nov 2007
3·5^{2} Posts 

20080927, 07:53  #10  
Nov 2007
3·5^{2} Posts 
Quote:
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 

20080929, 20:31  #11  
Nov 2007
3×5^{2} Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
QS Lattice Siever  R.D. Silverman  Factoring  31  20181008 17:17 
Compiling 64 bit lattice siever on gcc 4.8.5  chris2be8  Factoring  6  20180206 17:22 
OpenCL accellerated lattice siever  pstach  Factoring  1  20140523 01:03 
Shape of a CUDA lattice siever  fivemack  Programming  2  20121216 01:07 
ggnfs lattice siever misses some primes  fivemack  Factoring  1  20080118 13:47 