\mnb150<nb wrap="0" txtwidth="156" autowidth="1" pprint="1" typeset="1" xface="Times New Roman" xsize="240" xbold="0" xitalic="0" xcolor="#0000FF" slidents="1" sizemult="71" minsize="160" ifont="0 220 255 0 49 Courier New" ofont="0 220 16711680 0 49 Courier New" tfont="0 220 0 0 18 Times New Roman"></nb>ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\froman\fprq2 Times New Roman;}{\f4\fswiss\fprq2 Arial;}{\f5\fmodern\fprq1 Courier New;}{\f6\froman\fprq2\fcharset2 Symbol;}}
{\colortbl\red0\green0\blue0;\red255\green0\blue0;\red0\green0\blue255;\red0\green128\blue0;\red0\green255\blue0;}
\deflang1031\pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}reset():
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 unprotect(beta):
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// This gives the b-adic representation of x,
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 // starting with the least significent digit.
\par // numlib::g_adic( x, b );
\par a:=numlib::g_adic(654321,10);
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// number(L,b) performs the inverse.
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 number:=
\par proc(L,b)
\par   local i;
\par begin
\par   _plus( L[i] * b^(i-1) $ i=1..nops(L) );
\par end_proc:
\par number(a,10);
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// Fix a Sophie Germain prime p,
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 // ie. phi(p) has only two prime factors, namely 2 and one further:
\par q:=7541:
\par p:=2*q+1;
\par factor(numlib::phi(p));
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// We need two elements of Z_p^* :
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 alpha:=5573:
\par beta:=6904:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// Check whether both have order q in Z_p^\\times.
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 ////////////////
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// A short hash function.
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 h:=(a,b)->(powermod(alpha,a,p) * powermod(beta,b,p)) mod p;
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}/*
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 Soll \'fcbertragen werden zu einer Hackfunktion von Z_2^m nach Z_2^t.
\par Wir definieren dazu
\par  m so, da\'df Z_2^m --> Z_(p-1) x Z_(p-1) gerade noch surjektiv sein kann, und
\par  t so, da\'df Z_p^* --> Z_2^t gerade noch injektiv sein kann.
\par */
\par t:=nops( numlib::g_adic( p-1, 2) ):
\par m:=2* nops( numlib::g_adic( p-2, 2) ):
\par m,t;
\par // We use h to define a hash function Z_2^m to Z_2^t.
\par h0:= proc(x:DOM_LIST)
\par   //global m,t;
\par   local L,i,j;
\par begin
\par   if nops(x)<>m then
\par     error("Eingabel\'e4nge falsch! (Sollte ". m ." sein.)");
\par   end_if;
\par   i := number( x[1..m/2], 2);
\par   j := number( x[m/2+1..m], 2);
\par   h( i, j );
\par   L:=numlib::g_adic( %, 2);
\par   if nops(L)<t then L:=[op(L),0$t-nops(L)]; end_if;
\par   eval(L);
\par end_proc:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}[0$m];
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 h0(%);
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// From it we construct a long hash function:
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 H:= proc(x)
\par   //global m,t;
\par   local i,d,d_binaer,L,actualh,flag,g;
\par begin
\par   d:=(-nops(x)) mod (m-t-1);
\par   d_binary:= numlib::g_adic(2^(m-t-1)+d, 2)[1..m-t-1];
\par   // filled with zeroes
\par   L := [op(eval(x)),0$d, op(d_binary) ];
\par   userinfo(2,"L   = ".expr2text(L));
\par   actualh := [0$t]; flag := 0;
\par   while nops(L)>0 do
\par     g := [ op(actualh), flag, op( L[1..m-t] ) ];
\par     L := L[m-t..nops(L)];
\par     actualh := h0(g);
\par     userinfo(2,"g   = ".expr2text(g));
\par     flag:=1;
\par   end_while;
\par   userinfo(2,"h^* = " . expr2text(actualh) );
\par   number(actualh, 2);
\par end_proc:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// Test:
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 setuserinfo( H, 2 ):
\par H([0$100]);
\par H([0$99]);
\par setuserinfo( H, 0 ):
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// Schutz vor unbeabsichtigter Ver\'e4nderung:
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 protect(t,ProtectLevelError):
\par protect(m,ProtectLevelError):
\par protect(h,ProtectLevelError):
\par protect(h1,ProtectLevelError):
\par protect(H,ProtectLevelError):
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}// Einige Nachrichten:
\par \pard\li600\ri1\fi-300\plain\f5\fs22\cf1 Nachricht1 := [1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]:
\par Nachricht2 := [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]:
\par Nachricht3 := [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]:
\par Nachricht4 := [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]:
\par Nachricht5 := [1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0]:
\par Nachricht6 := [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1]:
\par Nachricht7 := [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0]:
\par Nachricht8 := [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]:
\par Nachricht9 := [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]:
\par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f5\fs22\cf1 {\pntext\f1\'b7\tab}
\par }