Feedback for new MPQS utility sought

[jasonp]

Originally Posted by dave_dm

The only problem I had was compiling it - gcc couldn't find aligned_malloc or aligned_free and they don't seem to be in any include file on my system. (FYI I run gcc 3.4.3, glibc 2.3.4-20041102). I changed these to normal malloc/frees and all was ok (apart from the nonalignment!) Have any other Linux users had this problem or had I just forgotten to link something in? If not, it's an easy task to write homemade versions of these functions.

I join with others in suggesting that you write a Makefile to go with the next release - else I'll write one myself

aligned_{malloc|free} should be program-local, in util.[ch]

I'll throw a makefile into the next version, but nobody's allowed to
complain about the compile options being wrong or their version
of make not working

[jasonp]

I've just finished a successful factorization of RSA110 using
msieve v0.86; output from the final restart is appended.

Many thanks to Tom for contributing ~30% of the relations that
were needed. I estimate that the complete factorization needed
~16.4 CPU-days, where the CPU is a 2GHz Opteron. I think
that time can be improved with less suboptimal parameter choices.
By way of comparison, someone just used GGNFS to factor a C114
in 3-4 days on a single (approximately comparable) CPU.

When I started work in earnest on this code, I thought I'd be happy
if it could manage a C100. At the time a factorization that big seemed
unimaginably huge. I guess I'm getting greedy now

Work has started on triple large primes. SQUFOF is the clear winner
for factoring integers 62 bits and under, but for 63-93 bit hard integers
it's not clear at all which method can manage the best throughput.
Sieve-based methods have tons of overhead, and the exponential
methods need millions of iterations at that size. Does a single ECM
curve have the same probability of succeeding as a P-1 run?

Anyway, this calls for a banana, to whit:

jasonp

Msieve v. 0.86
random seeds: 000018e8 41b1bd60
factoring 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
Sat Dec  4 08:36:32 2004
using multiplier of 3
Sat Dec  4 08:36:35 2004
using sieve block of 65536
using a sieve bound of 2016551 (74992 primes)
using large prime bound of 604965300
using double large prime bound of 6413791293514800
skipping 1159 corrupt relations
restarting with 14565 full and 2127558 partial relations

found 453531 relations (14565 full + 438966 partial), need 75120
begin with 2128707 relations
reduce to 886950 relations in 8 passes
attempting to read 14573 full and 886950 partial relations
failed to read relation 1555380
failed to read relation 1555381
[...]
failed to read relation 1556517
failed to read relation 1556522
recovered 14565 full and 886738 partial relations
recovered 859527 polynomials
freed 2492 duplicate relations
freed 375701 duplicate relations
attempting to build 63174 cycles
found 63174 cycles in 7 passes
distribution of cycle lengths:
   length 2 : 9737
   length 3 : 10924
   length 4 : 10111
   length 5 : 9118
   length 6 : 7027
   length 7 : 5539
   length 8 : 3938
   length 9+: 6780
largest cycle: 22 relations
Sat Dec  4 08:39:06 2004
74992 x 75056 system, weight 7109876 (avg 94.73/col)
reduce to 74850 x 74914 in 3 passes
lanczos halted after 1185 iterations
recovered 63 nontrivial dependencies
Sat Dec  4 08:40:45 2004
probable prime factor: 5846418214406154678836553182979162384198610505601062333
probable prime factor: 6122421090493547576937037317561418841225758554253106999
Sat Dec  4 08:41:29 2004

[ET_]

Originally Posted by jasonp

I've just finished a successful factorization of RSA110 using
msieve v0.86; output from the final restart is appended.

Many thanks to Tom for contributing ~30% of the relations that
were needed. I estimate that the complete factorization needed
~16.4 CPU-days, where the CPU is a 2GHz Opteron. I think
that time can be improved with less suboptimal parameter choices.
By way of comparison, someone just used GGNFS to factor a C114
in 3-4 days on a single (approximately comparable) CPU.

When I started work in earnest on this code, I thought I'd be happy
if it could manage a C100. At the time a factorization that big seemed
unimaginably huge. I guess I'm getting greedy now

Work has started on triple large primes. SQUFOF is the clear winner
for factoring integers 62 bits and under, but for 63-93 bit hard integers
it's not clear at all which method can manage the best throughput.
Sieve-based methods have tons of overhead, and the exponential
methods need millions of iterations at that size. Does a single ECM
curve have the same probability of succeeding as a P-1 run?

Anyway, this calls for a banana, to whit:

jasonp

Msieve v. 0.86
random seeds: 000018e8 41b1bd60
factoring 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
Sat Dec  4 08:36:32 2004
using multiplier of 3
Sat Dec  4 08:36:35 2004
using sieve block of 65536
using a sieve bound of 2016551 (74992 primes)
using large prime bound of 604965300
using double large prime bound of 6413791293514800
skipping 1159 corrupt relations
restarting with 14565 full and 2127558 partial relations

found 453531 relations (14565 full + 438966 partial), need 75120
begin with 2128707 relations
reduce to 886950 relations in 8 passes
attempting to read 14573 full and 886950 partial relations
failed to read relation 1555380
failed to read relation 1555381
...
failed to read relation 1556517
failed to read relation 1556522
recovered 14565 full and 886738 partial relations
recovered 859527 polynomials
freed 2492 duplicate relations
freed 375701 duplicate relations
attempting to build 63174 cycles
found 63174 cycles in 7 passes
distribution of cycle lengths:
   length 2 : 9737
   length 3 : 10924
   length 4 : 10111
   length 5 : 9118
   length 6 : 7027
   length 7 : 5539
   length 8 : 3938
   length 9+: 6780
