showtime: true;

Programmiertechniken

f(x):= if x > 0 then "positiv" else 
"nichtpositiv";

f(2);

f(-3);

f(0);

f(x);

x: 1$
for k: 1 thru 100 do
  x: k*x$
x;

Fak1(n):=block([x,k],
  x: 1,
  for k: 1 thru n do
    x: k*x,
  x
)$

Fak1(100);

Fak1(100000)-100000!;

L: makelist(k,k,1,100);

apply("*", L);

Fak2(n):=block([l],
  l: makelist(k, k, 1, 100),
  product(l[i],i,1,100)
)$

Fak2(100);

product(k,k,1,100);

Fak3(n):=product(k,k,1,100)$

Fak3(100);

100!;

Fak4(n):=if n = 0 then 1 else n*Fak4(n-1)$

Fak4(100);

Fak4(n):=if n = 0 then 1 else if integerp(n) and n > 0 then n*Fak4(n-1)$

Fak4(100);

Fak4(n):=if n = 0 then 1 else if integerp(n) and n > 0 then block(
  backtrace(), 
  n*Fak4(n-1)
)$

Fak4(5);

Fibionaccizahlen

showtime: true;

Fib1(n):=if n = 0 then 0 else if n = 1 then 1 else Fib1(n-1) + Fib1(n-2)$

Fib1(10);

Fib1(30);

Fib2[0]: 0; Fib2[1]: 1; Fib2[n] := Fib2[n-1] + Fib2[n-2];

Fib2[30];

res1: Fib2[1000];

res2: fib(1000);

res2-res1;

fib(1000000)$

Modulare Potenzen iterativ

Ziffern(n,b):=block([x,l],
    x:n,
    l:[],
    while x>0 do
      (l: append(l,[mod(x,b)]),
      x: part(divide(x,b),1)
    ),
    l
 );

Ziffern(n,b):=block([z,zahl],
if n<b then [n] else
(z:mod(n,b),
zahl:part(divide(n,b),1),
append(Ziffern(zahl,b),[z]))  
)$

z: Ziffern(1523,10);

reverse(liste):=block([],
    if length(liste)=1 then liste else 
    append(reverse(rest(liste)),[liste[1]])
)$

iterativepowermod(a,n,p):=block([digits,result,power,k],
    digits: reverse(Ziffern(n,2)),
    result: 1,
    power: a,
    for k:1 thru length(digits) do
      (
        if part(digits,k)=1 then
     (
            result: mod(result*power,p),
            power: mod(power^2,p)
          )
        else power: mod(power^2,p)
       ), 
     result
 )$

iterativepowermod(2,3,5);

power_mod(2,3,5);

a: random(10^100);

n: random(10^100);

p: random(10^100);

showtime: true;

res1: power_mod(a,n,p);

res2: iterativepowermod(a,n,p);

res1-res2;

Kleiner Satz von Fermat

power_mod(a,p-1,p);

p:next_prime(p);

power_mod(a,p-1,p);

power_mod(a,p,p)-a;

Reed-Solomon-Code

Digitalisiere(wort):=map(lambda([u], cint(u)-64), makelist(substring(wort,k,k+1),k,1,slength(wort)))$

liste: Digitalisiere("WORT");

Verbalisiere(liste):=apply(concat,map(lambda([u], ascii(u+64)), liste))$

Verbalisiere(liste);

a: [x,y,23,15,18,20];

mod(sum((k-1)*a[k],k,1,6),31);

y: mod(-263,31);

mod(sum(a[k],k,1,6),31);

x: mod(-y-76,31);

ReedSolomon(wort, p):=block([liste,n,a0,a1,k,sol],
  liste: Digitalisiere(wort),
  n: length(liste),
  a1: mod(-sum((k+1)*liste[k],k,1,n),p),
  a0: mod(-a1-sum(liste[k],k,1,n),p),
  liste: append([a0], append([a1],liste)),
  Verbalisiere(liste)
)$

ReedSolomon("WORT",31);

wort: "APWIRT";

liste: Digitalisiere(wort);

e: mod(apply("+",liste),31);

s: mod(sum((k-1)*liste[k],k,1,6),31);

x: mod(s*power_mod(e,-1,31),31);

liste[x+1]: mod(liste[x+1]-e,31);

Verbalisiere(liste);

InverseReedSolomon(wort,p):=block([liste,n,e,s,x,k],
  liste: Digitalisiere(wort),
  n: length(liste), 
  e: mod(apply("+",liste),p),
  s: mod(sum((k-1)*liste[k],k,1,n),p),
  x: mod(s*power_mod(e,-1,p),p),
  liste[x+1]: mod(liste[x+1]-e,p),
  liste: rest(rest(liste)), 
  Verbalisiere(liste)
)$

InverseReedSolomon("APWIRT",31);

code: ReedSolomon("MATHEMATIK", 31);

code: ssubst("S","H",code);

InverseReedSolomon(code,31);

code: ssubst("J","K",code);

InverseReedSolomon(code,31);

w: sum(binomial(6,k)*0.002^k*0.998^(6-k),k,2,6);

w*1.5*10^6;

w: sum(binomial(12,k)*0.002^k*0.998^(12-k),k,3,12);

w*1.5*10^6;

RSA-Verfahren

ListToNumber(liste):=block([l],
  l: length(liste),
  if l = 1 then
    liste[1]
  else
    1000*ListToNumber(reverse(rest(reverse(liste))))+liste[l] 
)$

TextToNumber(string):=block([],
  ListToNumber(map(lambda([u], cint(u)), makelist(substring(string,k,k+1),k,1,slength(string))))
)$

NumberToList(zahl):=block([],
  if zahl < 1000 then
    [zahl]
  else 
    append(NumberToList((zahl-mod(zahl,1000))/1000),[mod(zahl,1000)])
)$

NumberToText(zahl):=apply(concat, map(lambda([u], ascii(u)), NumberToList(zahl)))$

Verschluessele(nachricht):=power_mod(TextToNumber(nachricht),e,n)$

Entschluessele(zahl):=NumberToText(power_mod(zahl,d,n))$

InitialisiereRSA():=block([],
  p: next_prime(floor(random(1.0)*10^100)),
  q: next_prime(floor(random(1.0)*10^100)),
  n: p*q,
  phi: (p-1)*(q-1),
  e: phi,
  while gcd(phi,e) # 1 do (
    e: next_prime(floor(random(1.0)*10^50))
  ),
  d: power_mod(e,-1,phi),
  return() 
)$

InitialisiereRSA();

[e,n];

nachricht: "Dies ist meine Nachricht";

resultat: Verschluessele(nachricht);

Entschluessele(resultat);

Entschluessele(resultat+1);

resultat: Verschluessele("Wie ist es mit dieser Meldung?");

Entschluessele(resultat);