> restart:
> with(numtheory):
# convert( x, base, b ) liefert die b-adische Darstellung von x,
# das Ergebnis ist eine Liste, die mit der Einerziffer beginnt.
# convert( L, base, c, b) wandelt eine c-adische in eine b-adische
# Darstellung um.
> convert(654321,base,10);
> convert( %, base, 10, 17);
# number(L,p) macht es umgekehrt: eine p-adische Darstellung wird in
# eine Zahl zurückgerechnet.
> number:=
> proc(L,b)
>   local i;
>   add( L[i] * b^(i-1), i=1..nops(L) );
> end:
> number(%%,17);
# Definiere eine Sophie-Germain-Primzahl p (dh. phi(p) hat nur zwei
# Primfaktoren, nämlich 2 und einen weiteren):
> q:=7541:
> p:=2*q+1;
> ifactor(phi(p));
# Wir brauchen zwei Generatoren von Z_p^*:
> alpha:=14736:
> beta:=7965:
# Überprüfe, ob beide Generatoren sind.
> 
# Eine kleine Hackfunktion.
> h:=(a,b)->(alpha&^a * beta&^b) mod p;
# Soll übertragen werden zu einer Hackfunktion von Z_2^m nach Z_2^t.
# Wir definieren dazu
#  m so, daß Z_2^m --> Z_(p-1) x Z_(p-1) gerade noch surjektiv sein
# kann, und
#  t so, daß Z_p^* --> Z_2^t gerade noch injektiv sein kann.
> t:=nops( convert( p-1, base, 2) );
> m:=2* nops( convert( p-2, base, 2) );
# convert( x, base, b ) liefert die b-adische Darstellung von x,
# das Ergebnis ist eine Liste, die mit der Einerziffer beginnt.
# convert( L, base, c, b) wandelt eine c-adische in eine b-adische
# Darstellung um.
> convert(654321,base,10);
> convert( %, base, 10, 17);
# number(L,b) macht es umgekehrt: eine b-adische Darstellung wird in
# eine Zahl zurückgerechnet.
> number:=
> proc(L,b)
>   local i;
>   add( L[i] * b^(i-1), i=1..nops(L) );
> end:
> number(%%,17);
# Jetzt verwenden wir h, um eine Hackfunktion Z_2^m nach Z_2^t zu
# definieren.
> h1:= proc(x::list)
>   global m,t;
>   local L,i,j;
>   if nops(x)<>m then ERROR("Eingabelänge falsch! (Sollte ". m ."
> sein.)"); fi;
>   number( x[1..m/2], 2);
>   number( x[m/2+1..m], 2);
>   h(%%,%);
>   L:=convert( %, base, 2);
>   if nops(L)<t then t-nops(L); L:=[op(L),seq(0,i=1..%)]; fi;
>   eval(L);
> end:
> undebug(h1):
> [seq(0,i=1..m)];
> h1(%);
# Daraus bauen wir (in etwa wie in der Vorlesung) eine lange
# Hackfunktion:
> H:= proc(x)
>   global m,t;
>   local i,d,d_binaer,L,actualh,flag,g;
>   d:=(-nops(x)) mod (m-t-1);
>   d_binaer:= convert(2^(m-t-1)+d, base, 2)[1..-2]; # aufgefuellt mit
> Nullen!
>   L:=[op(eval(x)),seq(0,i=1..d), op(d_binaer) ];
>   actualh:=[seq(0,i=1..t)]; flag:=0;
>   while nops(L)>0 do
>     g:=[ op(actualh), flag, op( L[1..m-t-1] ) ];
>     L:=L[m-t..-1];
>     actualh:=h1(g);
>     userinfo(2,H,"Zur Kontrolle: g   = ",g);
>     flag:=1;
>   od;
>   userinfo(2,H,"Zur Kontrolle: h^* = ", actualh);
>   number(actualh, 2);
> end:
# Test:
> undebug(H):
> infolevel[H]:=2:
> H([seq(0,i=1..100)]);
> infolevel[H]:=0:
> H([seq(0,i=1..99)]);
# Schutz vor unbeabsichtigter Veränderung:
> protect('t','m',h,h1,H):
# Einige Nachrichten:
> Nachricht1 := [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0,
> 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0,
> 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0,
> 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0,
> 0, 1, 1, 1]:
> Nachricht2 := [0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0,
> 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
> 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
> 1]:
> Nachricht3 := [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1,
> 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0,
> 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0,
> 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1,
> 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1,
> 1, 0, 0, 1, 1, 0, 1, 1, 0]:
> Nachricht4 := [1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
> 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0,
> 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
> 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1,
> 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
> 1, 0, 0, 1, 0, 0, 1, 1, 1]:
> Nachricht5 := [0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1,
> 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0,
> 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0,
> 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0,
> 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0,
> 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]:
> Nachricht6 := [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0,
> 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0,
> 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1,
> 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1,
> 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0,
> 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]:
> Nachricht7 := [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1,
> 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1,
> 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1,
> 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
> 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1]:
>