largest cycle: 22 relations
Sat Dec  4 08:39:06 2004
74992 x 75056 system, weight 7109876 (avg 94.73/col)
reduce to 74850 x 74914 in 3 passes
lanczos halted after 1185 iterations
recovered 63 nontrivial dependencies
Sat Dec  4 08:40:45 2004
probable prime factor: 5846418214406154678836553182979162384198610505601062333
probable prime factor: 6122421090493547576937037317561418841225758554253106999
Sat Dec  4 08:41:29 2004

I am following GGNFS list and just started msieve 0.86 on 279802417050925240147946030591565340733962949895822646350930721424025002920927740807930564434975939126006501

It will take a while, though, as I'm working on an Athlon 2100+ XP @ 1736 MHz. 1207 total relation collected thusfar, need 75128.

Maybe I'll start a new client with the same number on my 2GHz Celery to speed up the search. Or we may beta-test a first distributed effort on this number...

Luigi

[jasonp]

Originally Posted by ET_

It will take a while, though, as I'm working on an Athlon 2100+ XP @ 1736 MHz. 1207 total relation collected thusfar, need 75128.

Note that I have not done extensive experiments with >100 digit
factorizations, so that the factor base you're using is probably too small.

Originally Posted by ET_

Maybe I'll start a new client with the same number on my 2GHz Celery to speed up the search. Or we may beta-test a first distributed effort on this number...

Going distributed is a good idea; my guess is that using your XP2100 alone
is going to take ~14 days. I don't think I'll be able to help, though: by the
time you finish you're going to have ~500MB of savefiles, although there's
a simple trick that the next version uses to reduce that number drastically.
I can download someone else's results but I don't have anywhere to upload
results I generate.

jasonp

[smh]

I am following GGNFS list and just started msieve 0.86 on 279802417050925240147946030591565340733962949895822646350930721424025002920927740807930564434975939126006501

GGNFS is clearly faster on numbers of this size. Last week i did a C108 in about 9 days on a P3@700, and the latest version is much faster in processing relations and the sqrt step. Using this latest version and better parameters, i think i could have done it in a week. Your pc should be able to do it in a day or two.

Just out of interest, what number is this?

I would like to add that msieve is a great factorization tool. Much faster than the widly used ppsiqs.exe, but for numbers > 100 digits, GNFS is clearly the faster method.

I have one more request though. It would be great if the program can factor multiple numbers from 1 input file. Currently it does only the first number. I have quiet a few numbers in the 85-95 digit range and a pc that i can only access once or twice a week.

[ET_]

Originally Posted by smh

GGNFS is clearly faster on numbers of this size. Last week i did a C108 in about 9 days on a P3@700, and the latest version is much faster in processing relations and the sqrt step. Using this latest version and better parameters, i think i could have done it in a week. Your pc should be able to do it in a day or two.

Just out of interest, what number is this?

I would like to add that msieve is a great factorization tool. Much faster than the widly used ppsiqs.exe, but for numbers > 100 digits, GNFS is clearly the faster method.

I have one more request though. It would be great if the program can factor multiple numbers from 1 input file. Currently it does only the first number. I have quiet a few numbers in the 85-95 digit range and a pc that i can only access once or twice a week.

I know GNFS is faster, I only wanted to help testing msieve with big numbers


The number is a C108 I found tested with GNFS. I also saw a C114 but I'm not trying to test it

Luigi

[jasonp]

Originally Posted by smh

I have one more request though. It would be great if the program can factor multiple numbers from 1 input file. Currently it does only the first number. I have quiet a few numbers in the 85-95 digit range and a pc that i can only access once or twice a week.

Earlier versions were capable of multiple factorizations in batch mode, but
I removed that capability because otherwise you'd run the risk of overwriting
the (one) savefile.

In the short term, you could put multiple factorizations in a script or batch file;
I'll look into adding batch mode back into the next version.

jasonp

[Phil MjX]

Originally Posted by ET_

I know GNFS is faster, I only wanted to help testing msieve with big numbers


The number is a C108 I found tested with GNFS. I also saw a C114 but I'm not trying to test it

Luigi

Hi ET and Sander.

This number is in fact a x^y+y^x number from Andrey Kulsha's list. It is the so named c108_108_26 I have factored a few days ago...
Why not trying to factorize numbers whose status is unknown?? It seems easy to verify that the process went OK by multiplying the two factors found together!!

Best regards to you.
Philippe S.

[smh]

Earlier versions were capable of multiple factorizations in batch mode, but
I removed that capability because otherwise you'd run the risk of overwriting
the (one) savefile.

Default writing of the factorization to a log file would be very useful too. I once started msieve from the windows explorer, After the factorization was done, the window disappeared. I managed to get the fatorization by restarting the save file, but this almost wasted a full day of cpu.

Once a factorization is done i don't mind loosing the save file, as long as the result is written to a file.

In the short term, you could put multiple factorizations in a script or batch file;
I'll look into adding batch mode back into the next version.

I thought of that myself and will do that next time i have access to that server, but a batch version would still be great though.

[smh]

Why not trying to factorize numbers whose status is unknown?? It seems easy to verify that the process went OK by multiplying the two factors found together!!

Agreed!! At least try factoring a number whose status is unknown.

[Mystwalker]

Originally Posted by jasonp

Does a single ECM curve have the same probability of succeeding as a P-1 run?

ECM is probabilistic, so there is a certain chance finding a suitable factor. P-1 finds every factor within bounds. In general (and given equal bounds), an ECM curve is a lot less likely to find a factor (given that the factor size and shape is unknown) than a P-1 run, but is a lot faster.
But using a certain pair of bounds with P-1 and don't finding a factor doesn't mean that ECM with the same bounds won't find any.
Maybe this thread gives a little more info on that occurence: http://www.mersenneforum.org/showthread.php?t=3135