Algoritmo de Polig-Hellman

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de abril de 2020; las comprobaciones requieren 2 ediciones .

El algoritmo Polyg-Hellman (también llamado algoritmo Silver-Polig-Hellman ) es un algoritmo de logaritmo discreto determinista en el anillo de residuos módulo un número primo . Una de las características del algoritmo es que para números primos de una forma especial, puede encontrar el logaritmo discreto en tiempo polinomial . [una]

Historia

Este algoritmo fue inventado por el matemático estadounidense Roland Silver , pero fue publicado por primera vez por otros dos matemáticos estadounidenses Stephen Pohlig y Martin Hellman en 1978 en el artículo " Un algoritmo mejorado para calcular logaritmos sobre GF (p) y su significado criptográfico" [2] , quien desarrolló este algoritmo independientemente de Roland Silver. [3]

Datos iniciales

Que se dé la comparación

$a^{x}\equiv b{\pmod {p)),$

(una)

y se conoce la descomposición de un número en factores primos: $p-1$

p-1=\prod\limits_{i=1}^{k}q_i^{\alpha_i}.

(2)

Es necesario encontrar un número que satisfaga la comparación (1). [cuatro] $x,\;0\leq x < p-1$

La idea del algoritmo

La esencia del algoritmo es que es suficiente encontrar módulos para todos , y luego la solución a la comparación original se puede encontrar usando el teorema chino del resto . Para encontrar cada uno de estos módulos, debe resolver la comparación: $X$ $q_i^{\alfa_i}$ $i$
$X$

(a^x)^{(p-1)/{q_i^{\alpha_i}}} \equiv b^{(p-1)/{q_i^{\alpha_i}}} \pmod{p}

. [5]

Descripción del algoritmo

Versión simplificada

La mejor manera de lidiar con este algoritmo es considerar el caso especial en el que . $p = 2 ^ n + 1$

Se nos da , y , si bien existe un elemento primitivo y necesitamos encontrar uno que lo satisfaga . $a$ $pags$ $b$ $a$ $FG(p)$ $X$ $a^x\equiv b\pmod{p}$

Se supone que , ya que es indistinguible de , porque en nuestro caso el elemento primitivo , por definición, tiene grado , por tanto: $0\leq x \leq p-2$ $x=p-1$ $x=0$ $a$ $p-1$

a^{p-1}\equiv 1\equiv a^{0}\pmod{p}

Cuando , es fácil de determinar por expansión binaria con coeficientes , por ejemplo: $p = 2 ^ n + 1$ $X$ $\{q_0, q_1,\puntos, q_{n-1}\}$

x = \sum\limits_{i = 0}^{n-1}q_i2^i=q_{0} + q_{1}2^1 + \cdots + q_{n-1}2^{n-1}

El bit menos significativo se determina elevando a una potencia y aplicando la regla $q_{0}$ $b$ $(p-1)/2 = 2^{n-1}$

b^{(p-1)/2}\pmod{p}\equiv \begin{casos}+1, & q_0 = 0\\ -1, & q_0 = 1. \end{casos}

Derivación de la regla superior

Considere la comparación obtenida anteriormente :

a^{p-1}\equiv 1\pmod{p}\Rightarrow a^{(p-1)/2}\equiv\pm 1\pmod{p}

pero por definición toma un valor distinto de , por lo que solo queda una comparación : $a$ $(p-1)/2 < p - 1$ $una$

a^{(p-1)/2}\equiv -1\pmod{p}

Eleve la comparación (1) a una potencia y sustituya la comparación obtenida anteriormente: $(p-1)/2$

b^{(p-1)/2}\equiv (a^x)^{(p-1)/2}\equiv(a^{(p-1)/2})^x\equiv(-1 )^x\pmod{p}

La igualdad es verdadera si es par, es decir, en la expansión en forma de polinomio, el término libre es igual a , por lo tanto, es verdadera cuando . $(-1)^x=1$ $X$ $q_{0}$ ${\ estilo de visualización 0}$ $(-1)^x = -1$ $q_0 = 1$

