Cómo calcular el resto de un número expresado en términos de exponentes apilados módulo N

Answer 1

Defina [matemáticas] f (S): = S ^ {f (S-1)} [/ matemáticas] para [matemáticas] s> 1 [/ matemáticas] y [matemáticas] f (1) = 1 [/ matemáticas].

Defina [math] g (S, N) [/ math] para que sea el entero menos positivo equivalente a [math] f (S) \ mod N [/ math].

Para calcular [matemática] g (S, N) [/ matemática], utilizaremos el teorema del totiente de Euler [1].

Establece que [matemáticas] S ^ {\ phi (N)} \ equiv 1 \ mod N [/ matemáticas]

[math] \ phi (N) [/ math] es el número de enteros menores que [math] N [/ math] que son relativamente primos para [math] N [/ math].

Esto significa que si [math] a \ equiv b \ mod \ phi (N) [/ math], entonces [math] S ^ a \ equiv S ^ b \ mod N [/ math]

Entonces [matemáticas] g (S, N) \ equiv S ^ {g (S-1, \ phi (N))} [/ matemáticas]

Esto significa que puede resolver su problema muy fácilmente con recursividad.

Puede que le preocupe que tendrá que hacer llamadas de función [matemáticas] S [/ matemáticas] incluso cuando [matemáticas] S [/ matemáticas] sea casi [matemáticas] 10 ^ 9 [/ matemáticas], pero no lo hace porque [ matemática] g (S, 1) = 0 [/ matemática] y para todos [matemática] N [/ matemática], [matemática] \ phi ^ k (N) [/ matemática] converge a [matemática] 1 [/ matemática] (y lo hace con bastante rapidez).

De hecho, usando [math] g (S, 1) = 0 [/ math] como el caso base para su recursión, solo necesitará [math] O (\ log (N)) [/ math] llamadas a funciones.

Notas al pie

[1] Función totient de Euler – Wikipedia