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.

grocid.net

scribbles from past, present and possibly future

Experiments with index calculus

Leave a Reply Cancel reply

Menu

grocid.net

scribbles from past, present and possibly future

Share this:

Like this:

Leave a Reply Cancel reply

Menu