[QUOTE=JHansen]Or, continuing on Paul's suggestion, take a look at the Lanczos code for NFS.

One thing that has bothered me some time now, is that none of the major NFS implementations (GGNFS,CWI and Franke et. al.) have support for running the linear algebra on more then one CPU. I've recently completed a matrix, and that took me 24 days. I'm sure this figure could be brought down a lot if I had been able to use all four CPU's on the computer.

I know NFSNET has a parallel version of the lanczos code from CWI, but is that is heavily licenced, and not availlable to us mere mortals. :rolleyes:
[/QUOTE]That would be a worthy achievement, indeed.

Another suggestion: write fast and memory-efficient programs to remove duplicates and singletons from a collection of relations. Remember that singletons occur in prime ideals, not in primes (except for linear polynomials where they are the same) and so if a prime occurs once in each of two different relations, it could belong to different ideals and so both relations would be removed. Remember, also, that prime ideals on one side do not match those on the other.

Ensure that your code works correctly on 32-bit machines with limited physical memory, where the maximum file size may be smaller than the total space taken up by the collection and the prime ideals in the relations may be up to, say, 48 bits in size. That is, you should be able to specify maximum memory use and maximum file size to be used and not assume that a prime will fit into a long int.

A somewhat more challenging project: write a filter/merge program that's less resource-hungry than the CWI version and/or creates a smaller matrix without increasing its density unduly.

I don't ask for much, do I?

Paul

I could add support for msieve to the next release of ECMNet (the 2.6 release, not the upcoming 2.5 release). That would make a few people happy...

[QUOTE=akruppa]Dear Jason,

would you like to add an API so your code can be included in other packages? I've compared msieve to the MPQS included in Pari/GP on a c60, yours took 113s while gp took 502s, almost four times as long. Perhaps the Pari group would like to include your code in gp?
[/QUOTE]

An external API shouldn't be difficult at all.

What machine was this on? My 1GHz K7 can factor a C60 in ~22 seconds.

jasonp

A Pentium-3 500 MHz, built with gcc 3.4 and -march petium3.

Alex

Just finished a test with the Win binary on a current C98 from the [URL=http://xyyxf.at.tut.by/]XYYXF-Project[/URL] (remaining composite factor of 135^129+129^135) :

[QUOTE]Msieve v. 0.87
random seeds: 00000148 41bcbb76
input to factor: factoring 55306274586393503759204077009511216978122667363582888
891525962393354443122157897021114787184932999
Sun Dec 12 22:43:18 2004
using multiplier of 7
Sun Dec 12 22:43:21 2004
using sieve block of 65536
using a sieve bound of 1813003 (67752 primes)
using large prime bound of 431494714
using double large prime bound of 3491048112625402


sieving in progress (press Ctrl-C to pause)
found 67939 relations (15100 full + 52839 partial), need 67880
begin with 1305275 relations
reduce to 170230 relations in 12 passes
attempting to read 15100 full and 170230 partial relations
recovered 15100 full and 170230 partial relations
recovered 183463 polynomials
attempting to build 52839 cycles
found 52838 cycles in 6 passes
distribution of cycle lengths:
length 2 : 11363
length 3 : 11488
length 4 : 9396
length 5 : 7282
length 6 : 5002
length 7 : 3307
length 8 : 2080
length 9+: 2920
largest cycle: 21 relations
Mon Dec 13 17:10:26 2004
67752 x 67816 system, weight 4825745 (avg 71.16/col)
reduce to 67116 x 67180 in 3 passes
lanczos halted after 1064 iterations
recovered 62 nontrivial dependencies
Mon Dec 13 17:15:03 2004
probable prime factor: 670835676887414404450531442698119811
probable prime factor: 82443848012089991282671595442342852949675881896980280729217709
Mon Dec 13 17:16:06 2004[/QUOTE]
Found the P36 within 18.5 h on my XP2400+, very impressive, thanks for the great tool !
Size of the final msieve.dat file was about 99 MB.

There's a typo in my earlier posting: the msieve time for the c60 was 133s, not 113.

I tried to reproduce which number exactly I factored, I think it was 314159265358979323846264338328907078125461821459237067283727 = 314159265358979323846264338311 * 1000000000000000000000000000057

A new run took 128s on my Pentium-III. Unfortunately I have no Athlon available to compare timings with the 22s you mentioned.

Alex

[QUOTE=akruppa]There's a typo in my earlier posting: the msieve time for the c60 was 133s, not 113.

I tried to reproduce which number exactly I factored, I think it was 314159265358979323846264338328907078125461821459237067283727 = 314159265358979323846264338311 * 1000000000000000000000000000057

A new run took 128s on my Pentium-III. Unfortunately I have no Athlon available to compare timings with the 22s you mentioned.

Alex[/QUOTE]

[code]
Msieve v. 0.87
random seeds: 00000d48 41be0c8a
input to factor: 314159265358979323846264338328907078125461821459237067283727
factoring 314159265358979323846264338328907078125461821459237067283727
Mon Dec 13 22:41:49 2004
using multiplier of 3
Mon Dec 13 22:41:49 2004
using sieve block of 65536
using a sieve bound of 56527 (2882 primes)
using large prime bound of 2769823


sieving in progress (press Ctrl-C to pause)
found 3072 relations (1414 full + 1658 partial), need 3010
begin with 13346 relations
reduce to 3077 relations in 2 passes
attempting to read 1414 full and 3077 partial relations
recovered 1414 full and 3077 partial relations
recovered 3742 polynomials
attempting to build 1658 cycles
found 1658 cycles in 1 passes
distribution of cycle lengths:
length 2 : 1658
largest cycle: 2 relations
Mon Dec 13 22:42:02 2004
2882 x 2946 system, weight 73985 (avg 25.11/col)
reduce to 2727 x 2791 in 3 passes
lanczos error: not all columns used
lanczos halted after 44 iterations
linear algebra failed; retrying...
lanczos halted after 45 iterations
recovered 62 nontrivial dependencies
Mon Dec 13 22:42:03 2004
probable prime factor: 314159265358979323846264338311
probable prime factor: 1000000000000000000000000000057
Mon Dec 13 22:42:04 2004

[/code]

15 seconds with an Athlon XP 2100+

Luigi

13 s with an XP 2400+ (2 GHz).

17 s with PowerMac G5 2.5 GHz (in 32-bit mode)

103 seconds on a Celeron 1.8 GHz

Luigi

gcc bug?
 

If all you involuntary beta testers could do me a favor...

I think I've finally tracked down a nasty bug in the cycle-
finding code, and it seems to be compiler-dependent

If you have logs from old factorizations using 0.86 or
0.87 lying around, look for the lines that read:

(X full + Y partial)

[...]

attempting to build Y1 cycles

[...]

found Y2 cycles in Z passes

Correct operation requires Y, Y1 and Y2 to all be the same. Some
of the published reports from big factorizations, however, have all
these numbers different. If Y2 > Y1 you have a memory leak at best,
and possibly a buffer overflow.

I use gcc 3.4.1 locally and have never had this problem. The problem
occurs with bleeding-edge gcc 4.0 with optimization turned on (but not
if optimization is turned off). Are there other gcc versions for which you
see this symptom occur?

FWIW the win32 binary is built with gcc 3.4.1; if you've seen the
problem with the prebuilt msieve.exe I'd be really interested to hear it.

<sigh> This is hard enough without having to fight one's tools.

jasonp