Ahora transformamos la descomposición conocida e introducimos una nueva variable : $z_{1}$

b\equiv a^x\equiv a^{x_1 + q_0}\pmod{p}\Rightarrow z_1\equiv ba^{-q_0}\equiv a^{x_1}\pmod{p}

dónde

x_1 = \sum\limits_{i = 1}^{n-1}q_i2^i=q_{1}2^1 + q_{2}2^2 + \cdots + q_{n-1}2^{n -una}

Está claro que es divisible por when , y when es divisible por , pero ya no. $x_{1}$ $cuatro$ $q_1=0$ $q_1=1$ $2$ $cuatro$

Argumentando como antes, obtenemos la comparación :

z_1^{(p-1)/4}\pmod{p}\equiv \begin{casos}+1, & q_1 = 0\\ -1, & q_1 = 1, \end{casos}

de la que nos encontramos . $q_{1}$

Los bits restantes se obtienen de manera similar. Escribamos la solución general de hallar con nueva notación: $q_{yo}$

m_i=(p-1)/2^{i+1}

z_i\equiv b\cdot a^{-q_0 - q_{1}2^1 - \dots - q_{i-1}2^{i-1}}\equiv a^{x_i}\pmod{p}

dónde

x_i = \sum\limits_{k = i}^{n-1}q_k2^k

Entonces elevando a una potencia da: $z_{yo}$ $mi$

z_i^{m_i} \equiv a^{(x_{i}\cdot m_i)}\equiv\left(a^{(p-1)/2}\right)^{(x_i/2^i)}\ equivalente (-1)^{x_i/2^i}\equiv(-1)^{q_i}\pmod{p}

Como consecuencia:

z_i^{m_i}\pmod{p}\equiv \begin{casos}+1, & q_i = 0\\ -1, & q_i = 1, \end{casos}

de la que nos encontramos . $q_{yo}$

Habiendo encontrado todos los bits, obtenemos la solución requerida . [6] $X$

Ejemplo

Dado:

a = 3,\;b = 11,\;p = 17 = 2^4 + 1

Encontrar:

X

Solución:
Obtenemos . Por lo tanto, parece: $p-1=2^4$ $X$

x = q_0 + q_{1}2^1 + q_{2}2^2 + q_{3}2^3

Encontramos : $q_{0}$

b^{(p-1)/2} \equiv 11 ^ {(17 - 1)/2} \equiv 11 ^ {8} \equiv (-6) ^ 8 \equiv (36) ^ 4 \equiv 2 ^ 4 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_0 = 1

También contamos : $z_{1}$ $m_1$

z_1 \equiv b\cdot a^{-q_0} \equiv 11\cdot 3 ^{-1} \equiv 11 \cdot 6 \equiv 66 \equiv -2 \pmod{17}

m_1 = (p-1)/2^{1+1}= (17 - 1)/2^2 = 4

Encontramos : $q_{1}$

z_1^{m_1} \equiv (-2)^4 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_1 = 1

También contamos : $z_{2}$ $m_2$

z_2 \equiv z_1 \cdot a^{-q_{1}2^1} \equiv (-2) \cdot 3^{-2} \equiv (-2) \cdot 6^2 \equiv (-2) \ cdot 36 \equiv (-2) \cdot 2 \equiv -4 \equiv 13 \pmod{17}

m_2 = (p-1)/2^{2+1}= (17 - 1)/2^3 = 2

Encontramos : $q_{2}$

z_2^{m_2} \equiv 13 ^2 \equiv (-4) ^2 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_2 = 1

También contamos : $z_{3}$ $m_3$

z_3 \equiv z_2 \cdot a^{-q_{2}\cdot2^2} \equiv 13 \cdot 3^{-4} \equiv 13 \cdot 9^{-2} \equiv 13 \cdot 2^2 \ equivalente (-4) \cdot 4 \equiv -16 \equiv 1 \pmod{17}

m_3 = (p-1)/2^{3+1}= (17 - 1)/2^4 = 1

