Index-Calculus Yöntemi

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in $(\mathbb {Z} /q\mathbb {Z} )^{*}$ where ${\displaystyle q}$ is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.

x=log_\alpha(mod~p)=?

Table of Contents

Adım 1 – Kat sayı tabanının seçilmesi:

$\mathbb{Z}_p^{*}$ ‘da bir asal sayılar altkümesi seçilir

S=\{P_1,P_2,P_3,\dots,P_i\}

Adım 2

$P_i$ ‘nin ayrık logaritmalarını hesaplıyabilmek için, S kümesindei elemanların logaritmalarını da içeren lineer denklemler takımları oluşturulur.

Adım 2.1

\alpha^k(mod~p)~hesaplanır.

Adım 2.2

$\alpha^k$ ‘yı S’dei elemanların çarpımı olacak şekilde yazılır.

\alpha^k=\prod_{i=1}^t{P_i^{c_i}},\quad c_i \ge 0

k=\sum_{i=1}^t{c_i*log_\alpha P_i}

Adım 2.3

(t+c) gibi lineer denklem takımları olur.

Adım 3

$\mathbb{Z}_p$ ‘de $log_\alpha P_i$ ‘ler $0 \le i \le t$ (t+c) denklem takımları çözülür.

Adım 4 – x’in hesaplanması

Adım 4.1

0 \le r \le (p-1)

\beta*\alpha^r(mod~p)

Adım 4.2

\beta*\alpha^r(mod~p)=(\prod_{i=1}^t{d_i~log_\alpha P_i-r})(mod~p)

Örnek:

\alpha = 6 \quad p=229 \quad \beta=12 \Rightarrow x=?

Adım~1:S=\{2,3,5,7,11\} \rightarrow 5~sayı~seçtik

Adım~2:Rastgele~K~değerleri:\{100,18,12,62,143,206\}

\begin{align*} 6^{100}(mod~229)&=180=2^2*3^2*5 \\ 6^{18}(mod~229)&=176=2^4*11 \\ 6^{12}(mod~229)&=165=3*5*11 \\ 6^{62}(mod~229)&=154=2*7*11 \\ 6^{143}(mod~229)&=198=2*3^2*11 \\ 6^{206}(mod~229)&=210=2*3*5*7 \end{align*}

\begin{align*} 100 &= 2\log_{6}{2}+ 2\log_{6}{3}+\log_{6}{5} \\ 18 &= 4\log_{6}{2}+ ~~~\log_{6}{11} \\ 12 &= ~~~\log_{6}{3}+ ~~~\log_{6}{5}+\log_{6}{11} \\ 62 &= ~~~\log_{6}{2}+ ~~~\log_{6}{7}+\log_{6}{11} \\ 143 &= ~~~\log_{6}{2}+2\log_{6}{3}+\log_{6}{11} \\ 206 &= ~~~\log_{6}{2}+ ~~~\log_{6}{3}+\log_{6}{5}+\log_{6}{7} \end{align*}

Adım~3:\\ \begin{align*} \log_62&=21 \\ \log_63&=208 \\ \log_65&=98 \\ \log_67&=107 \\ \log_611&=162 \end{align*}

Adım~4:r=77\quad13*6^{77}(mod~229)=147=3*7^2

x=\log_613=(\log_63+2\log_67-77)\\ (208+2*107-77)=117~~???