Test de primalidad de Miller-Rabin

El test de primalidad de Miller-Rabin és un test de primalidad, és dir, un algoritme per a determinar si un número donat és primer, similar al test de primalidad de Fermat. La seua versió original va ser proposta per G. L. Miller, es tractava d'un algoritme determinista, pero basat en la no demostrada hipòtesis generalisada de Riemann; Michael Oser Rabin va modificar la proposta de Miller per a obtindre un algoritme provabilístic que no utilisa resultats no provats.

Conceptes matemàtics

De forma similar a les proves Fermat i Solovay-Strassen, la prova de primalidad de Miller-Rabin comprova si una propietat específica, que se sap que és verdadera per als número primo, se satisfà per al número a prova.

Provables cosins forts

Donat un sancer impar n > 2, escrivim n com 2^s⋅d + 1 a on s i d són sancers positius i d és impar. Siga a un número entero tal que 0 < a < n. Llavors, direm que n és provable primer fort per a la base a si es complix alguna de les següents relacions de congruència:

• $a^d\equiv 1(\mathrm{mod}n)$;
• $a^{2^r\cdot d}\equiv -1(\mathrm{mod}n)$ per a algun 0 ≤ r < s.

L'idea darrere del test de Miller-Rabín és que quan n és un cosí impar, passa el test per dos resultats:

• pel menuda teorema de Fermat, $a^{n-1}\equiv 1(\mathrm{mod}n)$ (esta propietat per sí sola és una noció més dèbil provable cosí dèbil per a la base a, sobre la qual està basat el test de primalidad de Fermat);
• les úniques raïls quadrades de l'1 mòdul n són 1 i −1.

Per contraposició, si n no és un provable cosí fort per a alguna base a, llavors n és compost i a és cridat un testic de la propietat de que n és compost.

No obstant, esta propietat no és una caracterisació exacta dels número primo. Si n és compost, pot haver una base a para la qual n siga provable cosí fort, en el cas del qual es diu un pseudoprimo fort i a li'l denomina un boler fort.

El test provabilístic de Miller-Rabin es basa en la comprovació per a diferents bases de que un número donat és provable cosí fort.

Elecció de bases

Afortunadament, cap número compuesto és un pseudoprimo fort per a totes les bases al mateix temps. No obstant, no es coneix una forma senzilla de trobar un testic. Una solució ingènua és provar totes les bases possibles, lo que produïx un algoritme determinista ineficiente. La prova de Miller determinista és una variant més eficient d'açò.

Una atra solució és elegir una base a l'encert. Açò produïx una ràpida prova provabilística. Quan n és compost, la majoria de les bases són testics, per lo que la prova detectarà n com a compost en una provabilitat raonablement alta, major que 0.75. Podem reduir ràpidament la provabilitat d'un fals positiu a una taxa arbitrariamente menuda, combinant el resultat de tantes bases elegides independentment com siga necessari per a conseguir dita taxa. En açò consistix el test provabilístic de Miller-Rabin. El número de bases a provar no depén de n.

Per a fer el test a un n arbitrariamente gran, elegir bases a l'encert és essencial, ya que no coneixem la distribució de testics i bolers forts entre els números 1, 2, …, n−1.

Demostracions

Ací una demostració de que quan n és un cosí impar, les úniques raïls quadrades d'1 mòdul n són 1 i −1.

Plantilla:Demostració

Ací una demostració de que si n és un cosí impar, llavors n és provable cosí fort per a qualsevol base a.

Test de Miller–Rabin

L'algoritme es pot escriure en pseudocódigo de la següent manera. El paràmetro k determina la precisió de la prova. Quant major siga el número de rondes (k és el número de rondes), major precisió tindrà el resultat.

Pseudocódigo estil Python:

def test_Miller_Rabin(n: int, k: int) -> bool:
    s, d = satisfan n = 2*s * d + 1, d impar
    repetir k voltes:
        a = sancer a l'encert entre 2 i n-1
        fpp = False # fortament primer segons
        if 1 == a*d % n:
            fpp = True
        else:
            r = 0
            while r  <= s and fpp == False:
                if n - 1 == a**(2*r * d) % n:
                    fpp = True
         if fpp == False: # si no passa la prova
            return False
    # si va passar les k proves
    return True