mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2022-06-10, 06:05   #12
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

56358 Posts
Default

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
kar_bon is offline   Reply With Quote
Old 2022-06-10, 06:49   #13
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2,287 Posts
Default

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
a1call is offline   Reply With Quote
Old 2022-06-10, 07:37   #14
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

47416 Posts
Default

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\).
  1. Set \(m \leftarrow \lceil \frac{m}{2} \rceil\).
  2. 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!
kruoli is offline   Reply With Quote
Old 2022-06-10, 08:31   #15
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

43578 Posts
Default

My mistake. Please disregard.

Last fiddled with by a1call on 2022-06-10 at 08:32
a1call is offline   Reply With Quote
Old 2022-06-10, 08:43   #16
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

21648 Posts
Default

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.
kruoli is offline   Reply With Quote
Old 2022-06-10, 09:49   #17
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

659610 Posts
Default

Quote:
Originally Posted by kruoli View Post
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
retina is offline   Reply With Quote
Old 2022-06-10, 10:34   #18
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

22·3·5·19 Posts
Default

Why not?
  1. test: \(t_1 := \text{gcd}(n, c_1 \cdot c_2)\), f \(1 < t_ 1 < n\), \(t_1\) is the result, exit
  2. test:
    1. if \(t_1=1\), \(t_2 := \text{gcd}(n, c_3)\), if \(t_2=1\), \(c_4\) is the result, \(c_3\) otherwise
    2. 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.
kruoli is offline   Reply With Quote
Old 2022-06-10, 11:38   #19
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×17×97 Posts
Default

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
retina is offline   Reply With Quote
Old 2022-06-10, 11:54   #20
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

22×3×5×19 Posts
Default

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:
  1. 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
  2. test:
    1. if \(t_1 = 1\), \(t_2 := \text{gcd}(n, c_4)\), if \(t_2 = 1\), error, otherwise \(c_4\) is the result
    2. 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
kruoli is offline   Reply With Quote
Old 2022-06-10, 12:04   #21
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·17·97 Posts
Default

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
retina is offline   Reply With Quote
Old 2022-06-10, 13:40   #22
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,483 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PRP double checks are also included in the first time list retina PrimeNet 6 2017-10-29 01:31
Manual testing on CPU list Fred PrimeNet 3 2016-02-12 02:49
Time needed to factor a 150 digit number ladderbook Factoring 14 2008-11-27 13:02
Is it time for a 100M digit option? petrw1 PrimeNet 60 2008-09-30 22:43
50 Digit Testing 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

Powered by vBulletin® Version 3.8.11
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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”