Encontramos : $q_{3}$

z_3^{m_3} \equiv 1 ^ 1 \equiv 1 \pmod{17} \Rightarrow q_3 = 0

Encuentra lo que buscas : $X$

x = 1 + 1\cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 \equiv 7

Responder: $x=7$

Descripción básica

Paso 1 (recopilación de la tabla). Haz una tabla de valores , donde

\{r_{i,j}\}

r_{i,j}=a^{j\cdot\frac{p-1}{q_i}}, i\in\{1,\dots,k\}, j\in\{0,\dots,q_i -una\}.

Paso 2 (cálculo ).

\log_a{b}\;\bmod{q_i^{\alpha_i}}

Para i de 1 a k : Dejar

x\equiv\log_a{b}\equiv x_0+x_1q_i+...+x_{\alpha_{i}-1}q_i^{\alpha_{i}-1}\pmod{q_i^{\alpha_i)),

dónde

0\leq x_i\leq q_i-1

. Entonces la comparación es correcta:

a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}

Salida de comparación superior

Elevemos las partes izquierda y derecha de la comparación (1) a la potencia : $(p-1)/q_i$

a^{x\cdot \frac{p-1}{q_i}} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p}

Sustituye y transforma la comparación: $X$

a^{x_0 \cdot \frac{p-1}{q_i} + x_1\cdot(p-1) + x_2\cdot q_i \cdot(p-1) + \dots + x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i)) \pmod{p}

a^{x_0 \cdot \frac{p-1}{q_i}}\cdot a^{x_1\cdot(p-1)} \cdot a^{x_2\cdot q_i \cdot(p-1)} \cdot \puntos \cdot a^{x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i)) \pmod {pags}

Porque es un elemento primitivo, por lo tanto comparaciones de la forma: $a$

a^{m \cdot (p-1)} \equiv 1 \pmod{p},\;\forall m \in \{0,1, \dots, p-1\}

Obtenemos

a^{x_0 \cdot \frac{p-1}{q_i}}\cdot 1 \cdot 1 \cdot \dots \cdot 1 \equiv b ^ {\frac{p-1}{q_i}} \pmod{p }

a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}

[cuatro] Usando la tabla compilada en el paso 1, encontramos For j de 0 a

x_{0}.

\alpha_{i}-1

Teniendo en cuenta una comparación

a^{x_{j}\cdot\frac{p-1}{q_i}} \equiv (ba^{-x_0-x_1q_i...-x_{j-1}q_i^{j-1}})^ {\frac{p-1}{q_i^{j+1}}} \pmod{p}

La solución se encuentra nuevamente en la tabla. Fin del ciclo en j Fin del ciclo en i Paso 3 (encontrar la respuesta). Encontrando para todo i , encontramos por el teorema chino del resto . [7]

\log_a{b}\;\bmod{q_i^{\alpha_i}}

\log_a{b}\;\bmod\;(p-1)

Ejemplo

Es necesario encontrar el logaritmo discreto en base a , es decir, encontrar para: $28$ $2$ $novia(37)$ $X$

2^x \equiv 28 \pmod{37}

Encontramos una descomposición . $\varphi(37) = 37 - 1 = 36 = 2^{2}\cdot3^{2}$

obtenemos _ $q_{1} = 2, \alpha_{1} = 2, q_{2} = 3, \alpha_{2} = 2$

Hacemos una tabla : $r_{{ij}}$

r_{20}\equiv 2^{0\cdot {\frac {37-1}{2}}}\equiv 1{\pmod {37}}

r_{21}\equiv 2^{1\cdot {\frac {37-1}{2}}}\equiv 2^{18}\equiv -1{\pmod {37}}

r_{30}\equiv 2^{0\cdot {\frac {37-1}{3}}}\equiv 1{\pmod {37}}

r_{31}\equiv 2^{1\cdot {\frac {37-1}{3))}\equiv 2^{12}\equiv 26{\pmod {37))

r_{32}\equiv 2^{2\cdot {\frac {37-1}{3))}\equiv 2^{24}\equiv 10{\pmod {37))

