Description
Roughly speaking, the discrete log problem asks us to find an x such that, where g, h, and the modulus n are given.
The algorithm (described in detail below) applies to the group where q is prime. It requires a factor base as input. This factor base is usually chosen to be the number −1 and the first r primes starting with 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 three stages. The first two stages depend only on the generator g and prime modulus q, and find the discrete logarithms of a factor base of r small primes. The third stage finds the discrete log of the desired number h in terms of the discrete logs of the factor base.
The first stage consists of searching for a set of r linearly independent relations between the factor base and power of the generator g. Each relation contributes one equation to a system of linear equations in r unknowns, namely the discrete logarithms of the r primes in the factor base. This stage is embarrassingly parallel and easy to divide among many computers.
The second stage solves the system of linear equations to compute the discrete logs of the factor base. Although a minor computation compared to the other stages, a system of hundreds of thousands or millions of equations is a significant computation requiring large amounts of memory, and it is not embarrassingly parallel, so a supercomputer is typically used.
The third stage searches for a power s of the generator g which, when multiplied by the argument h, may be factored in terms of the factor base gsh = (−1)f0 2f1 3f2···prfr.
Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm x = f0logg(−1) + f1logg2 + f2logg3 + ··· + frloggpr − s.
The first and third stages are both embarrassingly parallel, and in fact the third stage does not depend on the results of the first two stages, so it may be done in parallel with them.
The choice of the factor base size r is critical, and the details are too intricate to explain here. The larger the factor base, the easier it is to find relations in stage 1, and the easier it is to complete stage 3, but the more relations you need before you can proceed to stage 2, and the more difficult stage 2 is. The relative availability of computers suitable for the different types of computation required for stages 1 and 2 is also important.
Read more about this topic: Index Calculus Algorithm
Famous quotes containing the word description:
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)
“As they are not seen on their way down the streams, it is thought by fishermen that they never return, but waste away and die, clinging to rocks and stumps of trees for an indefinite period; a tragic feature in the scenery of the river bottoms worthy to be remembered with Shakespeare’s description of the sea-floor.”
—Henry David Thoreau (1817–1862)
“I fancy it must be the quantity of animal food eaten by the English which renders their character insusceptible of civilisation. I suspect it is in their kitchens and not in their churches that their reformation must be worked, and that Missionaries of that description from [France] would avail more than those who should endeavor to tame them by precepts of religion or philosophy.”
—Thomas Jefferson (1743–1826)