 mersenneforum.org Counting cycles with 3 large primes (for QS)
 Register FAQ Search Today's Posts Mark Forums Read 2021-08-02, 10:55 #1 Till   "Tilman Neumann" Jan 2016 Germany 1E216 Posts Counting cycles with 3 large primes (for QS) Hi together, I've been trying for a while to implement the cycle counting algorithm with three large primes from  https://www.researchgate.net/publica...e_large_primes with the help of  https://www.ams.org/journals/mcom/19...-1250773-9.pdf.  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  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. Last fiddled with by Till on 2021-08-02 at 10:57 Reason: other refs   2021-08-02, 14:17 #2 bsquared   "Ben" Feb 2007 2·11·163 Posts 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.   2021-08-03, 13:49   #3
Till

"Tilman Neumann"
Jan 2016
Germany

2·241 Posts Quote:
 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 , 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.

Last fiddled with by Till on 2021-08-03 at 13:49 Reason: typo  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Software 1 2020-11-03 04:45 jasonp Msieve 24 2010-06-01 19:14 retina Puzzles 19 2008-03-15 06:14 fivemack Factoring 18 2007-05-10 12:14 Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 04:19.

Tue Jan 25 04:19:30 UTC 2022 up 185 days, 22:48, 0 users, load averages: 1.20, 1.52, 1.48