// --------------------------------------------------------------- /* n = 221 = 13 * 17 zusammengesetzt 121 in 221: 121 in 2 mod 13 121 in 6 mod 17 --> mit CRT 210 mod 221. Jacobi(2, 95) == +1 = (-1) * (-1), aber 2 kein Quadrat in 95, weil weder in 5 noch in 19 2 --> 193 3 5 7 11 13 ----------------------- 8*95 = 1 0 4 1 6 193 = 1 3 4 6 11 Da 3 kein Quadrat mod 5, und nur 0 dazu kommt, kann die Suche gleich abgeblasen werden */ import java.awt.Button; import java.awt.Label; import java.math.BigInteger; // Hier die Methoden für Krypto public class Wurzel_Thread extends Thread { private BigInteger q; private BigInteger n; private Label status; private Button knopf; // Feld einfach und vorquadriert // 40633 ist komplett durch folgende Primfaktoren überdeckt bis 17 (Produkt) private static final int primbasisMax = 100; // mehr Faktoren sollen nicht rein private static int anzP = 3; // (aktuelle) Anzahl Primfaktoren im Feld private static int prim100 [] = new int [primbasisMax]; private static int prim100_2 [] = new int [primbasisMax]; private static int primquad [][] = new int [primbasisMax] []; // für jedes p die Reste Jacobi % p private static final boolean modusErweitern = true; public static int anzahlPrim() { return anzP; } // für Filter an Oberfläche private static boolean DEBUG = false; private static boolean DEBUG2 = false; private static boolean DEBUG3 = true; // zeigt an, wenn Testzahl tatsächlich ber. wird private final static BigInteger ZWEI = BigInteger.valueOf(2); private final static BigInteger DREI = BigInteger.valueOf(3); private final static BigInteger SIEBEN = BigInteger.valueOf(7); private final static BigInteger MINUSEINS = BigInteger.valueOf(-1); public short laufStatus; // zum Unterbrechen/Beenden eines Thread: 0 = laufen, 1=unterbrechen, 2=abbrechen private long laufzeit, startzeit; // Versucht, eine Wurzel durch Zerlegen des Moduls n über einer Basis zu vereinfachen, ruft dann für // Teiler istWurzel() auf. Am Ende dann mit chines. Restesatz zusammensetzen. wichtig, wenn mit Filter gesucht wird ! // Ruft bei Zerlegungsmöglichkeiten des Moduls die Methode istWurzel auf // Probleme gibt es momentan, wenn n durch ein Quadrat teilbar ist public BigInteger istWurzelGesamt(BigInteger para) { // initiale Primbasis nehmen, die später ggf. erweitert wird prim100[0] = 3; prim100_2[0] = 9; anzP = 3; primbasis_fuellen(); // prim100 reste_fuellen(); // quadPrim // Felder maximal dimensionieren long wurz [] = new long[anzP]; // Wurzel für folgenden Teiler von n long mod [] = new long[anzP]; // Teiler von n int stelle = 0; BigInteger aktuell = n; System.out.println("Suche gesamt für " + para + " und " + n); // 1) möglichst n faktorisieren final int anzPFest = anzP; // weil anzP kann später vergrößert werden for (int i = 0; (i < anzPFest) && (!aktuell.equals(BigInteger.ONE)); ++i) { BigInteger lauf = BigInteger.valueOf(prim100[i]); BigInteger erg [] = aktuell.divideAndRemainder(lauf); boolean teilt = erg[1].equals(BigInteger.ZERO); BigInteger basis = null; if (teilt) { BigInteger rest = para.remainder(lauf); int rueck = jacobiSymbol(rest, lauf); if (rueck != +1) { System.out.println ("Wurzel nicht vorhanden"); return MINUSEINS; } if (erg[0].remainder(lauf).equals(BigInteger.ZERO)) { System.out.println ("n mit quadratischem Teiler: noch nicht programmiert"); return null; } basis = lauf; } else if (i == anzPFest-1) { basis = aktuell; // aktuell ist unteilb. Rest oder prim } else continue; // weder teilt noch Primbasis zu Ende BigInteger suche = istWurzel(para.remainder(basis), basis); if (suche == null) { System.out.println("Wurzel wurde nicht berechnet"); return null; } // sollte nicht vorkommen else if (suche == MINUSEINS) return null; else System.out.println (para + " --> " + suche + " in " + basis); // Erfolg // Um Überläufe möglichst zu vermeiden, hier noch Wurzel verkleinern, falls möglich if (suche.bitLength() == basis.bitLength()) suche = basis.subtract(suche); wurz[stelle] = suche.longValue(); mod[stelle] = lauf.longValue(); ++stelle; if (teilt) aktuell = erg[0]; } // 2) die Relationen zu n wieder zusammenführen, wenn mind. ein Teiler von n ermittelt if (stelle > 1) { System.out.println ("Anzahl Relationen: " + stelle); // Stelle jetzt == Anzahl Relationen for (int i = 0; i < stelle; ++i) System.out.println(wurz[i] + " und " + mod[i]); } // 3) mit CRT zusammenführen // Felder noch dimensionieren je nachdem, was angefallen ist (Ursprünglich Größe aller Primzahlen) long wurz2 [] = new long[stelle]; long mod2 [] = new long[stelle]; for (int i = 0; i < stelle; ++i) wurz2[i] = wurz[i]; for (int i = 0; i < stelle; ++i) mod2[i] = mod[i]; long wurzAgg[] = new long[(stelle > 1) ? (stelle-1) : 1]; long modAgg[] = new long[(stelle > 1) ? (stelle-1) : 1]; boolean moeglich = chinesischerSatz(wurz2, mod2, wurzAgg, modAgg, 0, n.shiftRight(3).longValue()); if (moeglich) { return BigInteger.valueOf(wurzAgg[wurzAgg.length-1]); } else { return null; } } // Versucht, eine Wurzel aus 2 verschiedenen Methoden zu berechnen // Bei Primzahlen ist dies einfach, vor allem bei 3 mod 4 private BigInteger istWurzel(BigInteger para, BigInteger wert) { if (para == null || para.equals(BigInteger.ZERO)) return para; if (wert == null || wert.equals(BigInteger.ZERO)) return n; if (para.compareTo(wert) >= 0) para = para.remainder(wert); // nur modulo betrachten // Test, ob Primzahl: wichtig, da ja ein eingegebenen Quadrat in der Zahl n zerlegt werden kann, // und Jacobi bei gesamt +1 in Teilbereichen auch -1 ergeben kann System.out.println("istWurzel mit " + para + " und " + wert); if (Wurzel_Thread.jacobiSymbol(para, wert) != +1) { System.out.println("Kein Quadrat"); return MINUSEINS; } // Bei Primzahlen hier Verkürzung if (wert.testBit(0) && wert.isProbablePrime(2)) { BigInteger erg = wurzelBeiPrim(para, wert); // bei Primzahlen besonders einfach if (erg != null) return erg; // mod prim ist Wurzelziehen leichter, aber nicht deterministisch } // 1) sorge dafür, dass para == 1 mod 8 ist, zähle Bit-Verschiebungen int weg; int faktor = 1; boolean sonderfall = (wert.bitLength() == wert.bitCount()); // n == 2^k - 1 while ((weg = para.getLowestSetBit()) != 0) { if (weg >= 2) { para = para.shiftRight(2); faktor <<= 1; } else { // para ist durch 2 teilbar, wenn n = 2^k - 1, dann ist hier Endlosschliefe möglich, // z.B. bei x^2 = 2 mod 15, hier ist dann immer 2, 32, 8, 2 ... if (sonderfall) { System.out.println ("Sonderfall 2^k - 1"); return null; } para = para.add(wert.shiftLeft(1)); } // System.out.println ("Para nun " + para); } // ist ungerade if (para.testBit(1)) { para = para.add(wert.shiftLeft(1)); } if (para.testBit(2)) { para = para.add(wert.shiftLeft(2)); } // ist jetzt 1 mod 8 System.out.println(" Suche normal für " + para + " und " + wert); // 2) Schmeisse noch die Quadrate raus (Vorbed.: para != 0) boolean verringert = false; for (int i = 0; i < anzP; /* s.u. */) { BigInteger tmp = BigInteger.valueOf(prim100_2[i]); BigInteger tmp2 [] = para.divideAndRemainder(tmp); if (tmp2[1].equals(BigInteger.ZERO)) { para = tmp2[0]; faktor = faktor * prim100[i]; verringert = true; // System.out.println (prim100[i] + " rausgeworfen"); } else { ++i; } } if (verringert) System.out.println(" ... für " + para + " und " + wert); if (para.equals(BigInteger.ONE)) return BigInteger.valueOf(faktor); // 3) erstelle Signatur zu Wert, und was dazu kommt (8 * n); jeweils die Quadrate der Reste, wegen 0-Behandlung if (DEBUG) System.out.print("Sig. Q: "); int [] signatur = reste_ermitteln(para); BigInteger dazuZahl = wert.shiftLeft(3); if (DEBUG) System.out.print("Sig. 8n: "); int [] dazu = reste_ermitteln(dazuZahl); BigInteger erg = null; erg = istWurzelVoll(para, wert /* f. Anzahl Schleifen */, dazuZahl, signatur, dazu); // Wenn was gefunden, dann noch mit ggf. vorhandenen Faktor erweitern if (erg == null) return erg; else return erg.multiply(BigInteger.valueOf(faktor)).remainder(n); } // Bei Primzahlen lassen sich Quadrate besonders gut errechnen - hier kein Primtest mehr gemacht, // dies ist also ungeprüfte Voraussetzung private BigInteger wurzelBeiPrim(BigInteger para, BigInteger wert) { System.out.println(" Suche prim für " + para + " und " + wert); BigInteger erg = null; if (wert.testBit(1)) { // 3 mod 4 BigInteger exp = wert.add(BigInteger.ONE).shiftRight(2); erg = para.modPow(exp, wert); } else { // 1 mod 4, hier schwerer BigInteger exp = wert.subtract(BigInteger.ONE); int weg = exp.getLowestSetBit(); exp = exp.shiftRight(weg); BigInteger tmp = para.modPow(exp, wert); if (tmp.equals(BigInteger.ONE)) { erg = para.modPow(exp.add(BigInteger.ONE).shiftRight(1), wert); } // Fall mit para^exp==-1 evt. noch leicht zu bewältigen else { // -1, oder sonst und Quadrierung ergibt -1, sofern n wirklich prim ist // System.out.println ("Potenz ergibt " + tmp + ": noch nicht programmiert"); return null; } } if (erg.modPow(ZWEI, n).equals(para)) { if (DEBUG) System.out.println ("Erg " + erg); return erg; } else { System.out.println ("Algorithmus für Primzahlen funktioniert nicht"); return null; } } // Durchsucht alle Kombinationen von 0 bis n/8. Wenn alle anhand der Primzahlen zu prüfenden // Bedingungen erfüllt sind, wird versucht, eine Wurzel zu ziehen, und im Erfolgsfall die // Methode mit diesem Wert verlassen. Bei Scheitern der Wurzelziehung wird die Primbasis/Signaturen angepasst private BigInteger istWurzelVoll(BigInteger para, BigInteger wert /*n*/, BigInteger dazuZahl, int [] signatur, int [] dazu) { // Vorbedingung: para == 1 mod 8 long lauf; // die Anzahl Versuche müssen ggf. in Abhängigkeit von n beschränkt werden long grenze = (wert.longValue() >> 3) + 1; // 33 in 95: max 11 mal addieren, also 12 mal testen; if (wert.bitLength() > 63) grenze = Long.MAX_VALUE; // Überlauf von long behandeln boolean treffer = false; if (DEBUG) System.out.println("Anzahl Versuche: " + grenze); for (lauf = 0; lauf < grenze; ++lauf) { if (laufStatus == 1) { unterbrechen(); // möglich, dass es weitergeht } // gleich prüfen, ob er ganz abbrechen soll if (laufStatus == 2) { System.out.println ("Thread ganz beenden"); return null; } // Abbrechen // wenn die Signatur alle Bedingungen erfüllt ... if (alleBedingungenErfuellt(signatur)) { // Signatur OK, teste, ob tatsächlich Quadrat in Z BigInteger tmp = para.add(dazuZahl.multiply(BigInteger.valueOf(lauf))); // korr. zu Feld signatur if (DEBUG3) { System.out.print ("Testzahl " + tmp+ "\t"); for (int j = 0; j < signatur.length; ++j) System.out.print((signatur[j] % prim100[j])+ " "); System.out.println(""); } BigInteger tmp_erg = holeWurzel(tmp, true); // != null, wenn Wurzel ganzzahlig in Z if (tmp_erg != null) { System.out.println ("Gefunden nach: " + (lauf + 1) ); System.out.println ("Erfolg bei Größe Primbasis " + anzP); return tmp_erg; } else if (modusErweitern) { // Primbasis-Größe und Signaturen nun vergrößern, bis eine Bed. fehlschlägt. Grundlage: // eine Quadratzahl in Z erfüllt alle Tests mod p. do { ++anzP; primbasis_fuellen(); // prim100 reste_fuellen(); // quadPrim signatur = reste_ermitteln (tmp /* wichtig nicht para! */); // muss wie bis. Sign, nur um einen Primf. erw. dazu = reste_ermitteln (dazuZahl); } while (alleBedingungenErfuellt(signatur)); // gibt es eine Chance weiterzumachen, also dazu[i]!= 0. Lohnt sich kaum, da dann neues p n teilen muss } } addiere_signatur(signatur, dazu); // nächsten Wert 1 mod 8 erzeugen } System.out.println ("Abbruch bei Größe Primbasis " + anzP); // Wenn hier angekommen, trotz Komplettsuche nichts gefunden return null; } /* ********************** private statische Hilfsmethoden ********************** */ // ergänzt das Feld mit den Resten (quadprim) private static void reste_fuellen() { for (int i = 0; i < anzP; ++i) { if (primquad[i] != null) continue; // schon drin primquad[i] = new int[(prim100[i] - 1) >> 1]; // mod p genau (p+1)/2 Reste, 0 nicht speichern final int bis = (prim100[i] >> 1); for (int j = 1; j <= bis; ++j) { int rest = (j * j) % prim100[i]; // Hier kann genutzt werden, dass Felder immer mit 0 init. werden, was hier nicht vorkommen kann //System.out.print(rest + ","); for (int k = 0; k < primquad[i].length; ++k) { if (primquad[i][k] == 0) { primquad[i][k] = rest; break; } } } } } // ergänzt die Primbasis private static void primbasis_fuellen() { for (int i = 0; i < anzP; ++i) { if (prim100[i] != 0) continue; // schon drin // Primzahl ist diejenige ungerade, die durch alle vorhergehende nicht geteilt wird int weiter = prim100[i-1]; do { weiter += 2; int j; for (j = 0; j < i; ++j) if ((weiter % prim100[j]) == 0) break; if (j == i) { prim100[i] = weiter; prim100_2[i] = weiter*weiter; break; } } while (true); } } // zerlegt eine Großzahl in ein Feld von Resten, welche dort zum Quadrat abgespeichert werden // die Speicherung als Quadrat ist wichtig, wegen der Sonderbehandlung 0 mod p^2 private static int [] reste_ermitteln(BigInteger zahl) { int [] rueck = new int[anzP]; // von 0 bis < ab soll numerisch 0 sein, dies ist schon so vorinitialisiert for (int i = 0; i < anzP; ++i) { rueck[i] = zahl.remainder(BigInteger.valueOf(prim100_2[i])).intValue(); if (DEBUG) System.out.print((rueck[i] % prim100[i])+" "); } if (DEBUG) System.out.println(""); return rueck; } // schaut zur Signatur (Reste mod p1^2) nach, ob alle Bedingungen erfüllt sind, dann wahr private static boolean alleBedingungenErfuellt(int signatur []) { for (int i = 0; i < anzP; ++i) { int rest = signatur[i]; // 1) Sonderfall, wenn einfach geteilt 0 ist- wenn nicht auch durch Quadrat davon, dann kein Quadrat if (rest == 0) continue; // durch Quadrat teilbar, in Ordnung rest = rest % prim100[i]; // mod p weiter if (rest == 0) return false; // kein Quadrat, da Primzahl nur einmal teilbar, nicht quadratisch // 2) schaue nach, ob in Resten > 0 drin ist int j; for (j = 0; j < primquad[i].length; ++j) { if (primquad[i][j] == rest) break; } if (j == primquad[i].length) return false; // nicht in Quadraten } // Ende for return true; // alle Tests bestanden } // Addiert zur signatur die Verschiebung, und macht noch ggf. Testausgaben // Anm.: Diese Methode wird laut hprof besonders häufig durchlaufen private static void addiere_signatur(int signatur[], int dazu[]) { for (int j = 0; j < anzP; ++j) { int modulo = prim100_2[j]; int siglok = signatur[j]; siglok += dazu[j]; if (siglok >= modulo) siglok -= modulo; signatur[j] = siglok; } if (DEBUG) { signatur_wahr_falsch_ausgeben (signatur); } } // Gibt aus, was zur Signatur ein Quadrat ist (1) oder nicht (0) private static void signatur_wahr_falsch_ausgeben (int signatur[]) { System.out.print("Sig: "); for (int j = 0; j < signatur.length; ++j) { if (signatur[j] == 0) { System.out.print("1"); continue; } // Sonderfall, wahr int suche = signatur[j] % prim100[j]; if (suche == 0) { System.out.print("0"); continue; } int k = 0; for (; k < primquad[j].length; ++k) { if (primquad[j][k] == suche) { break; } } System.out.print((k == primquad[j].length) ? "0" : "1"); } System.out.println(""); } /* **************** Methoden zur Steuerung des Frame ***************** */ // Konstruktor für Frame public Wurzel_Thread (BigInteger p_q, BigInteger p_n, Label p_status, Button p_knopf) { super(); q = p_q; n = p_n; status = p_status; knopf = p_knopf; laufStatus = 0; laufzeit = 0; } // Hauptmethode für Thread public void run() { startzeit = System.currentTimeMillis(); BigInteger rueck = istWurzelGesamt(q); laufzeit += (System.currentTimeMillis() - startzeit); // start- und laufzeit siehe Konstruktor if ((status != null) && (knopf != null)) { if (rueck == null) status.setText("Wurzel unbek. " + holeLaufzeit()); else if (!rueck.equals(MINUSEINS)) status.setText("w= " + rueck.toString() + holeLaufzeit()); else status.setText("Kein Quadrat"); knopf.setLabel("Berechnen"); } else { System.out.println ("Wurzel ist " + ( (rueck == null || rueck.equals(MINUSEINS)) ? "unbekannt" : rueck.toString()) + holeLaufzeit() ); } } // Thread fortsetzen // bei beiden Methode ist synchronized entscheidend, weil sonst ein Laufzeitfehler kommt(sowohl bei notify als auch wait): // Fehlermeldung: "current thread not owner" public synchronized void weitermachen(short neuerStatus) { // neuerStatus zwischen 0 und 2 laufStatus = neuerStatus; startzeit = System.currentTimeMillis(); this.notify(); } // Thread unterbrechen private synchronized void unterbrechen() { laufzeit += (System.currentTimeMillis() - startzeit); startzeit = 0; try { wait(); } catch (InterruptedException ex) {} // solange warten, bis wieder aufgeweckt } private String holeLaufzeit() { double sek = (laufzeit / 100) / 10.0; // 1 NK return "(Laufzeit: " + new Double(sek).toString() + " sek.)"; } // ******************************************* // statische Methoden ausserhalb des Kontextes // ******************************************* // berechnet Wurzel mit Heron-Verfahren. // wenn angegeben nurExakt, wird Wurzel nur bei exakter Gleichheit zurückgeliefert // x[n+1] = (x[n] + q/x[n]) / 2 private static BigInteger holeWurzel (BigInteger eingabe, boolean nurExakt) { // System.out.println ("Wurzel der " + eingabe); // Für Startwert bilde die obersten 2 Bit ab (auf die Hälfte des Exponenten) BigInteger wert = BigInteger.ONE; for (int i = eingabe.bitLength() -1, tmp = 0; (i >= 2) && (tmp < 2); --i) { if (eingabe.testBit(i) && !wert.testBit(i >> 1)) { wert = wert.setBit(i >> 1); ++tmp; } } BigInteger erg = null, vorgaenger = null; BigInteger rueck []; // Schleife durchlaufen. Divsision arbeitet ganzzahlig // bei 35: Hier Oszillation zwischen 6 --> 5 --> 6 ) ! while (true) { rueck = eingabe.divideAndRemainder(wert); if ((rueck[0].equals(wert)) && (rueck[1].equals(BigInteger.ZERO)) ) return wert; // exakt gefunden // nächsten Folgewert berechnen erg = rueck[0].add (wert); erg = erg.shiftRight(1); // System.out.println (erg.toString() ); // für Testzwecke, zum Sehen der Approximation if (erg.equals(wert)) return (nurExakt ? null : wert); // keine Veränderung mehr, aber Rest if (!nurExakt && (vorgaenger != null) && (erg.equals(vorgaenger))) { if (wert.compareTo(erg) < 0) return wert; else return erg; // immer das kleinere nehmen } vorgaenger = wert; wert = erg; } } // Ende Methode holeWurzel // Berechnet allgemein das Jacobi-Symbol - auch 2er im Nenner werden korrekt beachtet // Nicht geprüfte Vorannahme: a und n sind >= 0 public static int jacobiSymbol(BigInteger a, BigInteger n) { BigInteger zaehler = a; BigInteger nenner = n; int rest; int rueck = +1; // wenn a < 0 ? Bei n == 3 mod 4 Vorzeichen wechsel if (zaehler.compareTo(BigInteger.ZERO) < 0) { if (nenner.testBit(0) && nenner.testBit(1)) rueck = -1; // zu tun: wenn n gerade zaehler = zaehler.abs(); } if (zaehler.equals(BigInteger.ZERO) || nenner.equals(BigInteger.ZERO)) { return +1; } // Behandlung von 2ern im Nenner else if (!zaehler.testBit(0) && !nenner.testBit(0)) { return 2; // ggT != 1 } else if (nenner.and(SIEBEN).intValue() == 0) // durch 2^x, x>= 3 teilbar { if (zaehler.and(SIEBEN).intValue() != 1) rueck = -1; } else if (nenner.and(DREI).intValue() == 0) // durch 4 teilbar { if (zaehler.and(DREI).intValue() == 3) rueck = -1; } // nun noch alle zweier-Potenzen raus nenner = nenner.shiftRight(nenner.getLowestSetBit()); while (!zaehler.equals(BigInteger.ONE)) { // System.out.println ("Zähler " + zaehler + ", Nenner " + nenner + " und Ergebnis " + rueck); if (zaehler.equals(BigInteger.ZERO)) return 0; // 4er raus while (zaehler.getLowestSetBit() >= 2) zaehler = zaehler.shiftRight(2); // 2er raus (max. einen) if (! zaehler.testBit(0)) { rest = nenner.and(SIEBEN).intValue(); if ((rest == 3) || (rest == 5)) rueck = - rueck; zaehler = zaehler.shiftRight(1); } if (zaehler.equals(BigInteger.ONE)) return rueck; // beide sich jetzt ungerade: modulo rechnen, um Fall beides 3 mod 4 ermitteln // rest = zaehler.and(DREI).intValue(); rest = (zaehler.testBit(1) ? 2 : 0) + (zaehler.testBit(0) ? 1 : 0); if (rest == 3) { // rest = nenner.and(DREI).intValue(); rest = (nenner.testBit(1) ? 2 : 0) + (nenner.testBit(0) ? 1 : 0); if (rest == 3) { rueck = - rueck; } } BigInteger neu = nenner.remainder(zaehler); nenner = zaehler; zaehler = neu; } return rueck; } // Berechnet/ergänzt Kongruenzen für chinesischen Restesatz - läßt ein element übrig // z.B. k == 2 mod 3, k == 1 mod 5, k == 4 mod 7 // berechnungAb gibt den Index in kwert bzw. mod an, ab dem neue Werte eingefüllt wurden private boolean chinesischerSatz(final long kwert [], final long mod [], long kwertAgg[], long modAgg[], int berechnungAb, long grenze) { if ((kwert.length != mod.length) || (kwertAgg.length != modAgg.length) || (kwertAgg.length == 0) || ((kwert.length > 1) && (kwert.length != (kwertAgg.length+1)))) { System.out.println("Felder haben nicht gleiche/passende Länge " + kwert.length + " und " + kwertAgg.length); return false; } // Bei einem Eintrag ist keine Verrechnung nötig if (kwert.length == 1) { kwertAgg[0] = kwert[0]; modAgg[0] = mod[0]; return true; } // Index ist die Position der letzten aggregierten Kongruenz, oder <0 falls nichts verwendet werden kann int index = (berechnungAb < 2) ? -1 : (berechnungAb -2); // für aggr. Kongruenzen int startAb = (berechnungAb <= 1) ? 1 : berechnungAb; // für einzelne Kongruenzen for (int i = startAb; i < kwert.length; ++i) { // System.out.println("Aktuell: " + kwert[index-1] + "/" + mod[index-1] + " und " + kwert[index] + "/" + mod[index]); // hat noch mind. 2 Einträge BigInteger tmp1 = BigInteger.valueOf(mod[i]); BigInteger tmp2 = BigInteger.valueOf((index >= 0) ? modAgg[index] : mod[0]); BigInteger k1 = BigInteger.valueOf(kwert[i]); BigInteger k2 = BigInteger.valueOf((index >= 0) ? kwertAgg[index] : kwert[0]); // if (tmp1.compareTo(tmp2) < 0) { BigInteger tmp3 = tmp2; tmp2 = tmp1; tmp1 = tmp3; } long modneu = mod[i] * ((index >= 0) ? modAgg[index] : mod[0]); // Überlauf von long-Wert ( 4 in 9223372036854775811). Bei letzten Kongruenz ggf. tolerierbar if (modneu < 0) { System.out.println ("Überlauf long-Wert"); return false; } // gerechnet werden muss nur, wenn k1 und k2 verschieden sind BigInteger zahlNeu3 = null; if (!k1.equals(k2)) { BigInteger erg_inv = null; try { erg_inv = tmp2.modInverse(tmp1); // tmp2 < tmp1 ! // System.out.println("Inverse ist " + erg_inv); } catch (ArithmeticException ex) { System.out.println("ggt != 1 bei " + tmp2 + " und " + tmp1 + " , sollte eigentlich nicht vorkommen !"); /* zeigt an: nicht möglich */ return false; } BigInteger zahlNeu = erg_inv.multiply(tmp2); BigInteger zahlNeu2 = null; if (zahlNeu.compareTo(BigInteger.ZERO) < 0) zahlNeu2 = zahlNeu.abs().add(BigInteger.ONE); else zahlNeu2 = (BigInteger.ZERO.subtract(zahlNeu)).add(BigInteger.ONE); // Nun noch überkreuz multiplizieren // System.out.println (zahlNeu + " , " + k1 + " , " + zahlNeu2 + " , " + k2); zahlNeu3 = (zahlNeu.multiply(k1).add (zahlNeu2.multiply(k2))).remainder(BigInteger.valueOf(modneu)); // noch remainder ? if (zahlNeu3.compareTo(BigInteger.ZERO) < 0) zahlNeu3 = zahlNeu3.add(BigInteger.valueOf(modneu)); // Test: if (!zahlNeu3.remainder(tmp1).equals(k1) && !zahlNeu3.remainder(tmp2).equals(k2)) { System.out.println ("Fehler: " + k1 + " und " + tmp1 + ", " + k2 + " und " + tmp2); return false; // System.out.println ("Fehler für " + zahlNeu3); } // Bei positiven k-Werten ist jetzt auch kneu > max(k1, k2). Dies kann zum vorzeitigen Abbruch ben. werden if (false /* zahlNeu3.longValue() > grenze */) { if (true /* DEBUG */) System.out.println("CRS Ende wegen Überschreitung " + zahlNeu3); /* zeigt an: nicht möglich */ // return false; noch nicht tun, wegen Berechnung Ab } } else // k sind gleich { // System.out.println ("Effizienter Sonderfall"); zahlNeu3 = k1; // gut, braucht kein modInvers } ++index; if (DEBUG || DEBUG2) System.out.println ("An " + index + ": " + zahlNeu3 + " und " + modneu); // Hinweis Zahlenüberlauf: modneu oben abgetestet, zahlNeu3 sollte kleiner sein ! kwertAgg[index] = zahlNeu3.longValue(); modAgg[index] = modneu; } return true; // System von Kongruenzen konnte aufgelöst werden } }