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.

Tests with sage.

### Like this:

Like Loading...