Feedback for new MPQS utility sought

[error404]

Jason,

The 98 digit test number from ggnfs failed.

Tom

/******************************************************************************/

AMD64-3400+, 1M L2, 2G PC3200
Gigabyte GA-K8VT800M motherboard

gigabyte#
gigabyte# uname -a
FreeBSD gigabyte.dl.cox.net 5.3-RELEASE-p1 FreeBSD 5.3-RELEASE-p1 #0: Mon Nov 22 20:37:33 CST 2004
root@gigabyte.dl.cox.net:/usr/src/sys/amd64/compile/MYKERNEL amd64
gigabyte#
gigabyte#
gigabyte# gcc34 -v
Reading specs from /usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/specs
Configured with: ./..//gcc-3.4-20041119/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --program-suffix=34 --with-gxx-include-dir=/usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/include/c++/ --disable-shared --disable-libgcj --prefix=/usr/local x86_64-portbld-freebsd5.3
Thread model: posix
gcc version 3.4.4 20041119 (prerelease) [FreeBSD]
gigabyte#
gigabyte#
gigabyte# gcc34 -O3 -march=k8 *.c -o qs082 -lm
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte# time ./qs082 < tsts1c98.txt
Msieve v. 0.82

random seeds: 0000033b 41a2bd4e
input to factor:
factoring 48112675629372767804524219707530062462251150382843481915847109420993527839223554575368891438718253
Mon Nov 22 22:32:14 2004
using multiplier of 1
Mon Nov 22 22:32:16 2004
using a sieve bound of 1812661 (67941 primes)
using large prime bound of 431413318
using double large prime bound of 3489862815056296

sieving in progress (press Ctrl-C to pause)
found 5 relations (5 full + 0 partial), need 68069
found 10 relations (10 full + 0 partial), need 68069
|
|
found 68053 relations (13554 full + 54499 partial), need 68069
found 68105 relations (13559 full + 54546 partial), need 68069
begin with 1329546 relations
reduce to 181315 relations in 12 passes
attempting to read 13559 full and 181315 partial relations
recovered 13559 full and 181315 partial relations
recovered 174525 polynomials
attempting to build 54546 cycles
found 54546 cycles in 6 passes
distribution of cycle lengths:
length 2 : 10216
length 3 : 10596
length 4 : 9454
length 5 : 7802
length 6 : 5712
length 7 : 4044
length 8 : 2667
length 9+: 4055
Tue Nov 23 23:28:47 2004
67941 x 68005 system, weight 5216229 (avg 76.70/col)
reduce to 67514 x 67578 in 3 passes
error: submatrix is not invertible
89710.012u 291.098s 25:03:32.77 99.7% 76+91338k 1+969io 0pf+0w
gigabyte#
gigabyte#

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

[BotXXX]

The following C98 went with out problems (version 0.80) on a slow Pentium M 1.4 Ghz laptop with WinXP:

msieve
input to factor: 30426235906460915022335516259603934752642860427748174515035130
90727867734745868467895848169399513

factoring 304262359064609150223355162596039347526428604277481745150351305907278
7734745868467895848169399513
Tue Nov 23 08:23:17 2004
324 bits 67647 primes bound 1799407
using multiplier of 1
Tue Nov 23 08:23:21 2004
using a sieve bound of 1799407 (67647 primes)
using large prime bound of 412064203
using double large prime bound of 3213192593896588
restarting from polynomial 379068
restarting with 7368 full and 710351 partial relations

sieving in progress (press Ctrl-C to pause)
found 67813 relations (13595 full + 54218 partial), need 67775
begin with 1318488 relations
reduce to 180293 relations in 10 passes
attempting to read 13595 full and 180293 partial relations
recovered 13595 full and 180293 partial relations
recovered 169286 polynomials
attempting to build 54218 cycles
found 54218 cycles in 6 passes
distribution of cycle lengths:
   length 2 : 10230
   length 3 : 10647
   length 4 : 9263
   length 5 : 7648
   length 6 : 5666
   length 7 : 4021
   length 8 : 2711
   length 9+: 4032
Tue Nov 23 21:40:57 2004
67647 x 67711 system, weight 5168422 (avg 76.33/col)
reduce to 67219 x 67283 in 3 passes
lanczos halted after 1065 iterations
recovered 64 nontrivial dependencies
Tue Nov 23 21:43:19 2004
probable prime factor: 11133794754447104519411036291181671454112777
probable prime factor: 2732782180514684540668644555428942980240496674688562769
Tue Nov 23 21:44:41 2004

Now trying to run a C110 on the same machine with version 0.83

[smh]

Now trying to run a C110 on the same machine with version 0.83

