20210802, 10:55  #1 
"Tilman Neumann"
Jan 2016
Germany
1E2_{16} 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 [1] https://www.researchgate.net/publica...e_large_primes with the help of [2] https://www.ams.org/journals/mcom/19...12507739.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. Last fiddled with by Till on 20210802 at 10:57 Reason: other refs 
20210802, 14:17  #2 
"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 yafu3lp alternates between sieving and trying to build a matrix. 
20210803, 13:49  #3  
"Tilman Neumann"
Jan 2016
Germany
2·241 Posts 
Quote:
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 cyclefinding algorithm was exactly the same as reported by the cyclecounting 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 20210803 at 13:49 Reason: typo 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Counting primes in residue classes  CRGreathouse  Software  1  20201103 04:45 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
Counting primes in Scrabble racks  retina  Puzzles  19  20080315 06:14 
Why only three large primes  fivemack  Factoring  18  20070510 12:14 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 