# Powermod

Für die Kryptografie ist es wichtig, dass hohe Potenzen 
riesiger Zahlen berechnet werden können.

/*Definition von pmod(a.k.m) powermod*/
pmod(a,k,m):=block([x,i,pot],
    i:k, x:1,pot:a,
    marke,
    if mod(i,2)=1 then (x:mod(x*pot,m),
        if i=1 then return(x),
        i:i-1    
    ),
    i:i/2,
    pot:mod(pot*pot,m),
    go(marke)
)$

pmod(5,3,16);mod(5^3,16);

pmod(12345,34567,16);mod(12345^34567,16);

Die letzte Rechnung könnte man mit einem gewöhnlichen Taschenrechner 
nicht ausführen. In der Kryptografie haben die Zahlen aber etwa 
200 Stellen und nicht 5 wie oben. Dann geht der rechte Befehl auch nicht mehr.

primlistebis(n):=([i,li],li:[],for i from 1  thru n do if  primep(i) then li:append(li,[i]),li);

lll:primlistebis(5000);

primep(250348280129);

makelist(pmod(99,p-1,p),p, primlistebis(5000));

mod(99^4998,4999);