mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-08-02, 10:55   #1
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

25×3×5 Posts
Default 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...-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.

Last fiddled with by Till on 2021-08-02 at 10:57 Reason: other refs
Till is offline   Reply With Quote
Old 2021-08-02, 14:17   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·1,193 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2021-08-03, 13:49   #3
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

7408 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.

Last fiddled with by Till on 2021-08-03 at 13:49 Reason: typo
Till is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Counting primes in residue classes CRGreathouse Software 1 2020-11-03 04:45
48-bit large primes! jasonp Msieve 24 2010-06-01 19:14
Counting primes in Scrabble racks retina Puzzles 19 2008-03-15 06:14
Why only three large primes fivemack Factoring 18 2007-05-10 12:14
What is the use of these large primes Prime Monster Lounge 34 2004-06-10 18:12

All times are UTC. The time now is 14:23.


Wed Dec 1 14:23:41 UTC 2021 up 131 days, 8:52, 2 users, load averages: 1.39, 1.33, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.