Testing a list of 65-digit primes instead of one at a time

[kar_bon]

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

[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.

[kruoli]

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!

[a1call]

My mistake. Please disregard.

[kruoli]

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.

[retina]

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.

[kruoli]

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.

[retina]

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.

[kruoli]

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

[retina]

You can just do:

a=gcd(n,c1*c2)
b=gcd(n,c3*c4)

And then figure out the divisors from a & b later.

[xilman]

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.