Msieve 1.40 Beta Feedback - Page 5

Andi_HB · 2009-03-09, 14:08

No Problems with Msieve 1.40beta2

Polynomial search with Msieve , Sieving with GNFS and finally Msieve again.

Code:

Mon Mar 09 07:15:26 2009  
Mon Mar 09 07:15:26 2009  
Mon Mar 09 07:15:26 2009  Msieve v. 1.40
Mon Mar 09 07:15:26 2009  random seeds: ade51018 e14bc1bb
Mon Mar 09 07:15:26 2009  factoring 37341749897142121501044346885341085486989665803866127120929436699947381633311322080195902338164347592550563750975260551289243 (125 digits)
Mon Mar 09 07:15:27 2009  searching for 15-digit factors
Mon Mar 09 07:15:29 2009  commencing number field sieve (125-digit input)
Mon Mar 09 07:15:29 2009  R0: -1088114432624936520075342
Mon Mar 09 07:15:29 2009  R1:  34737124470091
Mon Mar 09 07:15:29 2009  A0: -71496577573595625906473163785
Mon Mar 09 07:15:29 2009  A1:  35064141251845164949397623
Mon Mar 09 07:15:29 2009  A2: -776953222852106819385
Mon Mar 09 07:15:29 2009  A3: -2160258613523839
Mon Mar 09 07:15:29 2009  A4:  18360593834
Mon Mar 09 07:15:29 2009  A5:  24480
Mon Mar 09 07:15:29 2009  skew 181474.42, size 5.173726e-012, alpha -6.170813, combined = 1.493559e-010
Mon Mar 09 07:15:29 2009  
Mon Mar 09 07:15:29 2009  commencing relation filtering
Mon Mar 09 07:15:29 2009  commencing duplicate removal, pass 1
Mon Mar 09 07:17:02 2009  found 1491858 hash collisions in 9245826 relations
Mon Mar 09 07:17:25 2009  added 58666 free relations
Mon Mar 09 07:17:25 2009  commencing duplicate removal, pass 2
Mon Mar 09 07:17:40 2009  found 1497815 duplicates and 7806676 unique relations
Mon Mar 09 07:17:40 2009  memory use: 65.3 MB
Mon Mar 09 07:17:40 2009  reading rational ideals above 7405568
Mon Mar 09 07:17:40 2009  reading algebraic ideals above 7405568
Mon Mar 09 07:17:40 2009  commencing singleton removal, pass 1
Mon Mar 09 07:19:02 2009  relations with 0 large ideals: 263246
Mon Mar 09 07:19:02 2009  relations with 1 large ideals: 1611965
Mon Mar 09 07:19:02 2009  relations with 2 large ideals: 3137880
Mon Mar 09 07:19:02 2009  relations with 3 large ideals: 2223928
Mon Mar 09 07:19:02 2009  relations with 4 large ideals: 502682
Mon Mar 09 07:19:02 2009  relations with 5 large ideals: 12488
Mon Mar 09 07:19:02 2009  relations with 6 large ideals: 54487
Mon Mar 09 07:19:02 2009  relations with 7+ large ideals: 0
Mon Mar 09 07:19:02 2009  7806676 relations and about 7357141 large ideals
Mon Mar 09 07:19:02 2009  commencing singleton removal, pass 2
Mon Mar 09 07:20:24 2009  found 3492596 singletons
Mon Mar 09 07:20:24 2009  current dataset: 4314080 relations and about 3200149 large ideals
Mon Mar 09 07:20:24 2009  commencing singleton removal, pass 3
Mon Mar 09 07:21:13 2009  found 697808 singletons
Mon Mar 09 07:21:13 2009  current dataset: 3616272 relations and about 2461138 large ideals
Mon Mar 09 07:21:13 2009  commencing singleton removal, pass 4
Mon Mar 09 07:21:56 2009  found 183238 singletons
Mon Mar 09 07:21:56 2009  current dataset: 3433034 relations and about 2274326 large ideals
Mon Mar 09 07:21:56 2009  commencing singleton removal, final pass
Mon Mar 09 07:22:39 2009  memory use: 50.7 MB
Mon Mar 09 07:22:39 2009  commencing in-memory singleton removal
Mon Mar 09 07:22:39 2009  begin with 3433034 relations and 2394020 unique ideals
Mon Mar 09 07:22:41 2009  reduce to 3078894 relations and 2033836 ideals in 11 passes
Mon Mar 09 07:22:41 2009  max relations containing the same ideal: 26
Mon Mar 09 07:22:42 2009  reading rational ideals above 720000
Mon Mar 09 07:22:42 2009  reading algebraic ideals above 720000
Mon Mar 09 07:22:42 2009  commencing singleton removal, final pass
Mon Mar 09 07:23:28 2009  keeping 2804566 ideals with weight <= 20, new excess is 247608
Mon Mar 09 07:23:32 2009  memory use: 91.6 MB
Mon Mar 09 07:23:32 2009  commencing in-memory singleton removal
Mon Mar 09 07:23:33 2009  begin with 3082211 relations and 2804566 unique ideals
Mon Mar 09 07:23:37 2009  reduce to 3031265 relations and 2737239 ideals in 10 passes
Mon Mar 09 07:23:37 2009  max relations containing the same ideal: 20
Mon Mar 09 07:23:40 2009  relations with 0 large ideals: 4169
Mon Mar 09 07:23:40 2009  relations with 1 large ideals: 43318
Mon Mar 09 07:23:40 2009  relations with 2 large ideals: 218635
Mon Mar 09 07:23:40 2009  relations with 3 large ideals: 583081
Mon Mar 09 07:23:40 2009  relations with 4 large ideals: 887820
Mon Mar 09 07:23:40 2009  relations with 5 large ideals: 779594
Mon Mar 09 07:23:40 2009  relations with 6 large ideals: 389468
Mon Mar 09 07:23:40 2009  relations with 7+ large ideals: 125180
Mon Mar 09 07:23:40 2009  commencing 2-way merge
Mon Mar 09 07:23:43 2009  reduce to 1807463 relation sets and 1513482 unique ideals
Mon Mar 09 07:23:43 2009  ignored 45 oversize relation sets
Mon Mar 09 07:23:43 2009  commencing full merge
Mon Mar 09 07:24:18 2009  memory use: 140.6 MB
Mon Mar 09 07:24:18 2009  found 877039 cycles, need 841682
Mon Mar 09 07:24:18 2009  weight of 841682 cycles is about 59272709 (70.42/cycle)
Mon Mar 09 07:24:18 2009  distribution of cycle lengths:
Mon Mar 09 07:24:18 2009  1 relations: 98931
Mon Mar 09 07:24:18 2009  2 relations: 100305
Mon Mar 09 07:24:18 2009  3 relations: 99032
Mon Mar 09 07:24:18 2009  4 relations: 88140
Mon Mar 09 07:24:18 2009  5 relations: 78635
Mon Mar 09 07:24:18 2009  6 relations: 67756
Mon Mar 09 07:24:18 2009  7 relations: 57401
Mon Mar 09 07:24:18 2009  8 relations: 47966
Mon Mar 09 07:24:18 2009  9 relations: 40843
Mon Mar 09 07:24:18 2009  10+ relations: 162673
Mon Mar 09 07:24:18 2009  heaviest cycle: 20 relations
Mon Mar 09 07:24:18 2009  commencing cycle optimization
Mon Mar 09 07:24:20 2009  start with 4988347 relations
Mon Mar 09 07:24:34 2009  pruned 149444 relations
Mon Mar 09 07:24:34 2009  memory use: 129.3 MB
Mon Mar 09 07:24:34 2009  distribution of cycle lengths:
Mon Mar 09 07:24:34 2009  1 relations: 98931
Mon Mar 09 07:24:34 2009  2 relations: 103120
Mon Mar 09 07:24:34 2009  3 relations: 103173
Mon Mar 09 07:24:34 2009  4 relations: 90861
Mon Mar 09 07:24:34 2009  5 relations: 80983
Mon Mar 09 07:24:34 2009  6 relations: 68708
Mon Mar 09 07:24:34 2009  7 relations: 57891
Mon Mar 09 07:24:34 2009  8 relations: 47807
Mon Mar 09 07:24:34 2009  9 relations: 40685
Mon Mar 09 07:24:34 2009  10+ relations: 149523
Mon Mar 09 07:24:34 2009  heaviest cycle: 20 relations
Mon Mar 09 07:24:35 2009  RelProcTime: 534
Mon Mar 09 07:24:35 2009  
Mon Mar 09 07:24:35 2009  commencing linear algebra
Mon Mar 09 07:24:35 2009  read 841682 cycles
Mon Mar 09 07:24:37 2009  cycles contain 2673765 unique relations
Mon Mar 09 07:25:09 2009  read 2673765 relations
Mon Mar 09 07:25:14 2009  using 20 quadratic characters above 134216838
Mon Mar 09 07:25:30 2009  building initial matrix
Mon Mar 09 07:26:13 2009  memory use: 307.6 MB
Mon Mar 09 07:26:14 2009  read 841682 cycles
Mon Mar 09 07:26:15 2009  matrix is 841349 x 841682 (241.5 MB) with weight 80038905 (95.09/col)
Mon Mar 09 07:26:15 2009  sparse part has weight 56569614 (67.21/col)
Mon Mar 09 07:26:32 2009  filtering completed in 3 passes
Mon Mar 09 07:26:32 2009  matrix is 837333 x 837533 (240.7 MB) with weight 79742206 (95.21/col)
Mon Mar 09 07:26:32 2009  sparse part has weight 56405744 (67.35/col)
Mon Mar 09 07:26:35 2009  read 837533 cycles
Mon Mar 09 07:26:36 2009  matrix is 837333 x 837533 (240.7 MB) with weight 79742206 (95.21/col)
Mon Mar 09 07:26:36 2009  sparse part has weight 56405744 (67.35/col)
Mon Mar 09 07:26:36 2009  saving the first 48 matrix rows for later
Mon Mar 09 07:26:37 2009  matrix is 837285 x 837533 (230.5 MB) with weight 63294546 (75.57/col)
Mon Mar 09 07:26:37 2009  sparse part has weight 55403246 (66.15/col)
Mon Mar 09 07:26:37 2009  matrix includes 64 packed rows
Mon Mar 09 07:26:37 2009  using block size 65536 for processor cache size 3072 kB
Mon Mar 09 07:26:43 2009  commencing Lanczos iteration
Mon Mar 09 07:26:43 2009  memory use: 229.4 MB
Mon Mar 09 09:11:21 2009  lanczos halted after 13243 iterations (dim = 837285)
Mon Mar 09 09:11:23 2009  recovered 30 nontrivial dependencies
Mon Mar 09 09:11:23 2009  BLanczosTime: 6361
Mon Mar 09 09:11:23 2009  
Mon Mar 09 09:11:23 2009  commencing square root phase
Mon Mar 09 09:11:23 2009  reading relations for dependency 1
Mon Mar 09 09:11:24 2009  read 418665 cycles
Mon Mar 09 09:11:25 2009  cycles contain 1638314 unique relations
Mon Mar 09 09:11:47 2009  read 1638314 relations
Mon Mar 09 09:11:57 2009  multiplying 1333398 relations
Mon Mar 09 09:15:37 2009  multiply complete, coefficients have about 61.72 million bits
Mon Mar 09 09:15:40 2009  initial square root is modulo 726184289
Mon Mar 09 09:22:06 2009  sqrtTime: 613
Mon Mar 09 09:22:06 2009  prp58 factor: 3199531318649953244341022926800550296567933036062498357291
Mon Mar 09 09:22:06 2009  prp68 factor: 11671006212528191652002268221699814254356844004459282877277697877073
Mon Mar 09 09:22:06 2009  elapsed time 02:06:40

