In index calculus, the main problem is to represent powers of in a predefined prime-number basis. We are interested in unravel
from
.
Normal approach
First, we find some offset such that the factorization is
-smooth.
Using the prime-number basis , generate a corresponding vector
Then, we generate powers and check if they have the same property. The results are put into a matrix after which one performs Gaussian eliminiation over
.
. Then compute
to find
.
Different approach
Almost like in the normal approach, we find some offset such that the factorization of at least fraction of
greater than
is
-smooth.
Again, Using the prime-number basis , generate a corresponding vector
The vector is chosen such that corresponds to the product of primes not represented in the chosen basis. In other words,
for the vector above, or equivalently,
.
Again, we generate powers and check if they have the same property as above and solved as the normal approach.
Find . Then compute
to find
. There is a catch here. It will be correct if and only if
It remains to see if this actually improves over the normal approach.