Fermats lilla sats

Jo det gäller för alla heltal a så länge p är ett primtal.

Hur ser matlab-koden ut som du använder dig av?

function [ b ] = testfermat( a,p )
%
a=17
p= 13

% Test Fermats lilla sats
b = (mod(a^p,p) == mod(a,p))
end

testade då a = 3,60 funkar men inte då a= 17 eller 25

Problemet är att det inte går att representera 17^13 tillräckligt exakt. För att beräkna det korrekt så använd denna funktion (om jag inte gjorde någon miss nu)

function m = powmod(a, p, n)
m = 1;
b = a;
while p > 0
if mod(p, 2) == 1
m = mod(m * b, n);
end
b = mod(b * b, n);
p = floor(p/2);
end
end

Denna beräknar $a^p mod n$, så för att beräkna $17^{13} mod 13$ så anropar man powmod(17, 13, 13).

förstår inte riktigt funktionen , vad är a,,n ,m 

Funktionen beräknar alltså $a^p\text{ mod n}$ så om du vill beräkna $6^{302}\text{ mod } 43$ så anropar du powmod(6, 302, 43).

m är variabeln som innehåller return värdet av funktionen.

Skulle du kunna förklara din funktion lite mer, tack! 

Alltså varför du gör som du gör!

Problemet som måste lösas är att försöka hålla talen tillräckligt små så att de kan representeras av datorn.

Så själva idén är att använda binär representationen för p

$p = \alpha_0 + 2\alpha_1 + 2^2\alpha_2 + \cdots + 2^m \alpha_m$

Så nu vet man att

$a^p \equiv a^{ \alpha_0}\cdot a^{2\alpha_1} \cdot a^{2^2\alpha_2}\cdots a^{2^m \alpha_m}\text{ (mod n)}$

Nu är det alltså bara att skriva en loop som beräknat $a^{2^k}$ och multiplicera in denna faktor ifall $\alpha_k$ är 1.