Feedback for new MPQS utility sought

[wblipp]

I completed a C92 on an Athlon XP 2600+ (1.8 Ghz) in 16:13:37.


This time may reflect cache thrashing because Dario Alpern's Java Factoring applet was running at low priority at the same time.

[alpertron]

In contrast my applet takes about 15 hours in a P4 2.4 GHz to complete the factorization using SIQS with large primes. Aftre entering the C83, enter 0 in the New Curve box and press the button.

The big difference in times comes from the bad performance in Java for array usage, compared to C and Assembler. For ECM, the applet runs at about the same speed of GMP-ECM in AMD machines when B1 <= 10^6.

[ET_]

Hi Jason, I noticed a problem with your siqs.exe program.

When I try to factor 77777777777 I get this screenshot:

C:\Documents and Settings\Cygni_61\Desktop>siqs 77777777777

factoring 77777777777
Sat Nov 13 16:53:36 2004
prime factor: 7
using multiplier of 1
Sat Nov 13 16:53:36 2004
using a sieve bound of 491 (59 primes)
using large prime bound of 19640
fatal error: poly selection failed

When I try to factor 77777777777777777 I get this screenshot:

C:\Documents and Settings\Cygni_61\Desktop>siqs 77777777777777777

factoring 77777777777777777
Sat Nov 13 16:59:05 2004
prime factor: 7
using multiplier of 1
Sat Nov 13 16:59:05 2004
using a sieve bound of 479 (54 primes)
using large prime bound of 19160
fatal error: poly selection failed

Finally, when I try to factor 7777777777777777777777777 I get

C:\Documents and Settings\Cygni_61\Desktop>siqs 7777777777777777777777777

factoring 7777777777777777777777777
Sat Nov 13 17:00:34 2004
prime factor: 7
prime factor: 41
prime factor: 271
using multiplier of 1
Sat Nov 13 17:00:34 2004
using a sieve bound of 499 (52 primes)
using large prime bound of 19960
fatal error: poly selection failed

Is it only a problem of mine?

Addendum:
It happens with all strings of 11, 17 and 25 repdigits.

Luigi

[jasonp]

Originally Posted by ET_

Hi Jason, I noticed a problem with your siqs.exe program.

When I try to factor 77777777777 I get this screenshot:

fatal error: poly selection failed

Is it only a problem of mine?

It's not a bug, it's just that the input (possibly after trial factoring)
is too small for the self-initializing quadratic sieve.

The problem is that polynomials the program attempts to use have
leading coefficients that must be the product of at least two small
primes, and those two small primes must have at least 7 bits each
(7 bits is really pushing it, 11 or 12 bits is better). This may be impossible
if the input to be factored is small enough, in which case the program
fails. It seems to happen for most inputs that are under 20 digits after
trail factoring.

Pretty much the only solution for these numbers is to switch to another
factoring method; the MPQS code on my web page can factor integers
down to 12 digits, and a much older QS distribution I wrote can go down
to 6 digits.

The next version, due out any day now, will switch to SQUFOF for inputs
under 19 digits.

jasonp

[ET_]

Originally Posted by jasonp

It's not a bug, it's just that the input (possibly after trial factoring) is too small for the self-initializing quadratic sieve.

[...]

The next version, due out any day now, will switch to SQUFOF for inputs
under 19 digits.

jasonp

Thank you Jason.
It seems that I'll have to study QS algorithm to avoid trivial questions...

If I understand your explaination, the number has another factor bigger than the initial sieve, but too small to be headed with the polynomials, so an easy sieve program with a bigger range of primes wil factorize it. Did I get it right?

Luigi

[jasonp]

Originally Posted by ET_

It seems that I'll have to study QS algorithm to avoid trivial questions...

They're not trivial at all; few people get nuts'n'bolts experience with
this stuff.

Originally Posted by ET_

If I understand your explaination, the number has another factor bigger than the initial sieve, but too small to be headed with the polynomials, so an easy sieve program with a bigger range of primes wil factorize it. Did I get it right?

