Msieve sourceforge discussion

[jasonp]

I would just call it SVN 33, with an actual version number reserved for a published snapshot; that's enough to uniquely identify the source used. My personal policy is to bump the reported version number right after a full release.

[Jeff Gilchrist]

Sorry so is 1.42 still considered a "beta" version or is that a full release now? As in, should I update my Windows binaries?

^^^ Nevermind, I just noticed the 1.42 "release" message after beta 3. Things have been a little crazy around here lately...

Jeff.

[jasonp]

No big deal. Note that sourceforge lets you subscribe to an RSS feed that will notify you of news or announcements posted on the project page (I think; no idea how it works, so hopefully it's automatic :)

[fivemack]

I factored (10^201+9^201)/(10^67+9^67) using the obvious algebraic polynomial 100x^4 - 90x + 81. This splits modulo all primes, so each dependency prints the 'initial square root is modulo 53' message.

With msieve-1.37, dependency 1 gave 'square roots are identical', dependency 2 failed silently, dependency 3 gave 'newton iteration failed' and dependency 4 worked.

With the same dependencies and msieve-1.43-svn, dependencies 1,6,11,13,14 failed silently and dependencies 2,3,4,5,7,8,9,10,12 gave 'newton iteration failed'; dependency 15 worked.

I don't know how deterministic the process is so I don't know if this is a real issue

[jasonp]

Do you get the same increase in Newton failures when using v1.42? Latest svn uses GMP exclusively for the square root, which makes me suspicious. Also, v1.37 did use a different collection of relations in the square root, that was one release before Paul Zimmermann suggested only using relations with odd parity in the dependency, and then only once per relation.

[fivemack]

I think the current SVN doesn't stop quite early enough in the case where there are nothing like enough cycles: it doesn't seem that sensible to proceed to stages 2 and 3 when you've just said

found 3687 cycles, need 131782

Mon Aug 24 10:35:15 2009  found 125464 hash collisions in 2002778 relations
Mon Aug 24 10:35:15 2009  added 510 free relations
Mon Aug 24 10:35:15 2009  commencing duplicate removal, pass 2
Mon Aug 24 10:35:16 2009  found 74229 duplicates and 1929059 unique relations
Mon Aug 24 10:35:16 2009  memory use: 8.2 MB
Mon Aug 24 10:35:16 2009  reading ideals above 30000
Mon Aug 24 10:35:16 2009  commencing singleton removal, initial pass
Mon Aug 24 10:35:42 2009  memory use: 37.3 MB
Mon Aug 24 10:35:42 2009  reading all ideals from disk
Mon Aug 24 10:35:42 2009  memory use: 68.1 MB
Mon Aug 24 10:35:42 2009  keeping 2027735 ideals with weight <= 200, target excess is 8528
Mon Aug 24 10:35:43 2009  commencing in-memory singleton removal
Mon Aug 24 10:35:43 2009  begin with 1929059 relations and 2027735 unique ideals
Mon Aug 24 10:35:47 2009  reduce to 1188023 relations and 1139464 ideals in 14 passes
Mon Aug 24 10:35:47 2009  max relations containing the same ideal: 153
Mon Aug 24 10:35:48 2009  removing 143444 relations and 124111 ideals in 19333 cliques
Mon Aug 24 10:35:48 2009  commencing in-memory singleton removal
Mon Aug 24 10:35:49 2009  begin with 1044579 relations and 1139464 unique ideals
Mon Aug 24 10:35:50 2009  reduce to 1029353 relations and 999725 ideals in 7 passes
Mon Aug 24 10:35:50 2009  max relations containing the same ideal: 140
Mon Aug 24 10:35:51 2009  removing 103856 relations and 84523 ideals in 19333 cliques
Mon Aug 24 10:35:51 2009  commencing in-memory singleton removal
Mon Aug 24 10:35:51 2009  begin with 925497 relations and 999725 unique ideals
Mon Aug 24 10:35:52 2009  reduce to 916161 relations and 905681 ideals in 7 passes
Mon Aug 24 10:35:52 2009  max relations containing the same ideal: 127
Mon Aug 24 10:35:54 2009  relations with 0 large ideals: 867
Mon Aug 24 10:35:54 2009  relations with 1 large ideals: 57
Mon Aug 24 10:35:54 2009  relations with 2 large ideals: 139
Mon Aug 24 10:35:54 2009  relations with 3 large ideals: 1638
Mon Aug 24 10:35:54 2009  relations with 4 large ideals: 12419
Mon Aug 24 10:35:54 2009  relations with 5 large ideals: 119316
Mon Aug 24 10:35:54 2009  relations with 6 large ideals: 157551
Mon Aug 24 10:35:54 2009  relations with 7+ large ideals: 624174
Mon Aug 24 10:35:54 2009  commencing 2-way merge
Mon Aug 24 10:35:55 2009  reduce to 634175 relation sets and 623695 unique ideals
Mon Aug 24 10:35:55 2009  commencing full merge
Mon Aug 24 10:36:43 2009  memory use: 28.8 MB
Mon Aug 24 10:36:43 2009  found 3687 cycles, need 131782
Mon Aug 24 10:36:43 2009  weight of 3687 cycles is about 210676 (57.14/cycle)
Mon Aug 24 10:36:43 2009  distribution of cycle lengths:
Mon Aug 24 10:36:43 2009  1 relations: 2116
Mon Aug 24 10:36:43 2009  2 relations: 251
Mon Aug 24 10:36:43 2009  3 relations: 136
Mon Aug 24 10:36:43 2009  4 relations: 82
Mon Aug 24 10:36:43 2009  5 relations: 79
Mon Aug 24 10:36:43 2009  6 relations: 79
Mon Aug 24 10:36:43 2009  7 relations: 82
Mon Aug 24 10:36:43 2009  8 relations: 76
Mon Aug 24 10:36:43 2009  9 relations: 64
Mon Aug 24 10:36:43 2009  10+ relations: 722
Mon Aug 24 10:36:43 2009  heaviest cycle: 28 relations
Mon Aug 24 10:36:43 2009  commencing cycle optimization
Mon Aug 24 10:36:43 2009  start with 18118 relations
Mon Aug 24 10:36:43 2009  pruned 393 relations
Mon Aug 24 10:36:43 2009  memory use: 0.7 MB
Mon Aug 24 10:36:43 2009  distribution of cycle lengths:
Mon Aug 24 10:36:43 2009  1 relations: 2116
Mon Aug 24 10:36:43 2009  2 relations: 254
Mon Aug 24 10:36:43 2009  3 relations: 140
Mon Aug 24 10:36:43 2009  4 relations: 82
Mon Aug 24 10:36:43 2009  5 relations: 80
Mon Aug 24 10:36:43 2009  6 relations: 83
Mon Aug 24 10:36:43 2009  7 relations: 83
Mon Aug 24 10:36:43 2009  8 relations: 77
Mon Aug 24 10:36:43 2009  9 relations: 68
Mon Aug 24 10:36:43 2009  10+ relations: 704
Mon Aug 24 10:36:43 2009  heaviest cycle: 28 relations
Mon Aug 24 10:36:43 2009  RelProcTime: 109
Mon Aug 24 10:36:43 2009  
Mon Aug 24 10:36:43 2009  commencing linear algebra
Mon Aug 24 10:36:43 2009  read 3687 cycles
Mon Aug 24 10:36:43 2009  cycles contain 15551 unique relations
Mon Aug 24 10:36:43 2009  read 15551 relations
Mon Aug 24 10:36:43 2009  using 20 quadratic characters above 16716044
Mon Aug 24 10:36:43 2009  building initial matrix
Mon Aug 24 10:36:43 2009  memory use: 2.6 MB
Mon Aug 24 10:36:43 2009  read 3687 cycles
Mon Aug 24 10:36:43 2009  matrix is 53537 x 3687 (0.8 MB) with weight 224099 (60.78/col)
Mon Aug 24 10:36:43 2009  sparse part has weight 161098 (43.69/col)
Mon Aug 24 10:36:43 2009  matrix is corrupt; skipping linear algebra
Mon Aug 24 10:36:43 2009  
Mon Aug 24 10:36:43 2009  commencing square root phase
Mon Aug 24 10:36:43 2009  reading relations for dependency 1
Mon Aug 24 10:36:43 2009  error: read_cycles can't open dependency file

The same set of relations runs without issue on 1.37:

Mon Aug 24 10:40:19 2009  found 74229 duplicates and 1929059 unique relations
Mon Aug 24 10:40:19 2009  memory use: 37.8 MB
Mon Aug 24 10:40:19 2009  reading rational ideals above 3604480
Mon Aug 24 10:40:19 2009  reading algebraic ideals above 3604480
Mon Aug 24 10:40:19 2009  commencing singleton removal, pass 1
Mon Aug 24 10:40:41 2009  relations with 0 large ideals: 220888
Mon Aug 24 10:40:41 2009  relations with 1 large ideals: 462649
Mon Aug 24 10:40:41 2009  relations with 2 large ideals: 570256
Mon Aug 24 10:40:41 2009  relations with 3 large ideals: 353185
Mon Aug 24 10:40:41 2009  relations with 4 large ideals: 106780
Mon Aug 24 10:40:41 2009  relations with 5 large ideals: 215301
Mon Aug 24 10:40:41 2009  relations with 6 large ideals: 0
Mon Aug 24 10:40:41 2009  relations with 7+ large ideals: 0
Mon Aug 24 10:40:41 2009  1929059 relations and about 1514488 large ideals
Mon Aug 24 10:40:41 2009  commencing singleton removal, pass 2
Mon Aug 24 10:41:03 2009  found 359723 singletons
Mon Aug 24 10:41:03 2009  current dataset: 1569336 relations and about 1031824 large ideals
Mon Aug 24 10:41:03 2009  commencing singleton removal, pass 3
Mon Aug 24 10:41:20 2009  found 247462 singletons
Mon Aug 24 10:41:20 2009  current dataset: 1321874 relations and about 766540 large ideals
Mon Aug 24 10:41:20 2009  commencing singleton removal, final pass
Mon Aug 24 10:41:34 2009  memory use: 22.6 MB
Mon Aug 24 10:41:34 2009  commencing in-memory singleton removal
Mon Aug 24 10:41:34 2009  begin with 1321874 relations and 771981 unique ideals
Mon Aug 24 10:41:35 2009  reduce to 1205034 relations and 652651 ideals in 15 passes
Mon Aug 24 10:41:35 2009  max relations containing the same ideal: 47
Mon Aug 24 10:41:36 2009  reading rational ideals above 720000
Mon Aug 24 10:41:36 2009  reading algebraic ideals above 720000
Mon Aug 24 10:41:36 2009  commencing singleton removal, final pass
Mon Aug 24 10:41:50 2009  keeping 1014008 ideals with weight <= 20, new excess is 153892
Mon Aug 24 10:41:50 2009  memory use: 33.3 MB
Mon Aug 24 10:41:50 2009  commencing in-memory singleton removal
Mon Aug 24 10:41:51 2009  begin with 1205544 relations and 1014008 unique ideals
Mon Aug 24 10:41:52 2009  reduce to 1188023 relations and 994100 ideals in 10 passes
Mon Aug 24 10:41:52 2009  max relations containing the same ideal: 20
Mon Aug 24 10:41:53 2009  relations with 0 large ideals: 24434
Mon Aug 24 10:41:53 2009  relations with 1 large ideals: 68259
Mon Aug 24 10:41:53 2009  relations with 2 large ideals: 197936
Mon Aug 24 10:41:53 2009  relations with 3 large ideals: 310858
Mon Aug 24 10:41:53 2009  relations with 4 large ideals: 292292
Mon Aug 24 10:41:53 2009  relations with 5 large ideals: 229855
Mon Aug 24 10:41:53 2009  relations with 6 large ideals: 52589
Mon Aug 24 10:41:53 2009  relations with 7+ large ideals: 11800
Mon Aug 24 10:41:53 2009  commencing 2-way merge
Mon Aug 24 10:41:55 2009  reduce to 813028 relation sets and 619144 unique ideals
Mon Aug 24 10:41:55 2009  ignored 39 oversize relation sets
Mon Aug 24 10:41:55 2009  commencing full merge
Mon Aug 24 10:42:10 2009  memory use: 52.9 MB
Mon Aug 24 10:42:10 2009  found 326944 cycles, need 307344
Mon Aug 24 10:42:11 2009  weight of 307344 cycles is about 21619551 (70.34/cycle)
Mon Aug 24 10:42:11 2009  distribution of cycle lengths:
Mon Aug 24 10:42:11 2009  1 relations: 43843
Mon Aug 24 10:42:11 2009  2 relations: 28866
Mon Aug 24 10:42:11 2009  3 relations: 28450
Mon Aug 24 10:42:11 2009  4 relations: 26249
Mon Aug 24 10:42:11 2009  5 relations: 24068
Mon Aug 24 10:42:11 2009  6 relations: 21612
Mon Aug 24 10:42:11 2009  7 relations: 18991
Mon Aug 24 10:42:11 2009  8 relations: 16909
Mon Aug 24 10:42:11 2009  9 relations: 14894
Mon Aug 24 10:42:11 2009  10+ relations: 83462
Mon Aug 24 10:42:11 2009  heaviest cycle: 24 relations
Mon Aug 24 10:42:11 2009  commencing cycle optimization
Mon Aug 24 10:42:11 2009  start with 2102590 relations
Mon Aug 24 10:42:18 2009  pruned 112161 relations
Mon Aug 24 10:42:18 2009  memory use: 59.3 MB
Mon Aug 24 10:42:18 2009  distribution of cycle lengths:
Mon Aug 24 10:42:18 2009  1 relations: 43843
Mon Aug 24 10:42:18 2009  2 relations: 29950
Mon Aug 24 10:42:18 2009  3 relations: 30156
Mon Aug 24 10:42:18 2009  4 relations: 27785
Mon Aug 24 10:42:18 2009  5 relations: 25508
Mon Aug 24 10:42:18 2009  6 relations: 22603
Mon Aug 24 10:42:18 2009  7 relations: 19886
Mon Aug 24 10:42:18 2009  8 relations: 17481
Mon Aug 24 10:42:18 2009  9 relations: 15253
Mon Aug 24 10:42:18 2009  10+ relations: 74879
Mon Aug 24 10:42:18 2009  heaviest cycle: 24 relations
Mon Aug 24 10:42:18 2009  
Mon Aug 24 10:42:18 2009  commencing linear algebra

[blastwave]

Please pardon the potentially unsophisticated questions but I am new here. Despite my long time interest in most things mathematical I can not begin to discuss number theory related to primality tests nor factoring.

My primary interest in msieve at the moment is to make a reliable port to the Solaris Operating System such that users can simply install it and use it. I have already fetched the sources for 1.42 and built a first pass binary for AMD64 OpenSolaris ( build snv_121 ) using Sun Studio 12 Update 1 compiler tools. I did use GMP for this and I am sorry to say that I used GCC to port GMP. There simply is no easy way to port GMP with Studio 12.

So I am running a few tests and I only have Wolfram Alpha to verify with as well as a much older Msieve v. 1.19.

Are there any posted factor tests as well as results?

At the moment I am factoring, or at least attempting to factor, an 80 digit number :

21662887038670915563461368246059452237028460443882686940871185423604981619664343

This is the product of two 40 digit primes :

next number: 3615415881585117908550243505309785526231


Msieve v. 1.42
Mon Aug 24 23:25:16 2009
random seeds: 060e8830 77c22cbf
factoring 3615415881585117908550243505309785526231 (40 digits)
prp40 factor: 3615415881585117908550243505309785526231
elapsed time 00:00:00


next number: 5991810554633396517767024967580894321153


Msieve v. 1.42
Mon Aug 24 23:25:25 2009
random seeds: 96ab2ec0 20320617
factoring 5991810554633396517767024967580894321153 (40 digits)
prp40 factor: 5991810554633396517767024967580894321153
elapsed time 00:00:00

In any case, are there any tests posted as well as perhaps a testsuite to run?

Dennis

[Jeff Gilchrist]

Originally Posted by blastwave

In any case, are there any tests posted as well as perhaps a testsuite to run?

I'm not sure if Jason has an official test suite, but you can go to a factoring database and choose some numbers of the size you want to test and verify the results match such as: http://factorization.ath.cx/

[blastwave]

Originally Posted by Jeff Gilchrist

...you can go to a factoring database and choose some numbers of the size you want to test...

That page, I'm sad to say, seems to be gobbledygook. I entered a number into the factorize field and then ... nothing.

No, I think I'll just pick 40 digit and 50 digit primes and then multiply them together to get a simple composite. Then is msieve can factor an 80 digit number correctly into two 40 digit primes I should be happy in the knowledge that it seems to work.

Thus :

next number: 21662887038670915563461368246059452237028460443882686940871185423604981619664343


Msieve v. 1.42
Mon Aug 24 23:26:19 2009
random seeds: d5f4c533 38df083a
factoring 21662887038670915563461368246059452237028460443882686940871185423604981619664343 (80 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (80-digit input)
using multiplier of 3
using generic 32kb sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 1217947 (47294 primes)
using large prime bound of 121794700 (26 bits)
using trial factoring cutoff of 27 bits
polynomial 'A' values have 10 factors

sieving in progress (press Ctrl-C to pause)
47418 relations (24166 full + 23252 combined from 258247 partial), need 47390
47418 relations (24166 full + 23252 combined from 258247 partial), need 47390
sieving complete, commencing postprocessing
begin with 282413 relations
reduce to 67795 relations in 2 passes
attempting to read 67795 relations
recovered 67795 relations
recovered 57746 polynomials
attempting to build 47418 cycles
found 47418 cycles in 1 passes
distribution of cycle lengths:
length 1 : 24166
length 2 : 23252
largest cycle: 2 relations
matrix is 47294 x 47418 (6.9 MB) with weight 1422565 (30.00/col)
sparse part has weight 1422565 (30.00/col)
filtering completed in 3 passes
matrix is 33804 x 33867 (5.4 MB) with weight 1135443 (33.53/col)
sparse part has weight 1135443 (33.53/col)
saving the first 48 matrix rows for later
matrix is 33756 x 33867 (3.6 MB) with weight 832954 (24.59/col)
sparse part has weight 597783 (17.65/col)
matrix includes 64 packed rows
using block size 13546 for processor cache size 512 kB
commencing Lanczos iteration
memory use: 3.9 MB
lanczos halted after 535 iterations (dim = 33754)
recovered 16 nontrivial dependencies
prp40 factor: 3615415881585117908550243505309785526231
prp40 factor: 5991810554633396517767024967580894321153
elapsed time 00:33:51

So that works.

[10metreh]

Originally Posted by blastwave

That page, I'm sad to say, seems to be gobbledygook. I entered a number into the factorize field and then ... nothing.

It should come up with the number you entered. It shouldn't come up with the factors immediately.

[Andi47]

I just spotted that I accidently might have placed one of the betas of 1.42 into my GGNFS folder, or simply forgot to update. (AFIK only 1.42, but not the beta does in-memory singleton-removal from the beginning).

May I suggest, that any SVN or beta which is NOT an official version with an "official" number like 1.42 or 1.43 would print something like "msieve 1.42 SVN33" or "msieve 1.43 beta 1" to the logfile, so that it would be easier to spot which version or SVN is actually running? (this might also be important for bug reports - one might end up searching for a bug which had occurred in SVN<two umbers ago> and is already fixed in SVN<up-to-date>)

BTW: This also applies to the "newton iteration failed" which I reported over there in the 1.42 feedback thread a few days ago - the version is actually a beta - can't say for sure if beta1 or beta2 - just because the logfile doesn't tell me.