[QUOTE=jasonp]
There have been more developments on the 3-large-prime front. I tried drastically reducing the size of the factor base, and sieving for my test C100 finished in just 42 hours (the first 3LP run took over 90 hours).[/QUOTE]
Perhaps I should have drawn more attention to the observation that I found 3LP factorizations to need rather smaller factor bases. The pay back is less sieving per quadratic residue and a smaller number of relations needed to complete the factorization. We made this point in our ANTS paper, but perhaps not as emphatically as it should have been.

If you think about the situation carefully, you will realize that allowing for a third large prime means you don't have to sieve with the smallest of the three to find that relation with only 2LP. Ok, this argument is extremely non-rigorous and handwaving, but it can be tightened up.

My experiments showed a 3LP/2LP crossover at around 100 digits. However, the version of QS I was using is markedly less efficient than msieve and it's not surprising that the crossover may be shifted to larger numbers. Remember that the comparison with GNFS is affected similarly --- the more efficient the QS implementation, the higher will be the crossover point. Accordingly, the 3LP version of msieve may well be cost-effective up to, say, 110 or 115 digits.

Paul

[QUOTE=jasonp]I've been experimenting with using triple large primes in msieve, and have modified the sieving stage enough to be able to run some experiments. Originally the code used a 90-bit version of SQUFOF to do the heavy lifting for factoring tri-composites, but that turned out to be really slow. The current version uses a homegrown tiny MPQS implementation which is 5.5x faster. Does anyone know if 10ms to factor an 80-bit number is a good time for a 1GHz CPU? What about 20ms for a 90-bit number?[/QUOTE]
I'm not in the least surprised that SQUFOF was too slow. I used ECM, primarily because one is available in the LIP distribution.

Those timings sound pretty good to me, but I've never measured factorizations that small!

I really hope this question doesn't need to be asked, but just in case: when you get a bi-composite or tri-composite candidate, you do perform a Fermat or Miller-Rabin compositeness test beforehand, don't you? Similarly, do you test the large cofactor of a tri-composite candidate before trying to factor it?

The latter test is vital if SQUFOF or ECM is used, but I don't know the relative costs of a PRP test and seeking for further non-trivial dependencies and a square root extraction if you use MPQS. My guess is that it is worth doing. Should be easy enough to instrument the code and get an unambiguous answer.

Paul

[QUOTE=xilman]
I really hope this question doesn't need to be asked, but just in case: when you get a bi-composite or tri-composite candidate, you do perform a Fermat or Miller-Rabin compositeness test beforehand, don't you? Similarly, do you test the large cofactor of a tri-composite candidate before trying to factor it?
[/QUOTE]
Yes on both counts; the code uses a base-2 pseudoprime test, which is essentially free compared to even 62-bit SQUFOF.
[QUOTE=xilman]
The latter test is vital if SQUFOF or ECM is used, but I don't know the relative costs of a PRP test and seeking for further non-trivial dependencies and a square root extraction if you use MPQS. My guess is that it is worth doing. Should be easy enough to instrument the code and get an unambiguous answer.
[/QUOTE]
Actually, I think one of the big benefits of a small factor base is that factoring candidates of all types become more rare, and even when the input is 100 digits the vast majority of the time is not spent sieving in my 3LP variant.

FYI, here are the final statistics from the C100 run:

[code]
using a sieve bound of 606581 (25000 primes)
3-large-prime bound is 11994106627996407598800 (65-74 bits)
2-large-prime bound is 19773297594214800 (39-55 bits)
1-large-prime bound is 181974300 (28 bits)

candidates surviving the sieve: 98375349
candidates with 1 large prime: 48618
candiates with 2 large primes: 468672
candidates with 3 large primes: 1104279

candidates of size 29-38 bits: 411466
candidates of size 56-64 bits: 16230982
candidates of size > 74 bits 23665206
2LP candidates w/factors > 28 bits: 1180401
2LP candidates that are prime: 2722965
3LP candidates w/factors > 28 bits: 11565604 (*)
3LP candidates that are prime: 26738118
3LP candidates w/2 factors: 14060170 (*)
SQUFOF failures: 2
MPQS failues: 146655 (*)
[/code]

There are MPQS failures because the tiny implementation only finds 8 dependencies, which are not enough about 1/200 of the time. Likewise, there's a slight inaccuracy in the counts of failures; I think it's because some candidates add to more than one category of failure.

