Counting cycles with 3 large primes (for QS)

[Till]

Hi together,
I've been trying for a while to implement the cycle counting algorithm with three large primes from
[1] https://www.researchgate.net/publica...e_large_primes
with the help of
[2] https://www.ams.org/journals/mcom/19...-1250773-9.pdf.

[1] says that the formula is (approximately) #cycles = C + A - P - 2R, where
* C is the number of disconnected components
* A is the number of arcs between pairs of primes
* P is the number of primes (vertices), and
* R is the number of partial relations fed to the algorithm.

I have another solution that uses a Gaussian solver to find smooths from partials, implemented the cycle finding algorithm from [1] and both give the same results. My cycle counting implementation for two large primes works correctly, too. But at counting cycles with three large primes I am stuck.

Probably I do not exactly understand how to compute the arcs. Using the C + A - P - 2R formula, my numbers only get close to corrected ones (as computed by the Gaussian solver and cycle finder) if I take A=3R. But this is equal then to the formula for 2 large primes, #cycles = R + C - P.

So for a little help, could someone tell me how the cycle counting with 3LP would work for two small examples?

Example 1:
Let a, b, c, d, e, f be distinct primes. We get relations in the following order:
(a, b)
(c, d)
(a, b, c)
(e, f)
(c, e, f)
After the first four relations the cycle count should still be zero.
With the fifth relation we get a cycle (a, b), (a, b, c), (c, e, f), (e, f), but
I think there is only one disconnected component and thus R + C - P = 5 + 1 - 6 = 0.

Example 2:
Let a, b, c, d, e, f be distinct primes. We get relations in the following order:
(a, b)
(c, d)
(e, f)
(a, c, e)
The cycle count should always be zero, but again there should only be one component and hence R + C - P = 4 + 1 - 6 = -1.

If somebody could tell me how to get those counts right (probably involving counting arcs) that would be great.


P.S. Other threads/papers that explain the algorithm would be nice, too.

[bsquared]

I found some useful info here as well: https://www.researchgate.net/publica...ive_Experiment

I may be wrong, but I found that I couldn't compute an exact count of cycles without also building them. This is why yafu-3lp alternates between sieving and trying to build a matrix.

[Till]

Originally Posted by bsquared

I found some useful info here as well: https://www.researchgate.net/publica...ive_Experiment

I may be wrong, but I found that I couldn't compute an exact count of cycles without also building them. This is why yafu-3lp alternates between sieving and trying to build a matrix.

Thanks,
that's a good new option for me. If the number of cycles reported by our counting algorithm is an upper bound of the true cycle count, then we only need to run the matrix solver when the counting algorithm signals a smooth candidate.

But it is a pity that we cannot reproduce the algorithm from [1], because *cite from page 7*
"in every factorization we performed the number of cycles produced by the cycle-finding algorithm was exactly the same as reported by the cycle-counting algorithm".
That's much better than my counting algorithm and would render any matrix solver calls in this stage obsolete, no matter if the formula is exact or minimally incorrect.