# How large a product out of 3 close-by factors need to be to avoid factorization?

For encryption a prime $$P = 2 \cdot Q \cdot R \cdot S +1$$ was used.
An adversary want to solve the discrete log problem $$m \equiv g^i \bmod P$$. For this he want to use the Pholig-Hellmann algorithm.
To use this he need the factorization of $$P-1 = 2 \cdot Q \cdot R \cdot S$$.
Factor $$2$$ is trivial so he only need to know the primes $$Q, R, S$$

(edit) He should also not be able to project a value $$m$$ into a subgroup, like:

$$m^{2\cdot R \cdot S} \equiv v \bmod P$$ $$v$$ is $$1$$ or has order $$Q$$ (edit end)

He does know prime $$P$$ and the internal structure of $$P-1$$ has $$4$$ factors and one of those is $$2$$. He also knows the other three factors are quite similar to eachother: $$\frac{P-1}{2} \approx Q^3 \approx R^3 \approx S^3$$ with $$\max(Q,R,S) \le 1.25\cdot\min(Q,R,S)$$ or $$\forall a,b,c \in \{Q,R,S\}: 0.8\cdot a \le b \le 1.25 \cdot c$$

edit2: That means the potential factors are in limited range between $$\sqrt{(P/(1.25^2))}$$ and $$\sqrt{P}$$

For values consisting out of two factors the current record is afaik about 240 decimal digits or 795-bit (records-wiki)

Question: How large need to be a value out of three prime factors as described above to be as secure as the current record for two factors?

($$Q,R,S,P$$ can be set to special kind of primes, like safe primes, as long those conditions from above hold )

• Security of discrete log is not related to factoring. You can directly assume that the adversary has the factorization. – kelalaka Jan 21 at 11:24
• @kelalaka fastest way to solve such a discrete log is afaik Pholig-Hellmann algorithm which needs to know the factorization of $P-1$. If he dont know the factorization it will take way longer to solve it. Or did got something wrong? If a generator with e.g. order $Q$ is given. Would it be faster to find his order than factorizing $P-1$? – J. Doe Jan 21 at 11:38
• Do you want to increase the prime sizes since you fear of factoring? Then not able to solve the dLog since that already infeasible! – kelalaka Jan 21 at 12:10
• Note that the runtime of Pohlig-Hellman is roughly $O(\sqrt Q+\sqrt R+\sqrt S)$ in your case. As the product still needs to be at least 1000 bit long, each factor needs to be at least 333 bits long and so the runtime of Pohlig-Hellman would be roughly $2^{160}$ which is infeasible. – SEJPM Jan 21 at 12:26
• @kelalaka you are correct. The main reason is not be able to project one value to another subgroup. (did some edit) – J. Doe Jan 21 at 12:45