¿Cuál es el algoritmo más eficiente para encontrar el período de Pisano para un entero dado (incluso para enteros grandes)?

El período de Pisano [math] \ pi (n) [/ math] es una función multiplicativa, es decir, si [math] a [/ math] y [math] b [/ math] son ​​números coprimos que [math] \ pi (ab ) = \ pi (a) \ pi (b) [/ math]. Por lo tanto, solo debemos preocuparnos por el valor de [math] \ pi (p ^ k) [/ math] para prime [math] p [/ math]. (Factorizar incluso un gran número es aún mejor que la búsqueda de periodicidad de fuerza bruta).

Se presume que [math] \ pi (p ^ k) = p ^ {k-1} \ pi (p) [/ math] y dado que no se sabe que existan contraejemplos, también podría usarlo en su algoritmo.

Entonces, ¿cómo calcular [matemáticas] \ pi (p) [/ matemáticas] de manera eficiente? Hay dos casos especiales y dos casos generales.

[matemáticas] \ pi (2 ^ k) = 3 \ cdot 2 ^ {k-1} [/ matemáticas]

[matemáticas] \ pi (5 ^ k) = 4 \ cdot 5 ^ {k} [/ matemáticas]

Si [math] p \ equiv 1 [/ math] o [math] p \ equiv 9 \ pmod {10} [/ math] entonces [math] \ pi (p) \ mid p-1 [/ math]

Si [matemática] p \ equiv 3 [/ matemática] o [matemática] p \ equiv 7 \ pmod {10} [/ matemática] entonces [matemática] \ pi (p) \ mid 2 (p + 1) [/ matemática] , y por un divisor impar también.

Las últimas dos declaraciones nos dan un número relativamente pequeño de casos para probar (después de factorizar [matemática] p-1 [/ matemática] o [matemática] 2 (p + 1) [/ matemática].) Ahora use su fórmula favorita para calcular valores grandes de los números de Fibonacci [matemática] F (x) \ bmod p [/ matemática]. Vea la respuesta de Michal Forišek a ¿Qué es un algoritmo rápido para encontrar el resto de la división de un gran número de Fibonacci por algún número entero grande? Para probar un período candidato [matemática] R [/ matemática], calcule [matemática] F (R) \ bmod p [/ matemática] y [matemática] F (R + 1) \ bmod p [/ matemática]. Si estos son iguales a [matemática] F (0) = 0 [/ matemática] y [matemática] F (1) = 1 [/ matemática], entonces [matemática] \ pi (p) \ mid R [/ matemática].

Puede ser que [matemática] p-1 [/ matemática] o [matemática] 2 (p + 1) [/ matemática] tengan muchos divisores, pero no necesitamos probarlos todos. Suponga que [matemática] q ^ k \ mid R [/ matemática] para algunos primos q. Luego pruebe [matemáticas] R / q [/ matemáticas]. Si eso no produce un ciclo, entonces [math] \ pi (p) [/ math] debe tener el factor [math] q ^ k [/ math], y podemos dejarlo y continuar con otros factores. De lo contrario, podemos usar [math] R / q [/ math] como nuestro nuevo punto de partida y repetir el proceso. Por lo tanto, tenemos que hacer varias verificaciones proporcionales a [matemáticas] \ Omega (2 (p + 1)) [/ matemáticas], no a [matemáticas] d (2 (p + 1)) [/ matemáticas].