mersenneforum.org Testing a list of 65-digit primes instead of one at a time
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-10, 06:05 #12 kar_bon     Mar 2006 Germany 303010 Posts Easiest way if you got one/both prime factors of the C130 for sure in the list: - goto FactorDB - put the 130 digit number in the field and click "factorize" - put the list of the 100 possible primefactors in the input field for "Report factors" - click "Report" - the C130 now is factored
 2022-06-10, 06:49 #13 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 44768 Posts It would be an interesting puzzle to figure out the maximum number of gcd tests required if both primes are in the list of 100. I get maximum of 14 tests if Murphy’s law applies for all the tests. Last fiddled with by a1call on 2022-06-10 at 06:56
 2022-06-10, 07:37 #14 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 101101001012 Posts What I would do: Let $$c_1, \dots, c_{100}$$ be the candidates and $$n$$ the number to factor. Set $$i=1$$ and $$m=100$$.Set $$m \leftarrow \lceil \frac{m}{2} \rceil$$. Let $$f := \text{gcd}(n, \prod_{j=i}^{j \leq{} i + m - 1}{c_j})$$. If $$1 < f < n$$, $$f$$ is a factor, exit. Otherwise, if $$f=1$$, set $$i \leftarrow{} i + m$$. If $$m>1$$, go to step 1, error otherwise. This needs 7 GCDs at most!
 2022-06-10, 08:31 #15 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×7×132 Posts My mistake. Please disregard. Last fiddled with by a1call on 2022-06-10 at 08:32
 2022-06-10, 08:43 #16 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 5×172 Posts Maybe my solution is not optimal, either. I think the optimality can be proven, i.e. the worst case is always $$\lceil\log_2(\#\text{candidates})\rceil$$. My algorithm is not perfect; it tests numbers that have been ruled out because of overlapping ranges (halving odd numbers), this could be fixed, but would not improve the score.
2022-06-10, 09:49   #17
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×3,359 Posts

Quote:
 Originally Posted by kruoli I think the optimality can be proven, i.e. the worst case is always $$\lceil\log_2(\#\text{candidates})\rceil$$.
For 4 candidates and up to two divisors, you can't be guaranteed to find them with 2 tests.

Last fiddled with by retina on 2022-06-10 at 09:58

 2022-06-10, 10:34 #18 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 5×172 Posts Why not?test: $$t_1 := \text{gcd}(n, c_1 \cdot c_2)$$, f $$1 < t_ 1 < n$$, $$t_1$$ is the result, exit test:if $$t_1=1$$, $$t_2 := \text{gcd}(n, c_3)$$, if $$t_2=1$$, $$c_4$$ is the result, $$c_3$$ otherwise if $$t_1=n$$, $$t_ 2 := \text{gcd}(n, c_1)$$, if $$t_2=1$$, $$c_2$$ is the result, $$c_1$$ otherwise See that you only have to execute 2a or 2b, never both. Last fiddled with by kruoli on 2022-06-10 at 10:36 Reason: Omitted superfluous words.
 2022-06-10, 11:38 #19 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 671810 Posts You are correct, you can identify 0, 1 or 2 divisors with 2 tests from 4 candidates. But not with the algorithm as shown above. Test 2b gives no further information, both c1 and c2 divide n. Last fiddled with by retina on 2022-06-10 at 11:46
 2022-06-10, 11:54 #20 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 5·172 Posts As per the OP's statement, we know that we have at least one factor within the candidates. You are correct about 2b. You likely wanted to do: test: $$t_1 := \text{gcd}(n, c_1 \cdot c_2 \cdot c_3)$$, if $$0 < t_1 < n$$, $$t_1$$ is our result, exit test: if $$t_1 = 1$$, $$t_2 := \text{gcd}(n, c_4)$$, if $$t_2 = 1$$, error, otherwise $$c_4$$ is the result if $$t_1 = n$$, $$t_2 := \text{gcd}(n, c_1)$$, if $$t_2 = 1$$, both $$c_2$$ and $$c_3$$ are valid results, otherwise $$c_1$$ is our result
 2022-06-10, 12:04 #21 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 150768 Posts You can just do: a=gcd(n,c1*c2) b=gcd(n,c3*c4) And then figure out the divisors from a & b later. Last fiddled with by retina on 2022-06-10 at 12:05
2022-06-10, 13:40   #22
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

52×7×67 Posts

Quote:
 Originally Posted by a1call It would be an interesting puzzle to figure out the maximum number of gcd tests required if both primes are in the list of 100. I get maximum of 14 tests if Murphy’s law applies for all the tests.
Arjen Lenstra et al. did something closely similar to this exercise a few years back.

They collected a very large number of RSA public moduli and found common factors within the set, thereby breaking a large number of live public keys.

I will see if I can find the paper ... here it is https://eprint.iacr.org/2012/064

https://souravsengupta.com/publications/2017_iciss.pdf indicates that the algorithm can be parallelized.

 Similar Threads Thread Thread Starter Forum Replies Last Post retina PrimeNet 6 2017-10-29 01:31 Fred PrimeNet 3 2016-02-12 02:49 ladderbook Factoring 14 2008-11-27 13:02 petrw1 PrimeNet 60 2008-09-30 22:43 wblipp ElevenSmooth 1 2003-11-15 23:53

All times are UTC. The time now is 18:00.

Tue Mar 28 18:00:51 UTC 2023 up 222 days, 15:29, 0 users, load averages: 0.54, 0.75, 0.79