I'm interested in the runtime to see how this compares to GNFS

[jasonp]

Originally Posted by BotXXX

The following C98 went with out problems (version 0.80) on a slow Pentium M 1.4 Ghz laptop with WinXP:

Now trying to run a C110 on the same machine with version 0.83

Eek. I suppose that theoretically the latest code will handle factorizations
that big, but I'd be amazed if it took less than two weeks.

From some of the posts in the ggnfs egroup, a c102 takes ~20 hours
with proper tuning. That's already faster than this code can manage at
present, though I have several ideas for improvements.

jasonp

[jasonp]

Originally Posted by error404

The 98 digit test number from ggnfs failed.

error: submatrix is not invertible

Rats. Tom, does the failure persist if you do a restart on this number?
It could be that this is recoverable.

I'll start it running locally.
jasonp

[error404]

Jason,

The restart worked correctly.

Tom


gigabyte#
gigabyte# time ./qs082 < tsts1c98.txt
Msieve v. 0.82

random seeds: 00000222 41a48de9
input to factor:
factoring 48112675629372767804524219707530062462251150382843481915847109420993527839223554575368891438718253
Wed Nov 24 07:34:33 2004
using multiplier of 1
Wed Nov 24 07:34:34 2004
using a sieve bound of 1812661 (67941 primes)
using large prime bound of 431413318
using double large prime bound of 3489862815056296
restarting from polynomial 879502
restarting with 13559 full and 1329546 partial relations

begin with 1329546 relations
reduce to 181315 relations in 12 passes
attempting to read 13559 full and 181315 partial relations
recovered 13559 full and 181315 partial relations
recovered 174525 polynomials
attempting to build 54546 cycles
found 54546 cycles in 6 passes
distribution of cycle lengths:
length 2 : 10216
length 3 : 10596
length 4 : 9454
length 5 : 7802
length 6 : 5712
length 7 : 4044
length 8 : 2667
length 9+: 4055
Wed Nov 24 07:34:42 2004
67941 x 68005 system, weight 5216229 (avg 76.70/col)
reduce to 67514 x 67578 in 3 passes
lanczos halted after 1069 iterations
recovered 61 nontrivial dependencies
Wed Nov 24 07:35:55 2004
probable prime factor: 2255991822360879425583919003791503
probable prime factor: 21326617921435191345914805886616773334390107640406173073760517251
Wed Nov 24 07:36:23 2004
109.824u 0.913s 1:51.07 99.6% 76+180689k 2+0io 5pf+0w
gigabyte#
gigabyte#

[smh]

From some of the posts in the ggnfs egroup, a c102 takes ~20 hours
with proper tuning. That's already faster than this code can manage at
present, though I have several ideas for improvements.

I've had less luck with good parameters. It also depends on a good polynominal. I think 1.5 to 2 times that runtime is more reasonable on average. It's also much harder to set up.

I have (temporarily) 2 P4's available on which i can't install cygwin to run ggnfs and for which i don't have a lot of time to find reasonable parameters. Running msieve might be slower, but otherwise i couldn't run anything or had to use ppsiqs.exe which is even slower.

I hope you can get msieve more stable an squeeze some more speed out of it.

[jasonp]

Originally Posted by error404

The restart worked correctly.

Great. So this is another condition that's just bad luck in the
matrix code. The next version will restart the linear algebra
automatically if it's encountered.

jasonp

[error404]

Jason,

RSA100 failed on the 1st try and then found the factors on the 2nd try.

Tom

/******************************************************************************/

AMD64-3400+, 1M L2, 2G PC3200
Gigabyte GA-K8VT800M motherboard

gigabyte#
gigabyte# uname -a
FreeBSD gigabyte.dl.cox.net 5.3-RELEASE-p1 FreeBSD 5.3-RELEASE-p1 #0: Mon Nov 22 20:37:33 CST 2004
root@gigabyte.dl.cox.net:/usr/src/sys/amd64/compile/MYKERNEL amd64
gigabyte#
gigabyte#
gigabyte# gcc34 -v
Reading specs from /usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/specs
Configured with: ./..//gcc-3.4-20041119/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --program-suffix=34 --with-gxx-include-dir=/usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/include/c++/ --disable-shared --disable-libgcj --prefix=/usr/local x86_64-portbld-freebsd5.3
Thread model: posix
gcc version 3.4.4 20041119 (prerelease) [FreeBSD]
gigabyte#
gigabyte#
gigabyte# gcc34 -O3 -march=k8 *.c -o qs083 -lm
gigabyte#
gigabyte#
gigabyte#
gigabyte# time ./qs083 < rsa100.txt