jasonp · 2009-03-09, 15:57

Quote:

Originally Posted by Jeff Gilchrist

Is it just the poly selection that uses GMP code?

Yes, and the GMP-ECM driver. The amount of multiple-precision arithmetic in the poly selection is not very large or very time consuming, so I have plans to switch from GMP to the built-in multiple precision library. Then the new poly selection will become the default, and I can retire the crappy older poly selection code.

mklasson · 2009-03-09, 16:48

Code:

>msieve -np -v 15574594719946726376443054524568252573184064672883769399758713363048665898789051104120829428313817576121


Msieve v. 1.40
Mon Mar 09 17:43:51 2009
random seeds: 1e96f1b4 273b483c
factoring 15574594719946726376443054524568252573184064672883769399758713363048665898789051104120829428313817576121 (104 digits)
searching for 15-digit factors
commencing number field sieve (104-digit input)
commencing number field sieve polynomial selection
time limit set to 0.46 hours
searching leading coefficients from 1 to 4813
deadline: 30 seconds per coefficient
coeff 60-600 125964 163753 163754 212880 lattice 2579
p 74534 100000 268156 359777 lattice 962
batch 2192 107302
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
...

It goes on like that seemingly forever. Any ideas?

Jeff Gilchrist · 2009-03-09, 17:31

