Der größte gemeinsame Teiler (GGT) wird in der Informatik oft für Verschlüsselungen und anderen Anwendungen verwendet. Ein Beispiel wäre der RSA-Verschlüsselungsalgorithmus.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/** * Code zur Berechnung des größten gemeinsamen Teilers zweier Zahlen * @author ST-Page.de * */ public class GGT { /** * Der größte gemeinsame Teiler wird hier berechnet. Die Laufzeit entspricht * maximal der größten Zahl. * * @param a * Erste Zahl * @param b * Zweite Zahl * @return Größter gemeinsame Teiler */ public static int ggt(int a, int b) { // Hier versuche ich Arbeitsaufwand (Rechnenzeit) zu sparen in dem ich // mir die kleinste Zahl suche. int h = (a > b) ? b : a; // Der GGT wird hier berechnet. for (int i = h; i > 1; i--) { if ((a % i) == 0 && (b % i) == 0) { return i; } } // teilerfremde Zahlen haben immer den Teiler 1 return 1; } /** * @param args */ public static void main(String[] args) { System.out.println("GGT von 1024 und 256 => " + GGT.ggt(1024, 256) +"."); } } |
Java GGT
In dem Snippet wird der größte gemeinsame Teiler von zwei Zahlen, mittels der Modulo-Rechnung ermittelt. Die Methode ggt(int a, int b) ermittelt als erstes die kleinste Zahl, damit der Rechenaufwand nicht alzu hoch wird. So bald wie der größte gemeinsame Teiler gefunden wurde, wird dieser zurückgegeben. Sollte es keinen größten gemeinsamen Teiler geben, so ist immer der Teiler gleich 1.
Das Snippet arbeitet nur mit Integer-Werten. Innerhalb der For-Schleife wird solange runtergezählt bis ein größter gemeinsamer Teiler gefunden wurde. Hierbei wird die Modulo-Rechnung verwendet. Wenn die beiden Zahlen sich durch i ohne Rest teilen lassen, dann ist i der größte gemeinsame Teiler.
Anwendungsbeispiel
Mit dem größtem gemeinsamen Teiler können Elemente von Verschlüsselungsalgorithmen berechnet werden, zum Beispiel wie beim RSA.