Msieve v. 0.83
random seeds: 00000278 41a490ea
input to factor: factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Wed Nov 24 07:47:22 2004
using multiplier of 31
Wed Nov 24 07:47:24 2004
using a sieve bound of 1855327 (69248 primes)
using large prime bound of 523202214
using double large prime bound of 4938615570410940

sieving in progress (press Ctrl-C to pause)
found 5 relations (5 full + 0 partial), need 69376
found 10 relations (10 full + 0 partial), need 69376
|
|
found 69284 relations (13973 full + 55311 partial), need 69376
found 69388 relations (13978 full + 55410 partial), need 69376
begin with 1484207 relations
reduce to 184693 relations in 11 passes
attempting to read 13978 full and 184693 partial relations
recovered 13978 full and 184693 partial relations
recovered 180451 polynomials
attempting to build 55410 cycles
found 55410 cycles in 6 passes
distribution of cycle lengths:
length 2 : 10451
length 3 : 10863
length 4 : 9640
length 5 : 7723
length 6 : 5818
length 7 : 4109
length 8 : 2711
length 9+: 4095
Thu Nov 25 14:02:49 2004
69248 x 69312 system, weight 5142900 (avg 74.20/col)
reduce to 68818 x 68882 in 3 passes
error: submatrix is not invertible
108721.119u 332.088s 30:21:24.84 99.7% 76+100039k 1+1140io 0pf+0w
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte# time ./qs083 < rsa100.txt

Msieve v. 0.83
random seeds: 00001232 41a64171
input to factor: factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Thu Nov 25 14:32:49 2004
using multiplier of 31
Thu Nov 25 14:32:51 2004
using a sieve bound of 1855327 (69248 primes)
using large prime bound of 523202214
using double large prime bound of 4938615570410940
restarting from polynomial 1033648
restarting with 13978 full and 1484207 partial relations

begin with 1484207 relations
reduce to 184693 relations in 11 passes
attempting to read 13978 full and 184693 partial relations
recovered 13978 full and 184693 partial relations
recovered 180451 polynomials
attempting to build 55410 cycles
found 55410 cycles in 6 passes
distribution of cycle lengths:
length 2 : 10451
length 3 : 10863
length 4 : 9640
length 5 : 7723
length 6 : 5818
length 7 : 4109
length 8 : 2711
length 9+: 4095
Thu Nov 25 14:33:00 2004
69248 x 69312 system, weight 5142900 (avg 74.20/col)
reduce to 68818 x 68882 in 3 passes
lanczos halted after 1090 iterations
recovered 64 nontrivial dependencies
Thu Nov 25 14:34:12 2004
probable prime factor: 37975227936943673922808872755445627854565536638199
probable prime factor: 40094690950920881030683735292761468389214899724061
Thu Nov 25 14:34:42 2004
112.604u 0.953s 1:53.92 99.6% 76+181555k 0+0io 0pf+0w
gigabyte#
gigabyte#
gigabyte#
gigabyte# ls -l
|
|
-rw-r--r-- 1 root k5gj 40936641 Nov 25 14:02 msieve.pol
-rw-r--r-- 1 root k5gj 115977005 Nov 25 14:02 msieve.rel
|
|
gigabyte#
gigabyte#

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

[jasonp]

Version 0.84 is now available. Highlights include:

- automatically restarts the matrix step if a recoverable error
occurs (sorry Tom)

- complete overhaul of the savefile handling. Reading and writing
of savefiles is much more robust now, and I've gone from two
savefiles down to one combined savefile. NOTE: Savefiles from
different runs, or different machines, can be blindly concat-
enated together and the program can now start on the combined
savefile. This makes (labor intensive) distributed computing possible.

- automatic cache size detection for Intel and AMD processors. I've
verified this works on K7/K8 and Pentium M systems; the former
works like before, the latter seems to sieve ~5% faster with the
correct cache size. I don't have a P4 to test with, and frankly
have no idea how much of a difference it makes to correctly guess
the size of the P4's tiny cache (my guess is zero; tiny cache +
writethrough-not-writeback = inevitably dismal sieving performance).
PowerPC processors have their cache size hardwired at compile time
(all latter-day PPCs have a 32kB L1 cache). Look for 'sieve block size'
in the output and let me know if I got it wrong for your machine.

Enjoy
jasonp

[error404]

Jason,

I downloaded the new version 0.84 and tried a simple test with the 25
digit number 1111111111111111111111111, which is the smallest that will
generate the msieve.dat file.

I compiled msieve084 on my Macintosh with gcc34 and then with
IBM's XLC. Both work correctly.

Tom

