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
- $g$ is a generator and is a positive integer,
- $p$ is an unknown prime, and is of the form $p=2q+1$ where $q$ is prime
- $x_{priv}$ is the unknown private key,
- $x_{pub}$ is the known public key,
- $g \pmod{p}$ is a primitive root,
- $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.