ggT der beiden Zahlen a =7 077807420049 und b =4 080705260976. Schranke für Anzahl euklidische Divisionen?

Question

Aufgabe 5 Sie mochten den ggT der beiden Zahlen
a =7 077807420049 und b =4 080705260976
bestimmen. Geben Sie eine obere Schranke fur die Anzahl der euklidischen Divisionen an.

Answer 1

Eine Abschätzung der Iterationsschritte findest du unter

http://www.staff.uni-mainz.de/pommeren/Kryptologie/Klassisch/6a_Lin/euklana.pdf

Abschätzen kann man es also über

n < 0.718 + 4.785·LOG(7077807420049, 10) = 62.2

 

ggT bestimmen: a = 7077807420049 und b = 4080705260976

7077807420049 / 4080705260976 = 1 Rest 2997102159073 
4080705260976 / 2997102159073 = 1 Rest 1083603101903 
2997102159073 / 1083603101903 = 2 Rest 829895955267 
1083603101903 / 829895955267 = 1 Rest 253707146636 
829895955267 / 253707146636 = 3 Rest 68774515359 
253707146636 / 68774515359 = 3 Rest 47383600559 
68774515359 / 47383600559 = 1 Rest 21390914800 
47383600559 / 21390914800 = 2 Rest 4601770959 
21390914800 / 4601770959 = 4 Rest 2983830964 
4601770959 / 2983830964 = 1 Rest 1617939995 
2983830964 / 1617939995 = 1 Rest 1365890969 
1617939995 / 1365890969 = 1 Rest 252049026 
1365890969 / 252049026 = 5 Rest 105645839 
252049026 / 105645839 = 2 Rest 40757348 
105645839 / 40757348 = 2 Rest 24131143 
40757348 / 24131143 = 1 Rest 16626205 
24131143 / 16626205 = 1 Rest 7504938 
16626205 / 7504938 = 2 Rest 1616329 
7504938 / 1616329 = 4 Rest 1039622 
1616329 / 1039622 = 1 Rest 576707 
1039622 / 576707 = 1 Rest 462915 
576707 / 462915 = 1 Rest 113792 
462915 / 113792 = 4 Rest 7747 
113792 / 7747 = 14 Rest 5334 
7747 / 5334 = 1 Rest 2413 
5334 / 2413 = 2 Rest 508 
2413 / 508 = 4 Rest 381 
508 / 381 = 1 Rest 127 
381 / 127 = 3 Rest 0

Der ggT ist demnach 127