Quote:

Originally Posted by mklasson

It goes on like that seemingly forever. Any ideas?

What compiler/OS are you using? If you built that yourself using 64bit MSVC in Windows I think that is the error message I see when I'm trying to do polynomial selection. The code has changed enough that the Windows 64bit build is broken of poly selection.

Using your command line on a 64bit Linux binary I built seems to be working fine.

Jeff.

10metreh · 2009-03-09, 17:44

Quote:

Originally Posted by mklasson

Code:

>msieve -np -v 15574594719946726376443054524568252573184064672883769399758713363048665898789051104120829428313817576121
 
 
Msieve v. 1.40
Mon Mar 09 17:43:51 2009
random seeds: 1e96f1b4 273b483c
factoring 15574594719946726376443054524568252573184064672883769399758713363048665898789051104120829428313817576121 (104 digits)
searching for 15-digit factors
commencing number field sieve (104-digit input)
commencing number field sieve polynomial selection
time limit set to 0.46 hours
searching leading coefficients from 1 to 4813
deadline: 30 seconds per coefficient
coeff 60-600 125964 163753 163754 212880 lattice 2579
p 74534 100000 268156 359777 lattice 962
batch 2192 107302
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
expand failed
...

It goes on like that seemingly forever. Any ideas?

I'll do the poly search for you, if you like.

