test.tex

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.

$$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. The results are put into a matrix after which one performs Gaussian eliminiation.

$$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)
$$

$\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.
$$