{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "restart:\nwith(numth eory):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 0 21 "convert( x, base, b )" } {TEXT -1 13 " liefert die " }{TEXT 0 1 "b" }{TEXT -1 90 "-adische Dars tellung von x,\ndas Ergebnis ist eine Liste, die mit der Einerziffer b eginnt.\n" }{TEXT 0 23 "convert( L, base, c, b)" }{TEXT -1 32 " wandel t eine c-adische in eine " }{TEXT 0 1 "b" }{TEXT -1 24 "-adische Darst ellung um." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "convert(654321,base,1 0);\nconvert( \", base, 10, 17);" }}{PARA 0 "" 0 "" {TEXT -1 93 "numbe r(L,p) macht es umgekehrt: eine p-adische Darstellung wird in eine Zah l zur\374ckgerechnet." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "number:=\n proc(L,b)\n local i;\n add( L[i] * b^(i-1), i=1..nops(L) );\nend:" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "number(\"\",17);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "Definiere eine Sophie-Germain-Primzahl " } {TEXT 0 1 "p" }{TEXT -1 6 " (dh. " }{TEXT 0 6 "phi(p)" }{TEXT -1 36 " \+ hat nur zwei Primfaktoren, n\344mlich " }{TEXT 0 1 "2" }{TEXT -1 21 " \+ und einen weiteren):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "q:=7541:\np :=2*q+1;\nifactor(phi(p));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Wir brauchen zwei Generatoren von Z_p^*:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "alpha:=14736:\nbeta:=7965:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "\334berpr\374fe, ob beide Generatoren sind." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Eine kleine H ackfunktion." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "h:=(a,b)->(alpha&^a * beta&^b) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 221 "Soll \374b ertragen werden zu einer Hackfunktion von Z_2^m nach Z_2^t.\nWir defin ieren dazu\n m so, da\337 Z_2^m --> Z_(p-1) x Z_(p-1) gerade noch surj ektiv sein kann, und\n t so, da\337 Z_p^* --> Z_2^t gerade noch injekt iv sein kann." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "t:=nops( convert( \+ p-1, base, 2) );\nm:=2* nops( convert( p-2, base, 2) );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 0 21 "convert( x, base, b )" }{TEXT -1 13 " lief ert die " }{TEXT 0 1 "b" }{TEXT -1 90 "-adische Darstellung von x,\nda s Ergebnis ist eine Liste, die mit der Einerziffer beginnt.\n" }{TEXT 0 23 "convert( L, base, c, b)" }{TEXT -1 32 " wandelt eine c-adische i n eine " }{TEXT 0 1 "b" }{TEXT -1 24 "-adische Darstellung um." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "convert(654321,base,10);\nconvert( \+ \", base, 10, 17);" }}{PARA 0 "" 0 "" {TEXT 0 11 "number(L,b)" }{TEXT -1 26 " macht es umgekehrt: eine " }{TEXT 0 1 "b" }{TEXT -1 55 "-adisc he Darstellung wird in eine Zahl zur\374ckgerechnet." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "number:=\nproc(L,b)\n local i;\n add( L[i] * b ^(i-1), i=1..nops(L) );\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "nu mber(\"\",17);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Jetzt verwenden wir " }{TEXT 0 1 "h" }{TEXT -1 54 ", um eine Hackfunktion Z_2^m nach \+ Z_2^t zu definieren." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 293 "h1:= proc( x::list)\n global m,t;\n local L,i,j;\n if nops(x)<>m then ERROR(`E ingabel\344nge falsch! (Sollte `. m .` sein.)`); fi;\n number( x[1..m /2], 2);\n number( x[m/2+1..m], 2);\n h(\"\",\");\n L:=convert( \", base, 2);\n if nops(L) " 0 "" {MPLTEXT 1 0 36 "un debug(h1):\n[seq(0,i=1..m)];\nh1(\");" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Daraus bauen wir (in etwa wie in der Vorlesung) eine lang e Hackfunktion:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 506 "H:= proc(x)\n \+ global m,t;\n local i,d,d_binaer,L,actualh,flag,g;\n d:=(-nops(x)) m od (m-t-1);\n d_binaer:= convert(2^(m-t-1)+d, base, 2)[1..-2]; # aufg efuellt mit Nullen!\n L:=[op(eval(x)),seq(0,i=1..d), op(d_binaer) ]; \n actualh:=[seq(0,i=1..t)]; flag:=0;\n while nops(L)>0 do\n g:=[ op(actualh), flag, op( L[1..m-t-1] ) ];\n L:=L[m-t..-1];\n actu alh:=h1(g);\n userinfo(2,H,`Zur Kontrolle: g = `,g);\n flag:=1 ;\n od;\n userinfo(2,H,`Zur Kontrolle: h^* = `, actualh);\n number( actualh, 2);\nend:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "Test:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "undebug(H):\ninfolevel[H]:=2:\nH([seq(0,i=1..100)]);\ninfolevel[H] :=0:\nH([seq(0,i=1..99)]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Sch utz vor unbeabsichtigter Ver\344nderung:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "protect('t','m',h,h1,H):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "Einige Nachrichten:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 2499 "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]:\nNachricht2 := [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]:\nNachricht3 := [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]:\nNachricht4 := [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]:\nNachri cht5 := [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]:\nNachricht6 := [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]:\nNachricht7 := [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]:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "14 0 0" 0 } {VIEWOPTS 1 1 0 1 1 1803 }