/******************************************************************************/

Motorola PPc-7455 (Titanium Laptop)
G4-867, 256K L2, 1M L3, 768M PC133, Bus 133MHz

g4-867:~/msieve084 root#
g4-867:~/msieve084 root# uname -a
Darwin g4-867.local 7.6.0 Darwin Kernel Version 7.6.0: Sun Oct 10 12:05:27 PDT 2004; root:xnu/xnu-517.9.4.obj~1/RELEASE_PPC Power Macintosh powerpc
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# /usr/local/bin/gcc34 -v
Reading specs from /usr/local/lib/gcc/powerpc-apple-darwin7.6.0/3.4.4/specs
Configured with: /usr/gcc-3.4-20041119/./configure --program-suffix=34 --enable-languages=c,c++ --disable-nls
Thread model: posix
gcc version 3.4.4 20041119 (prerelease)
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# /usr/local/bin/gcc34 -O3 -mtune=7450 *.c -o qs084gcc
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# ./qs084gcc 1111111111111111111111111

Msieve v. 0.84
random seeds: 00000a15 41a733d0
factoring 1111111111111111111111111
Fri Nov 26 07:46:56 2004
prime factor: 41
prime factor: 271
using multiplier of 1
Fri Nov 26 07:46:56 2004
using sieve block of 32768
using a sieve bound of 1303 (119 primes)
using large prime bound of 52120

sieving in progress (press Ctrl-C to pause)
found 674 relations (212 full + 462 partial), need 247
begin with 1431 relations
reduce to 771 relations in 2 passes
attempting to read 212 full and 771 partial relations
recovered 212 full and 771 partial relations
recovered 1 polynomials
attempting to build 462 cycles
found 462 cycles in 1 passes
distribution of cycle lengths:
length 2 : 462
largest cycle: 2 relations
Fri Nov 26 07:46:57 2004
119 x 183 system, weight 1776 (avg 9.70/col)
reduce to 110 x 174 in 3 passes
lanczos halted after 3 iterations
recovered 62 nontrivial dependencies
Fri Nov 26 07:46:57 2004
probable prime factor: 21401
probable prime factor: 25601
probable prime factor: 182521213001
Fri Nov 26 07:46:57 2004
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# ls -l
|
|
-rw-r--r-- 1 root root 63249 26 Nov 07:46 msieve.dat
|
|
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#

/******************************************************************************/

g4-867:~/msieve084 root#
g4-867:~/msieve084 root# rm msieve.dat
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# ./xlc
xlc(1) IBM XL C/C++ Advanced Edition xlc(1)
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# ./xlc -O3 -qarch=auto *.c -o qs084xlc
gf2.c:
mp.c:
msieve.c:
1500-036: (I) The NOSTRICT option (default at OPT(3)) has the potential to alter the semantics of a program. Please refer to documentation on the STRICT/NOSTRICT option for more information.
poly.c:
relation.c:
sieve.c:
sqrt.c:
squfof.c:
1500-010: (W) WARNING in squfof: Infinite loop. Program may not stop.
1500-036: (I) The NOSTRICT option (default at OPT(3)) has the potential to alter the semantics of a program. Please refer to documentation on the STRICT/NOSTRICT option for more information.
util.c:
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root# ./qs084xlc 1111111111111111111111111

Msieve v. 0.84
random seeds: 00000a1a 41a734b0
factoring 1111111111111111111111111
Fri Nov 26 07:50:40 2004
prime factor: 41
prime factor: 271
using multiplier of 1
Fri Nov 26 07:50:40 2004
using sieve block of 65536
using a sieve bound of 1303 (119 primes)
using large prime bound of 52120

sieving in progress (press Ctrl-C to pause)
found 822 relations (253 full + 569 partial), need 247
begin with 1644 relations
reduce to 925 relations in 2 passes
attempting to read 253 full and 925 partial relations
recovered 253 full and 925 partial relations
recovered 1 polynomials
attempting to build 569 cycles
found 569 cycles in 1 passes
distribution of cycle lengths:
length 2 : 569
largest cycle: 2 relations
Fri Nov 26 07:50:40 2004
119 x 183 system, weight 1762 (avg 9.63/col)
reduce to 114 x 178 in 2 passes
lanczos halted after 3 iterations
recovered 64 nontrivial dependencies
Fri Nov 26 07:50:40 2004
probable prime factor: 21401
probable prime factor: 25601
probable prime factor: 182521213001
Fri Nov 26 07:50:41 2004
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
|
|
-rw-r--r-- 1 root root 71840 26 Nov 07:50 msieve.dat
|
|
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#
g4-867:~/msieve084 root#

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/