All of the cases labeled (*) involve a big factorization, and of the total of those only 4% are usable. That's really a shame. The number of candidates above 74 bits in size seems suspiciously large, but at least that doesn't cause extra factorizations.

At present the MPQS code does *not* test for perfect squares or cubes, and it really should. These are extremely rare, though. And with a factor base this small the cycle explosion definitely happens, and is a beautiful thing to behold.

jasonp

[QUOTE=jasonp]
There have been more developments on the 3-large-prime front. I tried drastically reducing the size of the factor base, and sieving for my test C100 finished in just 42 hours (the first 3LP run took over 90 hours). Version 0.88 needs 20 hours on the same machine, so there's a chance that triple large primes may be faster after all, for the input sizes people care about. I'm running a test C105 with triple large primes now; if it can finish in under 90 hours then it will be worthwhile to do another major release.
[/QUOTE]
It finished in 83 hours. Reducing the factor base size even further took longer, finishing in 87 hours. The cycle behavior with triple large primes is just crazy; once it 'goes nonlinear' all sorts of weird things start happening. Here's the tally from the 83-hour run, listing the number of relations that survived the pruning phase, the number of pruning passes, and the number of cycles. The numbers cover the last 10 hours of the run :

[code]
9808 relations 41 passes 1698 full 1776276 partial 1982 cycles
10012 relations 46 passes 1704 full 1781429 partial 2006 cycles
10254 relations 46 passes 1709 full 1787008 partial 2030 cycles
10783 relations 58 passes 1714 full 1794088 partial 2079 cycles
11121 relations 60 passes 1719 full 1797985 partial 2103 cycles
11284 relations 62 passes 1724 full 1800426 partial 2117 cycles
12048 relations 67 passes 1729 full 1807851 partial 2161 cycles
12224 relations 69 passes 1734 full 1809934 partial 2173 cycles
12919 relations 77 passes 1739 full 1814536 partial 2208 cycles
13353 relations 83 passes 1744 full 1817734 partial 2238 cycles
14067 relations 132 passes 1749 full 1826437 partial 2295 cycles <--
127793 relations 141 passes 1754 full 1831177 partial 1413 cycles <--
153071 relations 69 passes 1759 full 1836855 partial 1849 cycles <-- BOOM!
171671 relations 44 passes 1765 full 1843888 partial 2453 cycles <--
192400 relations 43 passes 1770 full 1854264 partial 3522 cycles
201149 relations 44 passes 1775 full 1859878 partial 4086 cycles
212057 relations 41 passes 1781 full 1867486 partial 4898 cycles
219558 relations 34 passes 1786 full 1872493 partial 5480 cycles
231806 relations 30 passes 1791 full 1881205 partial 6514 cycles
238561 relations 30 passes 1796 full 1885801 partial 7125 cycles
245094 relations 28 passes 1801 full 1891379 partial 7820 cycles
248192 relations 25 passes 1806 full 1893897 partial 8141 cycles
254438 relations 25 passes 1811 full 1898803 partial 8759 cycles
259386 relations 25 passes 1818 full 1903084 partial 9345 cycles
268620 relations 30 passes 1823 full 1910804 partial 10472 cycles
274376 relations 29 passes 1828 full 1916334 partial 11234 cycles
278198 relations 25 passes 1833 full 1919405 partial 11701 cycles
286604 relations 32 passes 1838 full 1926869 partial 12790 cycles
294366 relations 23 passes 1843 full 1934655 partial 13883 cycles
301472 relations 23 passes 1848 full 1941253 partial 14935 cycles
310914 relations 21 passes 1853 full 1950039 partial 16340 cycles
315536 relations 21 passes 1858 full 1954756 partial 17058 cycles
320476 relations 23 passes 1864 full 1959293 partial 17812 cycles
327039 relations 23 passes 1869 full 1965969 partial 18875 cycles
332935 relations 23 passes 1874 full 1971536 partial 19829 cycles
337719 relations 23 passes 1879 full 1976396 partial 20644 cycles
342389 relations 23 passes 1884 full 1981306 partial 21456 cycles
347094 relations 23 passes 1890 full 1985877 partial 22245 cycles
353518 relations 23 passes 1895 full 1991915 partial 23324 cycles
360701 relations 23 passes 1900 full 1999061 partial 24580 cycles
367259 relations 18 passes 1905 full 2006128 partial 25846 cycles
376659 relations 18 passes 1910 full 2015640 partial 27557 cycles
382586 relations 18 passes 1915 full 2021675 partial 28714 cycles
[/code]