estamos considerando por cierto: $q_{1} = 2$ $X$

x\equiv x_{0} + x_{1}q_{1} \pmod{q_{1}^{\alpha_i}} \equiv x_{0} + x_{1}\cdot 2 \pmod{2^2}

Encontramos por comparación: $x_{{0}}$

a^{x_{0}\cdot\frac{p-1}{q_{1}}} \equiv b^{\frac{p-1}{q_{1}}} \pmod{p}\Rightarrow 2 ^{x_{0}\cdot\frac{37 - 1}{2}} \equiv 28^{\frac{37-1}{2}} \equiv 28^{18} \equiv 1 \pmod{37}

De la tabla encontramos que para la comparación anterior es cierto. $x_{0}=0$

Encontramos por comparación: $x_{1}$

a^{x_{1}\cdot\frac{p-1}{q_{i))} \equiv (b\cdot a^{-x_{0)))^{\frac{p-1}{q_ {i}^{2}}} \Rightarrow 2^{x_{1}\cdot\frac{37 - 1}{2}} \equiv (28 \cdot 2 ^ {-0}) ^ {\frac{37 -1}{4}} \equiv 28 ^{9} \equiv -1 \pmod{37}

De la tabla obtenemos que la comparación anterior es cierta. Encontramos : $x_{1} = 1$ $X$

x \equiv 0 + 1 \cdot 2 \equiv 2 \pmod{4}

Ahora estamos considerando . por cierto: $q_{2} = 3$ $X$

x \equiv x_{0} + x_{1}\cdot3 \pmod{3^2}

Por analogía , encontramos : $x_{{0}}$ $x_{1}$

2^{x_0\cdot\frac{37 - 1}{3}} \equiv 28 ^ {\frac{37-1}{3}} \equiv 28^{12} \equiv 26 \pmod{37} \Rightarrow x_0 = 1

2^{x_1\cdot\frac{37 - 1}{3}} \equiv (28\cdot 2^{-1}) ^ {\frac{37 - 1}{3^2}} \equiv 14 ^ { 4} \equiv 10 \pmod{37} \Rightarrow x_{1} = 2

obtenemos : $X$

x \equiv 1 + 2 \cdot 3 \equiv 7\pmod{9}

Obtenemos el sistema:

\begin{casos} x \equiv 2 \pmod{4} \\ x \equiv 7 \pmod{9} \\ \end{casos}

Resolvamos el sistema. Transformamos la primera comparación en igualdad, que sustituimos en la segunda comparación:

x = 2 + 4 \cdot t \Rightarrow 2 + 4\cdot t \equiv 7 \pmod{9} \Rightarrow 4\cdot t \equiv 5 \pmod{9} \Rightarrow

t \equiv 5\cdot (4)^{-1} \equiv 5 \cdot (-2) \equiv -10 \equiv 8 \pmod{9}

Sustituimos lo que encontramos y obtenemos lo que buscamos : $t$ $X$

x \equiv 2 + 4 \cdot 8 \equiv 34 \pmod{36} \equiv 34 \pmod{37}

Respuesta: . [ocho] $x=34$

Complejidad del algoritmo

Si se conoce la expansión (2), entonces la complejidad del algoritmo es

O\left(\sum\limits_{i=1}^{k}\alpha_{i}\left(\log_2{p} + q_{i}^{1 - r_i}(1 + \log_{2}{ q_{i}^{r_{i}}}})\derecha)\derecha)

, donde .

0\leq r_{i}\leq1

Esto requiere un poco de memoria. [9] $O\left(\log_2{p}\sum\limits_{i=1}^{k}\left(1 + p_i^{r_i}\right)\right)$

En general, la complejidad del algoritmo también se puede estimar como

O\left(\sum\limits_{i=1}^{k}\alpha_i q_i + \log{p}\right)

. [diez]

Si, al procesar cada q i , se utilizan métodos acelerados (por ejemplo, el algoritmo de Shanks ), la puntuación general disminuirá a

O\left(\sum\limits_{i=1}^{k}\alpha_i \sqrt{q_i} + \log{p}\right)

En estas estimaciones, se supone que las operaciones aritméticas módulo p se realizan en un solo paso. De hecho, este no es el caso; por ejemplo, la suma módulo p requiere operaciones elementales O (log p ). Pero dado que se realizan refinamientos similares para cualquier algoritmo, este factor a menudo se descarta.

Complejidad polinomial

Cuando los factores primos son pequeños, la complejidad del algoritmo se puede estimar como . [once] $\izquierda\{q_{i}\derecha\}_{i=1}^{k}$ $O\izquierda((\log_2p)^2\derecha)$

El algoritmo tiene complejidad polinómica en general en el caso de que todos los factores primos no superen , donde son constantes positivas. [una] $O\izquierda((\log p)^{c_1}\derecha)$ $\izquierda\{q_{i}\derecha\}_{i=1}^{k}$ $(\log p)^{c_2}$
$c_1, c_2$

Ejemplo

Cierto para especies simples . $pags$ $p=2^{\alfa} + 1,\;p=2^{\alfa_1}3^{\alfa_2} + 1$

Complejidad exponencial

Si existe un factor primo tal que , donde . [una] $q_{yo}$ $q_i\geq p^{c}$ $c\geq 0$

Aplicación

El algoritmo de Polig-Hellman es extremadamente eficiente cuando se descompone en pequeños factores primos. Es muy importante tener esto en cuenta al elegir los parámetros de los esquemas criptográficos. De lo contrario, el esquema no será confiable. $p-1$

Nota

Para aplicar el algoritmo de Polig-Hellman, necesita conocer la factorización. En el caso general, el problema de factorización requiere bastante tiempo, pero si los divisores de un número son pequeños (en el sentido mencionado anteriormente), este número se puede factorizar rápidamente incluso mediante el método de división sucesiva. Así, en el caso de que el algoritmo de Polig-Hellman sea eficiente, la necesidad de factorización no complica el problema. $p-1$

Notas

↑ 1 2 3 Vasilenko, 2003 , pág. 131.
↑ Pohlig et al., 1978 .
↑ Odlyzko, 1985 , pág. 7.
↑ 1 2 Koblitz, 2001 , pág. 113.
↑ Koblitz, 2001 , pág. 113-114.
↑ Pohlig et al., 1978 , pág. 108.
↑ Vasilenko, 2003 , pág. 130-131.
↑ Koblitz, 2001 , pág. 114.
↑ Odlyzko, 1985 , pág. ocho.
↑ Hoffstein y otros, 2008 , pág. 87.
↑ Pohlig et al., 1978 , pág. 109.

Literatura

en ruso

N. Koblitz. Un curso de teoría de números y criptografía . - M. : Editorial científica TVP, 2001. - 254 p. (Ruso)
O. N. Vasilenko. Algoritmos de Teoría de Números en Criptografía . - M. : MTSNMO, 2003. - 328 p. - 1000 copias. — ISBN 5-94057-103-4 . (Ruso) Archivado el 27 de enero de 2007 en Wayback Machine .

en inglés

SC Pohlig y ME Hellman. Un algoritmo mejorado para calcular logaritmos sobre GF (p) y su significado criptográfico // Transacciones IEEE sobre teoría de la información. - 1978. - vol. 1 , no. 24 . - P. 106-110 .
A. M. Odlyzko. Logaritmos discretos en campos finitos y su significado criptográfico // T.Beth , N.Cot, I.Ingemarsson Proc. del taller EUROCRYPT 84 sobre Avances en criptología: teoría y aplicación de técnicas criptográficas. - NY, USA: Springer-Verlag New York, 1985. - Págs. 224-314 . - ISBN 0-387-16076-0 . (enlace no disponible)
J. Hoffstein, J. Pipher, J. H. Silverman. Introducción a la criptografía matemática . - Springer, 2008. - 524 págs. — ISBN 978-0-387-77993-5 .