Período máximo

01 · Punto de partida

Del olfato al teorema

En el Tema 13 viste el patrón empírico: con m = 16 funcionaban los a ≡ 1 mod 4 con c impar. No era coincidencia de ese m: es un caso de un teorema general que decide sin iterar si un mixto recorre todo el anillo.

Ese teorema es Hull–Dobell (1962): tres condiciones aritméticas necesarias y suficientes para período m. Con m de millones no podés medir el ciclo corriendo; con el teorema lo garantizás en papel.

• ¿Cuáles son las tres condiciones exactas?
• ¿Por qué con m = 2ᵏ se reducen a «c impar y a ≡ 1 mod 4»?
• ¿Qué pasa con multiplicativos (c = 0)?
• ¿Período máximo implica generador bueno?

02 · Teorema

Hull–Dobell sin miedo

Lee cada condición como una prohibición de «quedar atrapado en un sub-anillo»:

03 · Casos particulares

Dos atajos que usarás siempre

m = 2ᵏ (el rápido)

Primos de m: solo el 2. Condiciones: c impar y a ≡ 1 mod 4. Es lo que verificaba el laboratorio del Tema 13.

c = 0 (multiplicativo)

Hull–Dobell no aplica (falla (1) salvo m = 1). El techo pasa a m−1 y se necesita a raíz primitiva (si m primo) u otras condiciones (si potencia de 2). Detalle en Tema 12 y apéndice de params.

m primo (ej. 2³¹−1)

Primos de m: el propio m. Para mixto con ese m se pide a−1 múltiplo de m, casi imposible con a < m: por eso los primos se usan en multiplicativos, no en mixtos.

04 · Ejemplos

Leer el teorema en 4 tríos

1. 1
   (5,3,16): pasa todo.

   m = 2⁴: c impar ✓, 5−1 = 4 divisible por 2 y por 4 ✓ → p = 16.

2. 2
   (4,2,16): falla todo.

   c par ✗, 4−1 = 3 no divisible por 2 ✗ → p ≤ 4.

3. 3
   (5,3,15): trampa del 3.

   m = 3·5: mcd(3,15) = 3 ≠ 1 en realidad… espera: mcd(3,15)=3, ya falla (1). Incluso con c=7 (mcd 1), 5−1=4 no es múltiplo de 3 ✗.

4. 4
   (13,7,64): pasa.

   13−1 = 12 divisible por 2 y por 4 ✓, c impar ✓ → p = 64.

05 · Verificación en Python

El teorema en 15 líneas

Factorizar m chico es trivial; con m real se factoriza una vez en papel (es potencia de 2 o primo conocido).

import math

def primos_distintos(m):
    ps, d = set(), 2
    while d * d <= m:
        if m % d == 0:
            ps.add(d)
            while m % d == 0:
                m //= d
        d += 1 if d == 2 else 2
    if m > 1:
        ps.add(m)
    return ps

def hull_dobell(a, c, m):
    if math.gcd(c, m) != 1:
        return False, "falla (1): mcd(c,m)!=1"
    for p in primos_distintos(m):
        if (a - 1) % p != 0:
            return False, f"falla (2): {p} no divide a-1"
    if m % 4 == 0 and (a - 1) % 4 != 0:
        return False, "falla (3): m mult de 4 pero a!=1 mod4"
    return True, "período completo m"


for trio in [(5, 3, 16), (4, 2, 16), (13, 7, 64)]:
    print(trio, hull_dobell(*trio))

06 · Exploración

Laboratorio: verificador Hull–Dobell

Elegí a, c, m. Las tres luces chequean (1), (2) y (3); el panel da el período medido y el veredicto. Probá romper una sola condición y mirá el costo.

Barras: estados visitados en verde, no visitados en rojo. Período completo = todo verde.

Preguntas para explorar

1. Con m = 16 y (5,3), ¿qué luces dan? Cambiá a (5,2): ¿cuál se apaga y a cuánto cae p?
2. Con m = 60 (=2²·3·5), ¿qué pide la condición (2)? Probá a = 5: ¿pasa? ¿Y a = 21?
3. Si las tres dan verde pero N = 10⁶ con m = 60, ¿sirve igual? ¿Por qué el teorema no basta?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: verificar (13,7,64)

Usá la función del Tema y medí el período. ¿Coinciden teoría y medición?

def periodo(a, c, m, s=7):
    v = set()
    x = s
    while x not in v:
        v.add(x)
        x = (a * x + c) % m
    return len(v)


print(periodo(13, 7, 64))

Ejercicio 2: fabricar un completo para m = 32

Elegí c impar y a ≡ 1 mod 4 distintos de (5,3) y verificá p = 32.

print(periodo(9, 7, 32))
print(periodo(17 % 32, 11, 32))

Ejercicio 3: la trampa del 15

Con m = 15 (=3·5), probá (5,3): ¿p? ¿Qué condición falla?

print(periodo(5, 3, 15))
print(periodo(5, 7, 15))

09 · Síntesis

Ideas para recordar

En el próximo tema combinaremos generadores para ir más lejos: generadores congruenciales combinados.