(On a 32-bit machine, that is.)

mklasson · 2009-03-09, 18:04

Jeff,
ah, it's indeed a self-built x64 MSVC. It worked just fine on another number the other day though so I guess the code's not all broken.
EDIT: On second thought, that was probably with jason's 32-bit binary. Yeah, that number also gives the "expand failed" errors when I try with the x64 binary.

10metreh,
most gracious of you, but I've let ggnfs find a poly instead. It came up with one giving a Murphy score of 2.53e-9 (I'm just quoting here

). Hopefully that's not too shabby. The C103 I did the other day with a poly from msieve had "combined = 2.760954e-009", which I'm assuming is only slightly better? That one completed in just under 5 cpu hours so with any luck I should have this bastard on its back soon enough.

10metreh · 2009-03-09, 18:11

Quote:

Originally Posted by mklasson

Jeff,
ah, it's indeed a self-built x64 MSVC. It worked just fine on another number the other day though so I guess the code's not all broken.
EDIT: On second thought, that was probably with jason's 32-bit binary. Yeah, that number also gives the "expand failed" errors when I try with the x64 binary.

10metreh,
most gracious of you, but I've let ggnfs find a poly instead. It came up with one giving a Murphy score of 2.53e-9 (I'm just quoting here

). Hopefully that's not too shabby. The C103 I did the other day with a poly from msieve had "combined = 2.760954e-009", which I'm assuming is only slightly better? That one completed in just under 5 cpu hours so with any luck I should have this bastard on its back soon enough.

