Kjempekult at du har laget en primtallkalkulator!
Som de ovenfor sier så finnes det masse smarte metoder for å bestemme om et tall
er primtall elle ei. Grunnen til at dette er interessant er at alle banker bruker store primtall
for å hemmligjøre transaksjonene banken gjør.
For å bestemme om ett tall er primtall eller ei, liker jeg veldig godt
Solovay-Strassen testen
http://planetmath.org/SolovayStrassenTest
Det behagelige er at en ikke må forstå all matematikken bak det.
Tanken er at å primtallsfaktorisere et tall tar lang tid. Så derfor
lar vi primtallet gå igjennom en algoritme eller sekvens.
Dersom algoritmen gir ut 1 er vi 100% sikker på at tallet ikke er primtall.
Dersom algoritmen gir ut 0 er sjangsen maksimalt 50% for at tallet ikke er primtall.
Består primtallet testen to ganger, er sjangsen maksimalt 25% for at tallet ikke er primtall.
Slik fortsetter det, lar vi primtallet gå igjennom testen 14 ganger er det 0.001% sannsynlighet for at
tallet ikke er primtall. Eller med andre ord 99% sikkert at tallet er primtall.
En mindre optimal kode jeg skrev for herrens år siden ser slik ut. Syntaxen er maple
så kan du titte litt på den, prøve å se hva som foregår, og kanskje implementere noe liknende
i java. Spytter koden ut $0$ så er vi sikker på at tallet er sammensatt / ikke primsk. Spytter
den ut $1$ er vi ikke sikker enda.
Code: Select all
% Her er n primtallet vi tester, og k er antall tester primtallet går igjennom.
% Sannsynligheten for at n er primtall dersom n består k tester er
% P = 1 - 1/2^k
function [ Y ] = solovay( n,k )
if mod(n,2)~=0
p = (n-1)/2;
for i = 1:k
a = randi(n-1);
if gcd(a,n)~=1
Y = 0;
return
end
jacobi = jacobi(a,n);
mod = powermod(a, p, n);
if jacobi<0
jacobi = jacobi + n;
end
if mod ~= jacobi
Y = 0;
return
end
end
Y = 1;
else
Y = 0;
end
Men da jeg prøvde det, ble resultat slik, f.eks. ved tallet 10: