¿Cómo puedo solucionar este problema? $2^{x} \equiv{2070442609 \cdots 226509} \pmod {6561}$

Question

Quiero resolver este problema de logaritmo discreto con Algoritmo Pohlig-Hellman:

$$2^{x} \equiv{ 2070442609353644988500364779751625112994538364565830646055667805\\ 1945605813418120257083690993568845753318608515495923060805120997\\ 3428789429908548559535354422962118802026940584074383162419987316\\ 4251257235243687584403222687359220263252625476372842589113471426\\ 1782004893903634453733275871450024554309850603821543260259554681\\ 9788249500416881166827892874757890895573842787278113899169213463\\ 6207754656894365789382736647587424234413487070250150001802765877\\ 5362018623752370739226509} \pmod {6561}$$

De hecho, no sé cómo hacerlo, porque los números parecen terribles. Para resolver este logaritmo discreto he leído algunos ejemplos en libros PDF. Pero, no he podido aplicar este problema. No parece que sea un problema que pueda resolver por mi cuenta. Espero que me puedan ayudar.

¡Muchas gracias!

Answer 1

Aborté intentando reducir ese monstruo mod 6561 a mano, pero seguiré con el algoritmo a mano.

En primer lugar, porque todo lo que importa es mod poderes de $3$ haremos nuestra aritmética en base 9. Queremos resolver $2^x\equiv 2732_9\mod 10000_9$ .

El primer paso del algoritmo consiste en dividir las cosas en función de los factores primos del orden del grupo en el que estamos trabajando. Aquí, ese orden es $n=\phi(3^8)=2\cdot 3^7$ .

En primer lugar, los poderes de $2$ . Elevar tanto el generador como el objetivo al $\frac{n}{2}$ potencia; queremos resolver $\left(2^{3^7}\right)^x\equiv(2732_9)^{3^7}$ - o, simplemente, $(-1)^x\equiv-1$ . (Sólo necesitamos saber qué $k$ es mod $3$ para determinar su $3^7$ potencia mod. $3^8$ ). La solución es $x\equiv 1\mod 2$ .

A continuación, los poderes de $3$ - la parte interesante. Levantar ambos generadores $g$ y objetivo $h$ a la $\frac{n}{3^7}=2$ poder: $2^2\equiv 4$ y $$2732_9^2 = \begin{array}{r}5564\phantom{000}\\ 21645\phantom{00}\\ 8406\phantom{0}\\5564\\ \hline 7840234\end{array}\equiv 0234_9$$ Ahora pasamos al algoritmo de primera potencia, resolviendo $4^x\equiv 0234_9\mod 10000_9$ (en el orden $3^7$ subgrupo). En primer lugar, debemos calcular $\gamma \equiv 4^{3^6}$ . $(1+3)^{3^6}=1+3\cdot 3^6+3^2\cdot \binom{3^6}{2}+3^3\cdot\binom{3^6}{3}+\cdots$ y todos los términos menos los dos primeros son divisibles por $3^8$ Así que $\gamma = 4^{3^6}\equiv 3001_9\mod 10000_9$ .

Ahora, el bucle central. Ejecutamos $k$ de $0$ a $6$ primer cálculo $h_k=\left(g^{-x_k}h\right)^{3^{6-k}}$ y, a continuación, encontrar $d_k$ tal que $\gamma^{d_k}=h_k$ a continuación, establezca $x_{k+1}=x_k+3^k d_k$ .

Mientras que la página wiki en la que copié el algoritmo sugiere el algoritmo "baby-step giant-step" para encontrar $d_k$ No lo haremos aquí. $d_k$ oscila entre $0$ a $p-1$ y para $p=3$ podemos encontrarlo mediante inspección.

$k=0$ :
$x_0$ se inicializa como cero, por supuesto. Tenemos $h_0\equiv (0234_9)^{3^6} \equiv 4+(3^2\cdot 23_9)^{3^6} \equiv 4^{3^6}+3^8\cdot\text{stuff}\equiv 3001_9$ .
Entonces $3001_9^1\equiv 3001_9$ y $d_0=1$ .
Por fin, $x_1= 0 + 1\cdot 1 = 1$ .

$k=1$ :
$h_1\equiv (4^{-1}\cdot 0234_9)^{3^5}\equiv (6731_9)^{3^5}\equiv (1+3^3\cdot\text{stuff})^{3^5}\equiv 1$ .
Esto hace que $d_1=0$ .
Por fin, $x_2=1+3\cdot 0=1$ .

$k=2$ :
$h_2\equiv (4^{-1}\cdot 0234_9)^{3^4}\equiv (6731_9)^{3^4}\equiv (1+3^3\cdot(1+3\cdot \text{stuff}))^{3^4}\equiv 1 +3^7\cdot(1+3\cdot \text{stuff})\equiv 3001_9$ .
Esto hace que $d_2=1$ .
Por fin, $x_3=1+3^2\cdot 1=11_9$ .

$k=3$ :
$h_3\equiv (4^{-11_9}\cdot 0234_9)^{3^3}$ . Esto requiere algunos cálculos, pero $4^9\equiv 8531_9$ y $4^{-9}\equiv 4361_9$ . Entonces $4361_9\cdot 6731_9\equiv 1\color{red}{2}01$ . Ahora $h_3\equiv (1201_9)^{3^3}\equiv \left(1+3^4(2+3^2)\right)^{3^3}\equiv 1+2\cdot 3^7+\text{stuff}\equiv 6001_9$ .
Esto hace que $d_3=2$ .
Por fin, $x_4=11_9+3^3\cdot 2=71_9$ .

$k=4$ :
$h_4\equiv (4^{-71_9}\cdot 0234_9)^{3^2}\equiv \left(4^{-2\cdot 3^3}\cdot 1201_9\right)^{3^2}$ . Tenemos $4^{3^3}\equiv 1701_9$ y $4^{-3^3}\equiv 7201_9$ elevar al cuadrado y multiplicar por $1201_9$ para $(1200_9+7200_9+7200_9)+1\equiv 6601_9$ . Ahora $h_4\equiv (6601_9)^{3^2}\equiv 6001_9$ .
Esto hace que $d_4=2$ .
Por fin, $x_5=71_9+3^4\cdot 2=271_9$ .

$k=5$ :
$h_5\equiv (4^{-271_9}\cdot 0234_9)^3\equiv \left(4^{-2\cdot 3^4}\cdot 6601_9\right)^3$ . Tenemos $4^{3^4}\equiv 1701_9^3\equiv 1+3\cdot 1701_9\equiv 5301_9$ y $4^{-3^4}\equiv 3601_9$ elevar al cuadrado y multiplicar por $6601_9$ para $5001_9$ . Ahora $h_5\equiv (5001_9)^3\equiv 6001$ .
Esto hace que $d_5=2$ .
Por fin, $x_6=271_9+3^5\cdot 2=871_9$ .

$k=6$ :
$h_6\equiv (4^{-871_9}\cdot 0234_9)^1\equiv \left(4^{-2\cdot 3^5}\cdot 5001_9\right)^1$ . Tenemos $4^{-3^5}\equiv 2001$ elevando al cuadrado y multiplicando se obtiene $h_6\equiv 1$ .
Esto hace que $d_6=0$ .
Por fin, $x_7=871_9+3^6\cdot 0=871_9$ .

Ese es nuestro resultado: $x\equiv 871_9\mod 3^7$ . Convirtiendo de nuevo a base diez, eso es $x\equiv 8\cdot 81+7\cdot 9+1\equiv 712\mod 2187$ .

El paso final es combinar lo que obtuvimos para potencias de 2 y potencias de 3. Queremos algo que sea $1$ mod $2$ y $712$ mod $2187$ respuesta final $2899\mod 4374$ .

Mi primera respuesta no coincide. Hora de comprobarlo... La comprobación con ayuda de la hoja de cálculo ha encontrado el error, marcado en rojo (1101 según el cálculo inicial, lo que lleva a $3025$ respuesta final). Recalculando de ahí en adelante... Vale, ya lo tengo.

Aunque el trabajo que supone hacerlo a mano no es demasiado duro, es tan largo que es muy fácil cometer un error aritmético que lleve a una respuesta errónea. No lo recomendaría sin al menos comprobar mecánicamente las distintas piezas aritméticas. Al menos para eso no se necesitan herramientas especialmente sofisticadas.

Answer 2

En los comentarios lo han reducido a un problema muy manejable.

He intentado resolver el problema de dl $2^x\cong 2054\pmod{6561}$ utilizando el algoritmo Pohlig-Hellman, pero no conseguí hacerlo a mano.

Me encontré con un problema, no sé si es un bug o (probablemente) sólo yo.

De todos modos, encontré una calculadora en Internet que me dio la respuesta en cuestión de segundos.

Dio

$2899+4374k$ .