Don't know about how that will perform - the E score isn't an indicator of exactly how long the sieving will take. And, with larger numbers, you can expect lower scores, to confuse the matter.

And just to say, if you're having problems with poly selection on a small number, I'm willing to find a poly for you if you PM me the number.

Andi_HB · 2009-03-09, 20:00

Is the upper Limit for Msieve 1.40 still < 160 digits for GNFS Numbers?
I found this in the other Thread New Polynomial Finder

The poly selection code only has parameters for GNFS < 160 digits (they're copied from GGNFS, and the parameters are the same except for a little scaling). The largest input I'm bothering with right now is RSA140, there's a huge amount of optimization still needed.

jasonp · 2009-03-09, 20:54

The limits on input size for poly selection haven't changed, Tom was busy expanding those limits but the new release should not be delayed much longer and I don't want to rush him. v1.41 should be out much more quickly than the current release.

10metreh · 2009-03-09, 21:07

Quote:

Originally Posted by jasonp

The limits on input size for poly selection haven't changed, Tom was busy expanding those limits but the new release should not be delayed much longer and I don't want to rush him. v1.41 should be out much more quickly than the current release.

Is it possible to remove the limit on NFS poly selection in the full release for people who want to run C96 GNFSs (either because it is faster, or for experimenting) and the like? Or is that too specialised for it to be needed?

mdettweiler · 2009-03-09, 22:10

Quote:

Originally Posted by 10metreh

Is it possible to remove the limit on NFS poly selection in the full release for people who want to run C96 GNFSs (either because it is faster, or for experimenting) and the like? Or is that too specialised for it to be needed?

Well, AFAIK v1.40beta2 is quite likely to be identical to the 1.40 release (since, unless I missed something, no major bugs have been reported in beta 2), so, shazam: you have a nice pre-made full release version without any NFS size limitation.

2009-03-09, 18:04	#50
mklasson Feb 2004 2·3·43 Posts	Jeff, ah, it's indeed a self-built x64 MSVC. It worked just fine on another number the other day though so I guess the code's not all broken. EDIT: On second thought, that was probably with jason's 32-bit binary. Yeah, that number also gives the "expand failed" errors when I try with the x64 binary. 10metreh, most gracious of you, but I've let ggnfs find a poly instead. It came up with one giving a Murphy score of 2.53e-9 (I'm just quoting here ). Hopefully that's not too shabby. The C103 I did the other day with a poly from msieve had "combined = 2.760954e-009", which I'm assuming is only slightly better? That one completed in just under 5 cpu hours so with any luck I should have this bastard on its back soon enough. Last fiddled with by mklasson on 2009-03-09 at 18:07 Reason: my memory is flawed

2009-03-09, 20:00	#52
Andi_HB Mar 2007 Germany 2³×3×11 Posts	Is the upper Limit for Msieve 1.40 still < 160 digits for GNFS Numbers? I found this in the other Thread New Polynomial Finder The poly selection code only has parameters for GNFS < 160 digits (they're copied from GGNFS, and the parameters are the same except for a little scaling). The largest input I'm bothering with right now is RSA140, there's a huge amount of optimization still needed. Last fiddled with by Andi_HB on 2009-03-09 at 20:02

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.51 feedback	xilman	Msieve	256	2014-01-26 22:06
Msieve v1.46 feedback	em99010pepe	Msieve	153	2010-12-12 14:21
Msieve 1.44 feedback	xilman	Msieve	111	2010-09-14 21:50
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53

2009-03-09, 20:54	#53
jasonp Tribal Bullet Oct 2004 3,541 Posts	The limits on input size for poly selection haven't changed, Tom was busy expanding those limits but the new release should not be delayed much longer and I don't want to rush him. v1.41 should be out much more quickly than the current release.