Introduction and Motivation
I'm mainly active on Cryptography.SE and as such have already stumbled across the question: "How the hell am I supposed tools like cado-nfs to do stuff!?". They are super-complicated tools for a super-complicated task: Factoring large integers and computing large-scale discrete logarithms.
Now I'm standing here (in a metaphoric sense) and I am asking you:
Please give us poor cryptographers a usable tool. :( This question in particular is about the discrete logarithm problem which was broken by Logjam, is frequently used in the world of online security and you're supposed to solve it (as far as current technology goes)!
Your input will be three (potentially) large numbers: A generator, a prime and an argument. The integer encoding should be hex or decimal big-endian. Additionally you may require arbitrary generator and prime dependent state (a bunch of pre-calculations and stuff). The generators, primes and arguments for the score evaluation will not be public. But there will be several arguments for one set of generators and primes so caching does make sense here.
The output is supposed to be one (potentially large) integer, the discrete logarithm of the argument to the base of the generator in the field defined by the prime. Additionally you may output intermediate state that will speed-up future calculations.
What to do?
Using any library, tool and language you like (no online-services), hit the lowest time of execution for calculating the (correct) discrete logarithm. The parameters will be:
- There will be three pairs of random (safe) prime and an appropriate (small) generator
- Each pair will receive three distinct (random) arguments, for the latter two, intermediate state will speed things up significantly
- The tests will be run on an AWS EC2 c4.large instance
- The tests will use 332-bit (100 decimal digit) primes and arguments
This is fastest-code so the fastest code wins!
Submissions are evaluated earliest three days after lack of activity (these evaluations cost money!) and clearly inefficient submissions will not be evaluated at all.
OS: The submittant has the choice between the default Amazon-provided OSes which are Windows Server (2003 R2 - 2012 R2 Base), Red Hat Enterprise Linux 7.2, SUSE Linux Enterprise Server 12 SP1, Ubuntu Server 14.04 LTS, Debian 8 Jessie (community AMI), CentOS (6 or 7; community AMI) additionally the submittant can link to or provide instructions on using / creating a custom Amazon Machine Image (AMI) for testing
Installation instructions or links to those need to be provisioned.