 mersenneforum.org Testing a list of 65-digit primes instead of one at a time
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2022-06-10, 06:05 #12 kar_bon   Mar 2006 Germany 56358 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 2,287 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 47416 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 43578 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 21648 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

659610 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 22·3·5·19 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 22×17×97 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 22×3×5×19 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 22·17·97 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

11,483 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.   Thread Tools Show Printable Version Email this Page 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 08:56.

Sun Sep 25 08:56:33 UTC 2022 up 38 days, 6:25, 0 users, load averages: 1.43, 1.42, 1.27

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