Not exactly. The quadratic sieve attempts to find lots of 'x' for which
(x + square_root(n))^2 - n is smooth. For MPQS, you instead look at
polynomials of the form (a*x+b)^2 - n, where 'a' is a few digits shy of
the square root of n. 'a' is a prime number for MPQS, so if your input
is say 15 digits then 'a' can be ~5 digits at most. Because the 'M' in
MPQS indicates that you need multiple polynomials, when n is small you
have a small number of polynomials you can try (each needs a different
'a' value). QS only ever uses one polynomial, so it can just keep going and
going.

With self-initializing MPQS it gets even worse; there 'a' must be a product
of several different primes, the more the better. But your 15-digit input
would still only allow a ~5 digit 'a' value, so you've got to find two or more
primes whose product is ~5 digits (~14 bits). You can find pairs of primes
that are each 7 bits in size; but there are not too many of such primes,
and even if you kept finding unique pairs of them the sieving would be
inefficient.

The code could detect this and switch to ordinary MPQS with one prime,
but it's conceptually cleaner to just switch to another method entirely.

jasonp

[ET_]

Originally Posted by jasonp

The code could detect this and switch to ordinary MPQS with one prime,
but it's conceptually cleaner to just switch to another method entirely.

jasonp

NOW it's clear to me!
Thank you again, Jason!

Luigi

[jasonp]

I've just uploaded msieve version 0.8; this version contains sweeping
changes at all levels. Highlights are:

- double large primes used for factorizations of 85 digits and up
- automatic checkpoint/restart capability
- block lanczos
- rudimentary tuning up to 105 digits
- continuous progress reporting (though calculation of finish time
will take more work)
- several bugfixes, especially for small inputs

Luigi, I was right that your inputs were too small, but you were
also right that there were bugs involved...two of them in fact

I have verified things work up to 95 digits; the Opteron here is
factoring a c100 right now, and I expect it will take less than 24 hours.

Let me know how it works, and if you find problems. The next items
on the agenda are

- adding a logfile
- making the blocksizes variable for machines with different cache sizes
- revisiting the sieving code to test out a few ideas I have
- triple large primes? Can these really help for non-huge factorizations?
- your suggestion here
- finally getting some sleep

Happy factoring,
jasonp

[JHansen]

I think there is a bug in the new code. Here is the output of a trial factorization I just did:

C:\temp>msieve.exe
input to factor: 112466254807802417585982050550691473603585312325524962438957129
518003538142371

factoring 1124662548078024175859820505506914736035853123255249624389571295180035
38142371
Fri Nov 19 07:58:09 2004
using multiplier of 1
Fri Nov 19 07:58:10 2004
using a sieve bound of 972869 (38176 primes)
using large prime bound of 29186070

sieving in progress (press Ctrl-C to pause)
found 38309 out of 38304 relations (20101 full + 18208 partial)
begin with 140102 relations
reduce to 33871 relations in 2 passes
attempting to read 20101 full and 33871 partial relations
recovered 20101 full and 33871 partial relations
recovered 19188 polynomials
attempting to build 18208 cycles
found 18208 cycles in 1 passes
distribution of cycle lengths:
   length 2 : 18208
Fri Nov 19 08:15:39 2004
38176 x 38240 system, weight 1102080 (avg 28.82/col)
lanczos halted after 587 iterations
lanczos error: only trivial dependencies found

C:\temp>

What do you make of it, Jason?

-----
Cheers,
Jes

[ET_]

Originally Posted by JHansen

found 38309 out of 38304 relations

[xilman]

Originally Posted by jasonp

- triple large primes? Can these really help for non-huge factorizations?

My experience is that 3LP becomes cost-effective compared with 2LP somewhere around 100-105 digits. I expect the exact crossover point to be very implementation dependent. At 135 digits, 3LP is several times faster than 2LP, but several times slower than GNFS. Again, I expect the precise ratio to be very implementation dependent.

I've been informed that the link to my TMPQS (triple-large-prime multiple polynomial quadratic sieve) paper has broken since I left MSR. I'll fix it.


Paul