Computer Security and Cryptography

14.3 ADELMAN'S SUBEXPONENTIAL ALGORITHM FOR THE DISCRETE LOGARITHM PROBLEM [ADELMAN, 1979]

A number x is smooth relative to a bound N if the prime factorization of involves only prime numbers satisfying p_i ≤ N.

Proposition 14.2 (Adelman's Algorithm for the Discrete Logarithm Problem):

Given:    p a prime, q a primitive root of p, and x = q^k (modulo p),              A bound N(p) and primes p₁ < p₂ < ··· < p_m ≤ N(p);

Find:    k.

S1.    Find an integer R by random sampling such that B is smooth relative to N(p)

S2.    Find integers R_i for 1 ≤ i ≤ m by random sampling such that A_i is smooth relative to N(P).

    and the vectors

    span the m-dimensional vector space over .

S3.    Use Gaussian elimination to write

    Then

    Raising both sides of the equation B = x^R (modulo ...