In der Kryptografie ist die Berechnung des [url=https://www.inf.hs-flensburg.de/lang/algorithmen/grundlagen/zahlenth.htm]größten gemeinsamen Teilers[/url] (ggt) eine häufige Aufgabe. [br]Der [url=https://www.inf.hs-flensburg.de/lang/krypto/algo/euklid.htm]euklidische Algorithmus[/url][br]löst diese Aufgabe effizient, allerdings erfordert er die Berechnung der mod-Funktion, also im Prinzip eine Division mit Rest. Mit dem steinschen Algorithmus [Stein 67] lässt sich der größte gemeinsame Teiler ohne Divisionen berechnen. Der steinsche Algorithmus benutzt lediglich Division durch 2; diese lässt sich durch eine Schiebeoperation (js: <<) effizient realisieren.[br][br][color=#666666][size=85]https://www.inf.hs-flensburg.de/lang/krypto/algo/ggt-stein-algorithmus.htm[/size][/color][br][br]Klick Textblock to run the described code (js)[br]CAS Iteration steps controlled by slider n [br]GCD - ggb function call[br][br][color=#ff0000]Für die Berechnung im CAS muss n angepasst/eingestellt werden, der Euklidische Algorithmus in Zeile (2) [br]dargestellt durch Igcd muss in der 2.Spalte mit einer 0 abschließen![/color]
(Lemma von Bézout)[br]Seien a, b [img]https://www.inf.hs-flensburg.de/lang/symbols/elem.gif[/img] [img]https://www.inf.hs-flensburg.de/lang/symbols/zn.gif[/img][sub]0[/sub]. [br]Der größte gemeinsame Teiler ggt(a, b) lässt sich als ganzzahlige Linearkombination von a und b darstellen:[br][br]ggt(a, b) = u·a + v·b mit u, v [img]https://www.inf.hs-flensburg.de/lang/symbols/elem.gif[/img] [img]https://www.inf.hs-flensburg.de/lang/symbols/zz.gif[/img] [br][br]Die Darstellung ist nicht eindeutig; die Gleichung wird durch verschiedene Zahlenpaare u, v erfüllt.[br][br]Der erweiterte euklidische Algorithmus berechnet zusätzlich noch eine Darstellung von ggt(a, b) als ganzzahlige Linearkombination von a und b.[br]Er berechnet den größten gemeinsamen Teiler g zweier Zahlen a und b und zusätzlich die Koeffizienten u und v einer Darstellung von g als ganzzahlige Linearkombination.[br][br]Recursion[br][size=85]function extgcd(a, b) {[br] if (b == 0) {[br] return [a, 1, 0][br] } else {[br] guv = extgcd(b, a % b);[br] return [guv[0], guv[2], guv[1] - parseInt(a / b) * guv[2]][br] }[br]}[/size][br]Iteration[br][code][/code][size=85]function extgcd(a, b) {[br] a,b, u = 1; v = 0; s = 0; t = 1;[br] do {[br] q = parseInt(a / b);[br] tmp = b; b = a - q * b; a = tmp;[br] tmp = s; s = u - q * s; u = tmp;[br] tmp = t; t = v - q * t; v = tmp;[br] } while (b != 0)[br] return [a, u, v][br]};[br][/size][br][i]ab = extgcd(99, 78);[/i][br][math]\Longrightarrow[/math][3,-11,14][br]CAS (2) per Iterationlist (a,b,u,v,s,t): [br][math]\small ExI \, := \, \left(\begin{array}{rrrrrr}99&78&1&0&0&1\\78&21&0&1&1&-1\\21&15&1&-1&-3&4\\15&6&-3&4&4&-5\\6&3&4&-5&-11&14\\3&0&-11&14&26&-33\\\end{array}\right)[/math][br]n einstellen, so das Divisor 2.Spalte 0 wird!
Der letzte Rest im Euklidschen Algorithmus ist 3, der ggT von 99 und 78![br]Sukzessive rückwärts eingesetzen, um 3 (den ggT von 99 und 78) als Linearkombination dieser beiden Zahlen darzustellen[br]I(XX,j):=Element(XX, j) √[br]Extggt:=IterationList({ I(X,2), I(X,1)-floor(I(X,1)/I(X,2)) I(X,2) , I(X,5), I(X,6), I(X,3)-floor(I(X,1)/I(X,2))*I(X,5), I(X,4)-floor(I(X,1)/I(X,2))*I(X,6) } ,X, {{a,b,1,0,0,1}}, n)
A2=99, B=78[br]↓ Vorwärts-Algorithmus über [br]a' b' q r [br]endet in Zeile 6 → (D6=0)[br]↑Rück-Substitution x' y' → E6=0, F6=1 [br] r y'₁ x'₁[br]D5=3, F2=14, E2=-11 [br]→ 3 = -11*99+14*78[br]-----[br]Extgcd(3627,533)[br]D4(r)=13, F2(y')=-34, E2(x')=5
Einstellen der Iterationsschritte für Igcd, ExtIgdc
[i][url=https://www.inf.hs-flensburg.de/lang/krypto/index.htm]Kryptografie (H.W. Lang Hochschule Flensburg[/url]) [br][url=https://www.arndt-bruenner.de/mathe/scripts/chinesischerRestsatz.htm]https://www.arndt-bruenner.de/mathe/scripts/chinesischerRestsatz.htm[/url][br][/i][br]CAS [br](3) aMODb:={1,7,5,8,4,9}[br]x ≡ 1 mod 7[br]x ≡ 5 mod 8[br]x ≡ 4 mod 9[br][size=85]chineseRemainder([7,8,9], [1,5,4])[/size][br]==>[ChinRest][br]x ≡ 85 mod 504[br][br][ChinRest][br][size=85]function chineseRemainder(nn, rr) {[br] if (nn.length == 1) {[br] return [nn[0], rr[0]][br] } else {[br] var k = parseInt(nn.length / 2);[br] var ma = chineseRemainder(nn.slice(0, k), rr.slice(0, k));[br] var nb = chineseRemainder(nn.slice(k), rr.slice(k));[br] var guv = extgcd(ma[0], nb[0]);[br] var x = (nb[1] - ma[1]) * guv[1] % nb[0] * ma[0] + ma[1];[br] return [ma[0] * nb[0], x][br] }[br]};[br][br][size=100][ a x mod n = 1][/size][br]function modinv(a, n) {[br] guv = extgcd(a, n);[br] var x = guv[1] % n;[br] if (x < 0) x += n;[br] return x;[br]};[br][br][size=100]CAS step wise [br][/size][br]aMODb:={2,3,3,4,1,5 } ===> res mod num[br][i][size=85][i]res:=Sequence(aMODb( j),j,1,Length(aMODb),2)[/i][br]>{2,3,1}[/size][br]num: Sequence(aMODb(j),j,2,Length(aMODb),2)[/i][br]>{3,4,5}[br][i]prod: Product(num)[/i][br]>prod:=60[br][i]pp:Sequence(1/ num( j),j,1,Length(num)) prod[/i][br]>pp:={20,15,12}[br][i]inv: Flatten(Sequence( Sequence(j (Mod(j*pp(i),num(i))==1),j,0,num(i) -1)\{0} ,i,1,Length(num)))[/i][br]>inv:={2,3,3}[br][/size][br] A naive solution to find minimum x is the solution based on formula[br][math]xres \, := \, Mod \left(\sum_{i=1}^{Length \left(num \right)}res\left(i \right) \; pp\left(i \right) \; inv\left(i \right),prod \right)[/math][br][size=85]res: remainder, num: modulo, pp: prod/num(i), [br]inv - moduloinverse x: pp(i)*x mod num(i) = 1 (brutforce test over all mods either way v return of extgcd, v [size=85]factor of a, [size=85]v mod n[/size] [/size])[/size] [br][br][size=85][i]xres:= Mod(Sum(res(i)*pp(i)*inv(i) ,i,1,Length(num)) , prod)[/i][br]>xres:=11[br][/size][math] \left\{ x = 11 \;mod \, 60 \right\} [/math][br][br][i][size=85]Sequence({xres = res(j),mod,num(j)},j,1,Length(num))[/size][/i][br][math] \left\{ 11 = 2 \, mod \, 3 , 11 = 3 \, mod \, 4 , 11 = 1\, mod\, 5 \right\} [/math][br][br]https://www.youtube.com/watch?v=S_Dfw7J9EBE
