Carmichael tal – Kryptologi

Vi er ikke helt færdige med Fermats primtalstest.

I afsnittet om Fermats primtalstest diskuterer jeg hvordan man kan teste om et stort tal m er et primtal.

Mere præcist; vi så på hvor mange af tallene a = 1,2,3, …, m – 1 som opfylder at

\(a^{m-1} \equiv 1 \textrm{ mod } m \)

Hvis m er et primtal, så skal \(a^{m-1} \equiv 1 \textrm{ mod } m \) for alle værdier af a, fra a = 1, til a = m – 1.

Hvis vi bare har en værdi af a, så \(a^{m-1}\) ikke er lig 1, modulo m, så kan m ikke være et primtal.

Vi så også, at for langt de fleste tal m, som ikke er primtal, så vil de a‘er, hvor \(a^{m-1} \equiv 1 \textrm{ mod } m \), typisk kun udgøre få procent af samtlige a‘er fra a = 1 til a = m -1.

I dette afsnit vil vi ikke se på alle værdier af a, fra a = 1 til a = m – 1. Vi vil kun se på de værdier af a som er primiske med m.

Python-program

Ved at ændre minimalt i python-programmet fra forrige afsnit, så kan jeg, for hver værdi af m, optælle hvor mange af a‘erne der både er primiske med m, og som giver 1, når a opløftes i potensen m – 1. Vi regner naturligvis modulo m.

import math
mmax=1000
for m in range(1,mmax+1):
    antal=0
    antal_primiske=0
    for a in range(1,m):
        if math.gcd(a,m)==1:
            antal_primiske+=1
            if pow(a,m-1,m)==1:
                antal+=1
    print(m,antal_primiske,antal)

I pakken math, som vi importerer, ligger funktionen gcd, som beregner den største fælles divisor for to tal.

Jeg har brugt antal_primiske til at tælle de a‘er som er primiske med m.

Jeg har brugt antal til at tælle de a‘er som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \). Bemærk at antal kun forøges hvis a både er primiske med m og \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Eksempel på output af første resultater:

I hver række står der tre tal;

Første tal er værdien af m.
Andet tal er antallet af a‘er, fra a = 1, til a = m -1, der er primiske med m.
Tredie tal er antallet af de tal, der er primiske med m, som også opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Række 2: Når m = 2, så er der ét tal der er primisk med m; det er tallet 1. Og tallet 1 opfylder, at \(1^{2-1} \equiv 1 \textrm{ mod } 2 \). Derfor står der i række 2; “2 1 1”

\(1^{4-1} = 1^3 = 1 \equiv 1 \textrm{ mod } 4\)
\(3^{4-1} = 3^3 = 27 \equiv 3 \textrm{ mod } 4\)

Række 3: Når m = 3, så er der to tal som er primiske med m, og for begge de to tal gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \):

\(1^{3-1} = 1^2 = 1 \equiv 1 \textrm{ mod } 3\)
\(2^{3-1} = 2^2 = 4 \equiv 1 \textrm{ mod } 3\)

Række 4. Når m = 4, så er der to tal som er primisk med m. Det er tallene 1 og 3. Opfylder de at \(a^{m-1} \equiv 1 \textrm{ mod } m \) ?

\(1^{4-1} = 1^3 = 1 \equiv 1 \textrm{ mod } 4\)
\(3^{4-1} = 3^3 = 27 \equiv 3 \textrm{ mod } 4\)

Så det er kun tallet a = 1 der både er primisk med 4 og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Figur

Jeg har, for alle værdier af m fra m = 1 til m = 105, optalt antal a‘er der er primiske med m, og antal a‘er som både er primiske med m og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Jag har så divideret antal med antal_primiske, og omregnet til procent.

Figuren viser resultaterne:

De værdier af m hvor procenten er 100 er primtallene. Når m er et primtal, så vil alle værdier af a, fra a = 1 til a = m – 1, både være primiske med m og opfylde at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Man kan så omvendt spørge; findes der værdier af m, som ikke er primtal, hvor der for alle a‘er, som er primiske med m, også gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \) ?

Svaret er ‘ja’, der findes sammensatte tal m som opfylder, at der for alle a‘er primiske med m, gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Disse tal kaldes Carmichael-tal. Det mindste af disse tal er 561. Der er 320 tal fra a = 1 til a = 560 som er primiske med 561. For alle disse 320 værdier af a gælder der at \(a^{560} \equiv 1 \textrm{ mod } 561 \).

Tallet 561 er ikke et primtal; \(561 = 3 \cdot 11 \cdot 17\).

Hvis vi derfor vil teste om et tal m er et primtal, og kun kontrollerer for a‘er der er primiske med m, så kan vi komme ud for værdier af m hvor alle a‘er opfylder ligningen \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Figuren viser situationen.