cudadl/README

cudadl-0.8
23 Jan 2012
Ryan Henry and Ian Goldberg
{rhenry,iang}@cs.uwaterloo.ca
http://crysp.uwaterloo.ca/software/

This package contains the source code to our CUDA implementation of
van Oorschot and Wiener's parallel version of the Pollard rho discrete
log algorithm.  It is intended for use on 1536-bit moduli that are
RSA numbers with smooth totient; that is, the modulus N=pq, where p and q
are 768-bit primes, and the prime factors of p-1 and q-1 are all
distinct and less then B, for a parameter B.  [The value 1536 is
hardcoded as "WORDS = 24" (24*32*2 = 1536) in the Makefile; it is easy
to change this value and recompile if desired.]  Note that this means
the totient of N = \phi(N) = (p-1)(q-1) has all prime factors less than
B; that is, \phi(n) is "B-smooth".

Usage:

1. Build the software.  You'll need:

    NTL
    GMP
    NVIDIA CUDA Toolkit 3.1
    2 M2050 (or other compute capability level 2.0) CUDA cards
      [If you have more or just 1, you'll need to modify dlrho.cc,
       unfortunately.]

    Hopefully just typing "make" should work.  It will build gen_N and
    dlrho.

2. Create the modulus N as, for example, a 1536-bit RSA number whose
   totient is 2^50-smooth:

   ./gen_N 1536 50 > N

3. Generate a DL problem mod N and solve it:

    ./dlrho < N

This software is described in "Solving Discrete Logarithms in
Smooth-Order Groups with CUDA", CACR technical report 2012-02,
http://www.cacr.math.uwaterloo.ca/techreports/2012/cacr2012-02.pdf

This program is covered under version 3 of the GNU General Public
Licence; see the file COPYING for more information.