Index Calculus Algorithm Article Index for
Index 		Website Links For
Calculus 		 

Information About

Index Calculus Algorithm
  CATEGORIES ABOUT INDEX CALCULUS ALGORITHM
   
group theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




DESCRIPTION

Roughly speaking, the Discrete Log problem asks us to find an ''x'' such that g^x \equiv h \pmod{n}, where ''g'', ''h'', and the modulus ''n'' are given.

  • where ''q'' is prime. It requires a ''factor base'' as input. This ''factor base'' is usually chosen to be the number -1 and a number of consecutive primes starting from 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the ''factor base'' to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another.


The algorithm is performed in two stages. The first stage involves gathering a number of ''relations'' between the factor base and powers of the Generator ''g''. Once ''enough'' relations are gathered, we can compute the discrete log of each of the elements in the factor base. The second stage begins by multiplying ''h'' by consecutive powers of ''g'' until it can be factorised over the factor base. Once that can be done, we can work out ''x'' via a simple algebraic manipulation.


THE ALGORITHM

Input: Factor base {-1,2,3,...,''p''}, ''g'', ''h'', ''q''

Output: ''x'' such that g^x \equiv h \pmod{q}
# ''k'' = 0
# ''l'' = 0
# Increment ''k'' by 1 (i.e. if ''k'' was ''n'', now ''k'' = ''n'' + 1)
# Compute g^k
# Factorise g^k using the factor base, i.e. find k_i's such that g^k = (-1)^{k_0}2^{k_1}3^{k_2}...p^{k_r} if the factor base has r+1 elements
  • If g^k can not be factorised using the factor base, return to step 3

    • # Store ''k'' and the computed k_i's as a vector v_l = (k_0,k_1,k_2,...,k_r,k) (this is a called a relation)

# Check to see if this relation is Linearly Independent of the other relations
  • if not, discard it and go to step 3

  • if yes, keep it. ''l'' <- ''l'' + 1 (''l'' keeps track of the number of relations we have)

  • --- if ''l'' < ''r'', go to step 3

  • --- if ''l'' ≥ ''r'' (r+1 is the number of elements in the factor base), go to next step

    • # Form a matrix whose rows are the v_i's

# Obtain the Reduced Echelon Form of the matrix and declare the first element in the last column is the discrete log of -1 and the second element is the discrete log of 2 and so on
  • if this cannot be done go back to step 3

    • # ''s'' = 0

# ''s'' <- ''s'' + 1
# Compute hg^s
# Try to factorise hg^s over the factor base
  • if this can not be done go back to step 11

  • if this can be done, and hg^s = (-1)^{s_0}2^{s_1}3^{s_1}...p^{s_r}, then declare x = s_0log_g(-1) + s_1log_g2 + ... + s_rlog_gp - s



EXTERNAL LINKS