Experiments with index calculus

In index calculus, the main problem is to represent powers of g in a predefined prime-number basis. We are interested in unravel x from h = g^x\bmod p.

Normal approach

First, we find some offset hg^j = g^{x+j}\bmod p such that the factorization is B-smooth.

Using the prime-number basis (-1)^{e_1}2^{e_2}\cdots, generate a corresponding vector

\mathbf y = \begin{pmatrix}1 & 0 & 3 & 0 & \cdots & 1\end{pmatrix}

Then, we generate powers g^1, g^2, ... and check if they have the same property. The results are put into a matrix after which one performs Gaussian eliminiation over \mathbb{Z}_{p-1}.

A | \mathbf v^T = \left( \begin{array}{cccccc|cc}0 & 3 & 2 & 2 & \cdots & 1 & \mathbf{13} \\ 1 & 0 & 2 & 1 & \cdots & 0 & \mathbf{112} \\ 0 & 5 & 2 & 0 & \cdots & 0 & \mathbf{127} \\\vdots & \vdots & \vdots & \vdots & & \vdots & \vdots \\ 1 & 1 & 0 & 0 & \cdots & 0 & \mathbf{67114}\end{array}\right)

\mathbf xA = \mathbf y. Then compute \mathbf x \cdot \mathbf v to find x+j.

Different approach

Almost like in the normal approach, we find some offset hg^j = g^{x+j} \bmod p such that the factorization of at least fraction of hg^j \bmod p greater than \sqrt{p} is B-smooth.

Again, Using the prime-number basis (-1)^{e_1}2^{e_2}\cdots, generate a corresponding vector

\mathbf y | \Delta = \left(\begin{array}{cccccc|c}0 & 2 & 5 & 1 & \cdots & 0 & \Delta\end{array} \right)

The vector is chosen such that \Delta corresponds to the product of primes not represented in the chosen basis. In other words, (-1)^0 \cdot 2^2 \cdot 3^5 \cdot 7^1 \cdots > \sqrt{p} for the vector above, or equivalently, \Delta < \sqrt p.

Again, we generate powers g^1, g^2, ... and check if they have the same property as above and solved as the normal approach.

A | \mathbf v^T | \mathbf d^T = \left( \begin{array}{cccccc|c|c} 1 & 0 & 3 & 0 & \cdots & 0 & \mathbf{5} & \delta_1 \\ 0 & 3 & 2 & 2 & \cdots & 1 & \mathbf{13}& \delta_2 \\ 0 & 1 & 2 & 1 & \cdots & 0 & \mathbf{65}& \delta_3 \\ \vdots & \vdots & \vdots & \vdots & & \vdots & \vdots\\ 0 & 2 & 0 & 0 & \cdots & 0 & \mathbf{13121}& \delta_B \end{array}\right)

Find \mathbf xA = \mathbf y. Then compute \mathbf x \cdot \mathbf v to find x+j. There is a catch here. It will be correct if and only if

\prod \delta_i ^{x_i} \bmod p = \Delta.

It remains to see if this actually improves over the normal approach.

Tests with sage.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s