| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/M5_MAX_INT.java |
|---|
| 0,0 → 1,16 |
| package de.viathinksoft.immortable.gen2; |
| import java.io.IOException; |
| import java.math.BigInteger; |
| import de.viathinksoft.immortable.gen2.math.ImmortableBase; |
| public class M5_MAX_INT { |
| public static void main(String[] args) throws IOException { |
| String val = "" + Integer.MAX_VALUE; |
| ImmortableWriter.writeImmortable(ImmortableBase.M5, |
| new BigInteger(val), "m5_" + val + ".txt", true); |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/InvalidLengthException.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2; |
| public class InvalidLengthException extends Exception { |
| private static final long serialVersionUID = 559305281746485769L; |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/ImmortableWriter.java |
|---|
| 0,0 → 1,36 |
| package de.viathinksoft.immortable.gen2; |
| import java.io.BufferedWriter; |
| import java.io.FileWriter; |
| import java.io.IOException; |
| import java.math.BigInteger; |
| import de.viathinksoft.immortable.gen2.math.ImmortableBase; |
| public class ImmortableWriter { |
| public static void writeImmortable(ImmortableBase b, BigInteger u, |
| String filename, boolean reverse) throws IOException { |
| BufferedWriter f = new BufferedWriter(new FileWriter(filename)); |
| String s = null; |
| if (b == ImmortableBase.M5) { |
| s = Immortable.M5(u).toString(); |
| } else if (b == ImmortableBase.M6) { |
| s = Immortable.M6(u).toString(); |
| } |
| if (reverse) { |
| s = new StringBuffer(s).reverse().toString(); |
| } |
| f.write(s); |
| f.close(); |
| } |
| private ImmortableWriter() { |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/erkenntnisse |
|---|
| 0,0 → 1,32 |
| Erkenntnis #1 - Der Zusammenhang zwischen M5 und M6 |
| M5(u) + M6(u) = 1 + 10^u |
| M5(u) = 1 + 10^u - M6(u) |
| M6(u) = 1 + 10^u - M5(u) |
| z.B. |
| M6 = 0081787109376 |
| M5 = 9918212890625 |
| ^^^^^^^^^^^^ |
| 999999999999 |
| Erkenntnis #2 - Speicherung |
| Aufgrund von Erkenntnis #1: |
| => Man muss nur noch M5 oder M6 größtmöglich berechnen und |
| kann dann auf das jeweils Andere schließen. |
| => Man benötigt kein BigInteger, um von M5 auf M6 zu wechseln. |
| Es reicht, wenn man alle Komplemente der Ziffern (mit |
| Ausnahme der letzten Ziffer "5" bzw "6"!) bildet und |
| aneinander reiht! |
| Desweiteren |
| - Man sollte die Zahlen umdrehen, sodass eine Datei mit |
| der aktuellen größtmöglichen Suche immer nur Appended |
| werden muss. |
| - Man sollte immer wieder Backups machen, um zu prüfen |
| ob der Algorithmus nicht an irgendeiner Stelle einen |
| Fehler gemacht hat (danach prüfen, ob alle Dateien den |
| selben Anfang haben) |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/CoPrimeExpectedException.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2.math; |
| public class CoPrimeExpectedException extends CRTException { |
| private static final long serialVersionUID = 8804691690532130114L; |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/CRTNotSolveableException.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2.math; |
| public class CRTNotSolveableException extends CRTException { |
| private static final long serialVersionUID = -2550866943316039887L; |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/ImmortableBase.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2.math; |
| public enum ImmortableBase { |
| M5, M6 |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/CRTException.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2.math; |
| public class CRTException extends Exception { |
| private static final long serialVersionUID = 1040331240918766268L; |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/ExtEuclResult.java |
|---|
| 0,0 → 1,30 |
| package de.viathinksoft.immortable.gen2.math; |
| import java.math.BigInteger; |
| public class ExtEuclResult { |
| private BigInteger alpha; // inverse |
| private BigInteger beta; |
| private BigInteger gcd; // ggT |
| public ExtEuclResult(BigInteger alpha, BigInteger beta, BigInteger gcd) { |
| super(); |
| this.alpha = alpha; |
| this.beta = beta; |
| this.gcd = gcd; |
| } |
| public BigInteger getAlpha() { |
| return alpha; |
| } |
| public BigInteger getBeta() { |
| return beta; |
| } |
| public BigInteger getGcd() { |
| return gcd; |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/MathUtils.java |
|---|
| 0,0 → 1,140 |
| package de.viathinksoft.immortable.gen2.math; |
| import java.math.BigInteger; |
| public class MathUtils { |
| /** |
| * Division with remainder method - based on the original Java<br> |
| * 'divideAndRemainder' method<br> |
| * returns an object of results (of type BigInteger):<br> |
| * -> the division result (q=a/b)<br> |
| * result[1] -> the remainder (r=a-q*b) |
| * |
| * @param a |
| * @param b |
| * @return |
| * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java |
| **/ |
| public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) { |
| // if (b==0) { |
| // -> divideAndRemainder() throws ArithmeticException when b==0 |
| if ((b.compareTo(BigInteger.ZERO)) == 0) { |
| return new DivisionAndRemainderResult(BigInteger.ZERO, |
| BigInteger.ZERO); |
| } |
| BigInteger[] x = a.divideAndRemainder(b); |
| return new DivisionAndRemainderResult(x[0], x[1]); |
| } |
| /** |
| * The Extended Euclidean Algorithm |
| * |
| * @param a |
| * @param gcd |
| * @return Object of "alpha" (inverse), "beta" and gcd (of type BigInteger). |
| * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java |
| */ |
| public static ExtEuclResult extEucl(BigInteger a, BigInteger gcd) { |
| // Coefficients |
| BigInteger alpha_0 = new BigInteger("1"); |
| BigInteger alpha_1 = new BigInteger("0"); |
| BigInteger beta_0 = new BigInteger("0"); |
| BigInteger beta_1 = new BigInteger("1"); |
| BigInteger alpha = new BigInteger("0"); |
| BigInteger beta = new BigInteger("1"); |
| if (gcd.compareTo(BigInteger.ZERO) == 0) { |
| alpha = BigInteger.ONE; |
| beta = BigInteger.ZERO; |
| gcd = a; |
| } else if (a.compareTo(BigInteger.ZERO) != 0) { |
| DivisionAndRemainderResult qr = divRem(a, gcd); |
| while (qr.getRemainder().compareTo(BigInteger.ZERO) != 0) { |
| alpha = alpha_0.subtract(qr.getDivisionResult().multiply( |
| alpha_1)); |
| beta = beta_0.subtract(qr.getDivisionResult().multiply(beta_1)); |
| alpha_0 = alpha_1; |
| beta_0 = beta_1; |
| alpha_1 = alpha; |
| beta_1 = beta; |
| a = gcd; |
| gcd = qr.getRemainder(); |
| qr = divRem(a, gcd); |
| } |
| } |
| return new ExtEuclResult(alpha, beta, gcd); |
| } |
| /** |
| * Determinates wheter p and q are coprimes or not. |
| * |
| * @param p |
| * @param q |
| * @return |
| */ |
| public static boolean isCoprime(BigInteger p, BigInteger q) { |
| return p.gcd(q).compareTo(BigInteger.ONE) == 0; |
| } |
| /** |
| * Solves the simultaneous congruences by means of the CR-Theorem:<br> |
| * M = Mp mod P and M = Mq mod Q<br> |
| * M = (Mq*Yp*P + Mp*Yq*Q) mod N<br> |
| * (Yp, Yq -> Ext.Eucl: Yp*P + Yq*Q = 1) |
| * |
| * @param Mp |
| * @param P |
| * @param Mq |
| * @param Q |
| * @return |
| * @throws CoPrimeExpectedException |
| * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Rsa.java |
| */ |
| public static BigInteger chineseRemainder(BigInteger Mp, BigInteger P, BigInteger Mq, |
| BigInteger Q) throws CoPrimeExpectedException { |
| if (!isCoprime(P, Q)) { |
| throw new CoPrimeExpectedException(); |
| } |
| // 1) yiMi = 1 mod mi -> computing Inverses yi (extended |
| // Euclides): |
| // yp*P = 1 mod Q -> yp (inverse) |
| // yq*Q = 1 mod P -> yq (inverse) |
| BigInteger yq = extEucl(Q, P).getAlpha(); |
| BigInteger yp = extEucl(P, Q).getAlpha(); |
| // 2) collecting 'M = (Mp*yq*Q + Mq*yp*P) mod N': |
| BigInteger psum = Mp.multiply(yq).multiply(Q); |
| BigInteger qsum = Mq.multiply(yp).multiply(P); |
| BigInteger sum = psum.add(qsum); |
| // computing 'sum mod m' |
| BigInteger N = P.multiply(Q); // common modulus |
| BigInteger M = divRem(sum, N).getRemainder(); |
| // if remainder (a/b) is negative (cause 'a' negative) then: |
| if (M.compareTo(BigInteger.ZERO) < 0) { |
| M = M.add(N); |
| } |
| return M; |
| } |
| private MathUtils() { |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/RemainderNotSmallerThanModulusException.java |
|---|
| 0,0 → 1,7 |
| package de.viathinksoft.immortable.gen2.math; |
| public class RemainderNotSmallerThanModulusException extends CRTException { |
| private static final long serialVersionUID = -1361245285354281472L; |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/MathUtils2.java |
|---|
| 0,0 → 1,170 |
| package de.viathinksoft.immortable.gen2.math; |
| import java.math.BigInteger; |
| public class MathUtils2 { |
| public static BigInteger length(BigInteger x) { |
| // TODO: größer als MAX_INTEGER erlauben! |
| return new BigInteger(""+x.toString().length()); |
| } |
| public static BigInteger pow(BigInteger base, BigInteger exponent) { |
| if (exponent.compareTo(BigInteger.ZERO) < 0) { |
| throw new ArithmeticException("Negative exponent"); |
| } |
| BigInteger i = new BigInteger("0"); |
| BigInteger res = new BigInteger("1"); |
| while (i.compareTo(exponent) != 0) { |
| i = i.add(BigInteger.ONE); |
| res = res.multiply(base); |
| } |
| return res; |
| } |
| /** |
| * Division with remainder method - based on the original Java<br> |
| * 'divideAndRemainder' method<br> |
| * returns an object of results (of type BigInteger):<br> |
| * -> the division result (q=a/b)<br> |
| * result[1] -> the remainder (r=a-q*b)<br> |
| * If b==0 then result will be 0. No ArithmeticException! |
| * |
| * @param a |
| * @param b |
| * @return |
| * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java |
| **/ |
| public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) { |
| // if (b==0) { |
| // -> divideAndRemainder() throws ArithmeticException when b==0 |
| if ((b.compareTo(BigInteger.ZERO)) == 0) { |
| return new DivisionAndRemainderResult(BigInteger.ZERO, |
| BigInteger.ZERO); |
| } |
| BigInteger[] x = a.divideAndRemainder(b); |
| return new DivisionAndRemainderResult(x[0], x[1]); |
| } |
| /** |
| * |
| * @param a |
| * @param b |
| * @return |
| * @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js |
| */ |
| private static BigInteger[] extGGT(BigInteger a, BigInteger b) { |
| if (b.compareTo(BigInteger.ZERO) == 0) { |
| return new BigInteger[] { BigInteger.ONE, BigInteger.ZERO }; |
| } |
| BigInteger rem = divRem(a, b).getRemainder(); |
| if (rem.compareTo(BigInteger.ZERO) == 0) { |
| return new BigInteger[] { BigInteger.ZERO, BigInteger.ONE }; |
| } |
| BigInteger[] c = extGGT(b, rem); |
| BigInteger x = c[0]; |
| BigInteger y = c[1]; |
| return new BigInteger[] { y, x.subtract(y.multiply(a.divide(b))) }; |
| } |
| /** |
| * Erweiterter euklidscher Algorithmus |
| * |
| * @param a |
| * @param b |
| * @return Erzeugt Objekt mit mit gcd=ggT(a,b) und gcd=alpha*a+beta*b |
| * @see http://www.arndt-bruenner.de/mathe/scripts/chineRestsatz.js |
| */ |
| private static ExtEuclResult erwGGT(BigInteger a, BigInteger b) { |
| BigInteger aa = new BigInteger("1"); |
| BigInteger bb = new BigInteger("1"); |
| if (a.compareTo(BigInteger.ZERO) < 0) { |
| aa = new BigInteger("-1"); |
| a = a.negate(); |
| } |
| if (b.compareTo(BigInteger.ZERO) < 0) { |
| bb = new BigInteger("-1"); |
| b = b.negate(); |
| } |
| BigInteger[] c = extGGT(a, b); |
| BigInteger g = a.gcd(b); |
| return new ExtEuclResult(c[0].multiply(aa), c[1].multiply(bb), g); |
| } |
| /** |
| * Allgemeines Lösen zweier Kongruenzen (Chinesischer Restsatz) |
| * |
| * @param a |
| * @param n |
| * @param b |
| * @param m |
| * @return |
| * @throws CRTNotSolveableException |
| * @throws RemainderNotSmallerThanModulusException |
| * @see http://de.wikipedia.org/wiki/Chinesischer_Restsatz#Direktes_L.C3.B6sen_von_simultanen_Kongruenzen_ganzer_Zahlen |
| */ |
| public static BigInteger chineseRemainder(BigInteger a, BigInteger n, |
| BigInteger b, BigInteger m) throws CRTNotSolveableException, RemainderNotSmallerThanModulusException { |
| // Frage: Ist es notwendig, dass wir divRem() verwenden, das von a%0==0 ausgeht? |
| if (a.compareTo(BigInteger.ZERO) < 0) { |
| a = a.negate(); |
| } |
| if (b.compareTo(BigInteger.ZERO) < 0) { |
| b = b.negate(); |
| } |
| if (n.compareTo(BigInteger.ZERO) < 0) { |
| n = n.negate(); |
| } |
| if (m.compareTo(BigInteger.ZERO) < 0) { |
| m = m.negate(); |
| } |
| if ((a.compareTo(n) >= 0) || (b.compareTo(m) >= 0)) { |
| throw new RemainderNotSmallerThanModulusException(); |
| } |
| // d = ggT(n,m) |
| BigInteger d = n.gcd(m); |
| // a === b (mod d) erfüllt? |
| if (!divRem(a, d).getRemainder().equals(divRem(b, d).getRemainder())) { |
| throw new CRTNotSolveableException(); |
| } |
| // ggT(n,m) = yn + zm |
| BigInteger y = erwGGT(n, m).getAlpha(); |
| // x = a - y*n*((a-b)/d) mod (n*m/d) |
| BigInteger N = n.multiply(m).divide(d); |
| BigInteger x = divRem( |
| a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d))), N) |
| .getRemainder(); |
| x = a.subtract(y.multiply(n).multiply(a.subtract(b).divide(d))); |
| while (x.compareTo(BigInteger.ZERO) < 0) { |
| x = x.add(N); |
| } |
| return x; |
| } |
| private MathUtils2() { |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/DivisionAndRemainderResult.java |
|---|
| 0,0 → 1,25 |
| package de.viathinksoft.immortable.gen2.math; |
| import java.math.BigInteger; |
| public class DivisionAndRemainderResult { |
| private BigInteger divisionResult; |
| private BigInteger remainder; |
| public DivisionAndRemainderResult(BigInteger divisionResult, |
| BigInteger remainder) { |
| super(); |
| this.divisionResult = divisionResult; |
| this.remainder = remainder; |
| } |
| public BigInteger getDivisionResult() { |
| return divisionResult; |
| } |
| public BigInteger getRemainder() { |
| return remainder; |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |
| /ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/Immortable.java |
|---|
| 0,0 → 1,123 |
| package de.viathinksoft.immortable.gen2; |
| import java.math.BigInteger; |
| import de.viathinksoft.immortable.gen2.math.CoPrimeExpectedException; |
| import de.viathinksoft.immortable.gen2.math.ImmortableBase; |
| import de.viathinksoft.immortable.gen2.math.MathUtils; |
| import de.viathinksoft.immortable.gen2.math.MathUtils2; |
| /** |
| * Immortable Number Generator (ING) |
| * |
| * @author Daniel Marschall |
| */ |
| public class Immortable { |
| /** |
| * Calculates M5 or M6 |
| * |
| * @param base |
| * @param u |
| * @return |
| */ |
| public static BigInteger M(ImmortableBase base, BigInteger u) { |
| BigInteger p, q; |
| if (base == ImmortableBase.M5) { |
| p = BigInteger.ONE; |
| q = BigInteger.ZERO; |
| } else if (base == ImmortableBase.M6) { |
| p = BigInteger.ZERO; |
| q = BigInteger.ONE; |
| } else { |
| p = null; |
| q = null; |
| } |
| BigInteger a = MathUtils2.pow(new BigInteger("2"), u); |
| BigInteger b = MathUtils2.pow(new BigInteger("5"), u); |
| // To calculate M5: |
| // x = 2^u = a mod 1 |
| // x = 5^u = b mod 0 |
| // To calculate M6: |
| // x = 2^u = a mod 0 |
| // x = 5^u = b mod 1 |
| try { |
| return MathUtils.chineseRemainder(p, a, q, b); |
| } catch (CoPrimeExpectedException e) { |
| // Can never happen since 2^u and 5^u are always coprimes. |
| return null; |
| } |
| } |
| /** |
| * Gets M5(u) |
| * |
| * @param u |
| * Length of number |
| * @return |
| */ |
| public static BigInteger M5(BigInteger u) { |
| return M(ImmortableBase.M5, u); |
| } |
| /** |
| * Gets M6(u) |
| * |
| * @param u |
| * Length of number |
| * @return |
| */ |
| public static BigInteger M6(BigInteger u) { |
| return M(ImmortableBase.M6, u); |
| } |
| /** |
| * Toggles between M5 and M6 base. |
| * |
| * @param cur |
| * Number |
| * @param u |
| * Length of number (because of possible leading zeros) |
| * @return Number in opposide base. |
| * @throws InvalidLengthException |
| */ |
| public static BigInteger toggleBase(BigInteger cur, BigInteger u) |
| throws InvalidLengthException { |
| // Converts M6(u) <-> M5(u) |
| // M6(u) = 1 + 10^u - M5(u) |
| // M5(u) = 1 + 10^u - M6(u) |
| if (u.compareTo(MathUtils2.length(cur)) < 0) { |
| throw new InvalidLengthException(); |
| } |
| return BigInteger.ONE.add(MathUtils2.pow(BigInteger.TEN, u)).subtract(cur); |
| } |
| /** |
| * Toggles between M5 and M6 base. The length of the current number is |
| * assumed (and no leading zero). |
| * |
| * @param cur |
| * @return |
| */ |
| public static BigInteger toggleBase(BigInteger cur) { |
| try { |
| return toggleBase(cur, MathUtils2.length(cur)); |
| } catch (InvalidLengthException e) { |
| // Should never happen |
| return null; |
| } |
| } |
| private Immortable() { |
| } |
| } |
| Property changes: |
| Added: svn:mime-type |
| +text/plain |
| \ No newline at end of property |