# DLP - Which algorithms for large numbers are most efficient (in terms of time) in deriving most likely used private keys via Supercomputers?

Solving for $x$ is known as the discrete log problem.

$$g^{x} \pmod{p} = h$$

Now presume adversary Eve has the public key, $x_{pub}$ for the below encryption scheme;

$$g^{x_{priv}} \pmod{p} = h$$

Where

1. $g$ is a generator and is a positive integer,
2. $p$ is an unknown prime, and is of the form $p=2q+1$ where $q$ is prime
3. $x_{priv}$ is the unknown private key,
4. $x_{pub}$ is the known public key,
5. $g \pmod{p}$ is a primitive root,
6. $g, p, x_{priv}$ and $x_{pub}$ assumed to be large.

The aim is to obtain $x_{priv}$.

I am aware of several methods of solving it such as Pollard's rho, index calculus, polig-helman, brute-force etc.

Question: Which algorithms for large numbers are most efficient (in terms of time) in deriving most likely used private keys on Supercomputers - ie each key with a probability.

I'm assuming a supercomputer has at least 64 GB of Memory, and access to multiple CPUs / GPUs.

References & links are required where possible.

This is not a homework question. I am doing this as interest. This is one of multiple questions that was originally on InfoSec SE.

• Do you mean you have access to a super computer for the attack, or you want the attack to work against a super computer? Additionally, by "deriving most likely used private keys", do you mean a function/algorithm $f$ such that $f(x_{\text{pub}}) = x_{\text{priv}}$ as efficiently as possible? – Mark Jan 11 '18 at 20:28
• I don't have access to a supercomputer. This would be run on a supercomputer to decode for $x_{priv}$. I do not know what the most likely private keys would be, but can assume they can be generated once one pair of ($x_{priv},x_{pub}$) is found due to number theory – unseen_rider Jan 11 '18 at 20:44