7
\$\begingroup\$

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)!

Specification

Input

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.

Output

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

Who wins?

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.

(Potentially) Helpful resources:

Improve this question
\$\endgroup\$
4
  • 2
    \$\begingroup\$ This might be an overkill question. \$\endgroup\$
    – ave
    Commented Jul 22, 2016 at 21:33
  • \$\begingroup\$ I'm not sure if I'm understanding this correctly; the question is supposed to be about writing a script to install and invoke some factoring tools? \$\endgroup\$
    – feersum
    Commented Jul 23, 2016 at 5:26
  • \$\begingroup\$ @feersum, it's not about factoring (but rather a different, similarly used mathematical concept called discrete logarithm) and it doesn't require an installation script. Just some program that computes a discrete logarithm (quickly). Using the pre-built and engineered tools for this task would certainly help reduce code sizes and run-times. \$\endgroup\$
    – SEJPM
    Commented Jul 23, 2016 at 12:23
  • \$\begingroup\$ @ardaozkal, I was fearing the same. But in the end the resulting program should be "rather short", even though the required mathematical / technical skill may actually be overkill :/ \$\endgroup\$
    – SEJPM
    Commented Jul 23, 2016 at 12:26

1 Answer 1

Reset to default
1
\$\begingroup\$

Cado-nfs is the right tool to use.

It provides abstract enough way of handling any case, but relies on input specific optimizations that cannot be done by the program anyway.

There is no general (applicable to anything with same efficiency) solution (even theoretical one) for NFS that can be implemented in program at the moment.

Judging by the work done in CADO-nfs, simply coming up with a good enough algorithm for just 100 digit number would take several months of research before any programming can be done.

You should ask around on CADO-nfs forums, there were at least couple of tests mentioning 103-104-digit algorithms, that might be more useful.

If nfs is not a strict requirement, you could mention it in question. Sadly, I cannot comment yet; and no, I am far from specialist in any of the areas.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ In fact, cado-nfs already has kind of a one-shot tool for calculating discrete logarithms. It's just that it requires MAGMA to be installed (boo) and that some pre- and post- processing on the in- and outputs is needed... And the parameters are deliberately chosen such that the (G)NFS is the only viable tool for the job. \$\endgroup\$
    – SEJPM
    Commented Aug 4, 2016 at 13:51
  • 1
    \$\begingroup\$ Well, do you strictly require NFS solution? If so, you would need to map out mathematical algorithm for the procedure as a part of the question so that other may translate it into some programming language. I doubt you can expect anyone to go through whole theory, explanations and this particular implementation (CADO) before a single line of code can be written. Or you are looking for the fastest simple (intuitive) solution? \$\endgroup\$
    – Michael M
    Commented Aug 5, 2016 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.