Notice that while the number of relations that survive pruning goes through the roof when the explosion happens, the number of calculated cycles (i.e. surviving relations minus unique primes) starts off by *decreasing*. It's almost as if the explosion starts with a few massive cycles, then smaller cycles start appearing at a very high rate.

Despite what I said earlier, this really is not fast enough to justify the implementation effort required to finish the 3LP version.

jasonp

Jason,

I recently received an msieve log file that factored a number into a prime and a composite. The user had to re-sieve to factor the composite. I had expected additional dependencies from the matrix stage to be used against the composite. Is that not the way it works, or was this just a case of bad luck in only finding one factor? The tail of the log file is

Wed Mar 02 04:51:58 2005 largest cycle: 24 relations
Wed Mar 02 04:51:58 2005 72974 x 73038 system, weight 5546734 (avg 75.94/col)
Wed Mar 02 04:51:59 2005 reduce to 72449 x 72513 in 3 passes
Wed Mar 02 04:57:10 2005 lanczos halted after 1147 iterations
Wed Mar 02 04:57:10 2005 recovered 64 nontrivial dependencies
Wed Mar 02 04:58:34 2005 prp34 factor: 867...
Wed Mar 02 04:58:34 2005 c69 factor: 456...

William

[QUOTE=wblipp]
I recently received an msieve log file that factored a number into a prime and a composite. The user had to re-sieve to factor the composite. I had expected additional dependencies from the matrix stage to be used against the composite. Is that not the way it works, or was this just a case of bad luck in only finding one factor?
[/QUOTE]
It's just bad luck. msieve uses all of the dependencies to generate 64
(x,y) pairs, then tries gcd(x+-y,n) for all 64 pairs looking for a factor of n.
The idea at the time was that if n has 3 or more factors, then some gcd's
will find one factor and some will find the other. Most of the time you'll
find all of the factors, but sometimes you don't.

jasonp

[QUOTE=jasonp]It's just bad luck. msieve uses all of the dependencies to generate 64
(x,y) pairs, then tries gcd(x+-y,n) for all 64 pairs looking for a factor of n.
The idea at the time was that if n has 3 or more factors, then some gcd's
will find one factor and some will find the other. Most of the time you'll
find all of the factors, but sometimes you don't.

jasonp[/QUOTE]

That's what I had expected it to do. Failing to split the composite 64 times was worse luck than I was expecting, though. I guess these aren't really independent 50-50 odds.

I guess that if the bounds were set very large for small factors I wouldn't be surprised to always find the whole value in the gcd; I guess we are trending towards that limit here.

[QUOTE=wblipp]That's what I had expected it to do. Failing to split the composite 64 times was worse luck than I was expecting, though. I guess these aren't really independent 50-50 odds.

I guess that if the bounds were set very large for small factors I wouldn't be surprised to always find the whole value in the gcd; I guess we are trending towards that limit here.[/QUOTE]
I can't explain it either; it certainly has happened several times in random factorizations that I've performed. Briggs' paper on NFS shows (by enumerating all the possibilities) that if n is the product of just two primes then gcd(x+-y,n) finds a factor of n 2/3 of the time. It's a little hard to believe that you have overwhelming odds of finding one factor but only fair odds of finding more than one.

jasonp

msieve algorithm published!
 

Apparently the Dec 2004 volume of ASIACRYPT contains a paper titled 'Sieving Using Bucket Sort'. I haven't read the paper itself, but there is a PDF with slides available online; this describes exactly the algorithm that msieve uses!

The code that would become msieve was using bucket sort by mid-October 2004. I wonder if the code led to the paper, or if the authors happened to get the same idea at the same time...

jasonp

Is msieve opensource? You could probably contact the paper's authors. It is certainly possible that other people had the same idea that you did. Also, usually there is a gap of 3-9 months between a paper being submitted and being published in conference proceedings. So it is likely they had the idea even before you did.

[QUOTE=garo]Is msieve opensource? You could probably contact the paper's authors. It is certainly possible that other people had the same idea that you did. Also, usually there is a gap of 3-9 months between a paper being submitted and being published in conference proceedings. So it is likely they had the idea even before you did.[/QUOTE]
Msieve is essentially public domain.

Hmm, I didn't see that they reported some factorizations that took several months on many machines. So they probably did think of the idea first, and I got the same idea shortly afterwards.

Oh well.
jasonp