Demo priemtesten

Initialisatie

mod[x_,k_,m_]:=PowerMod[x,k,m]

rep[n_]:=(10^n-1)/9

randominteger[n_]:=RandomInteger[{(10^(n-1)),(10^n)}]

randomprime[n_]:=NextPrime[randominteger[n]]

rabin[n_,a_]:=Module[{m=n-1,k=0,r,power},
If[EvenQ[n],Print[n," is even"];Return[]];
While[EvenQ[m],m=m/2;k++];
power=mod[a,m,n];
If[power==1,Print["No conclusion"];Return[]];
For[r=0,r<k,r++,If[power==n-1,Print["No conclusion"];Return[]]];
Print[n," is composite"];
Return[]
]

Voorbeelden

We introduceren twee manieren om snel grote getallen te maken. Allereerst het commando rep[n] om een rep-unit van n enen te maken.

rep[23]

Het tweede commando is randominteger[n] dat een random getal van n cijfers maakt.

K=randominteger[50]

Een derde commando randomprime[n] maakt  een priemgetal van n cijfers.

K=randomprime[50]

Controle van Fermat.

mod[12345,K,K]

Maak een groot getal aan en kijk of het de zogenaamde Fermat priemtest passeert.

K=rep[71]

mod[5,K,K]

Probeer ook eens wat random getallen van 20 cijfers

K=randominteger[20]

mod[3,K,K]

Hier is een Carmichaelgetal

L=727993807201

mod[117,L,L]

FactorInteger[L]

rabin[L,3]

K=randomprime[50]

mod[123456789,K,K]

Er is ook een ontbindingsopdracht, maar die werkt tot getallen van 50 cijfers

FactorInteger[rep[71]]