/ViaThinkSoft Distributed/src/de/viathinksoft/immortable/internal/Endzeitpunkt.java |
---|
0,0 → 1,39 |
package de.viathinksoft.immortable.internal; |
import java.math.BigInteger; |
public class Endzeitpunkt { |
// Allgemeine Daten zum Test (GenX) |
private static final BigInteger TEST_BEGINN = new BigInteger("1291006160"); |
// Der alte Algorithmus (r19) |
// private static final int ABSCHNITT_STEP = 3; |
// private static final BigInteger ABSCHNITT_BEGINN = new BigInteger("789"); |
// private static final BigInteger ABFALL_MEDIAN = new BigInteger("199"); |
// Der neue Algorithmus (r20) |
private static final int ABSCHNITT_STEP = 29; |
private static final BigInteger ABSCHNITT_BEGINN = new BigInteger("94923"); |
private static final BigInteger ABFALL_MEDIAN = new BigInteger("30"); |
private static BigInteger f(int u) { |
BigInteger res = ABSCHNITT_BEGINN; |
for (int i = ABSCHNITT_STEP + 1; i <= u; i++) { |
res = res.add(ABFALL_MEDIAN.multiply(BigInteger.valueOf(i))); |
} |
return res; |
} |
private static BigInteger u(int u) { |
return f(u).add(TEST_BEGINN); |
} |
public static void main(String[] args) { |
int max_step = Integer.MAX_VALUE / 100000; |
System.out.println("End time for step: " + max_step); |
System.out.println(u(max_step)); |
} |
} |
/ViaThinkSoft Distributed/src/de/viathinksoft/immortable/gen2/math/MathUtils2.java |
---|
0,0 → 1,176 |
package de.viathinksoft.immortable.gen2.math; |
import java.math.BigInteger; |
public class MathUtils2 { |
public static BigInteger length(BigInteger x) throws Exception { |
// TODO: größer als MAX_INTEGER erlauben! |
BigInteger z = new BigInteger(""+x.toString().length()); |
if (z.signum() == -1) { |
throw new Exception("Integer overflow! (BigInteger-Length)"); |
} |
return z; |
} |
public static BigInteger pow(BigInteger base, BigInteger exponent) { |
if (exponent.signum() == -1) { |
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.signum() == 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.signum() == 0) { |
return new BigInteger[] { BigInteger.ONE, BigInteger.ZERO }; |
} |
BigInteger rem = divRem(a, b).getRemainder(); |
if (rem.signum() == 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.signum() == -1) { |
aa = new BigInteger("-1"); |
a = a.negate(); |
} |
if (b.signum() == -1) { |
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 CRTException { |
// Frage: Ist es notwendig, dass wir divRem() verwenden, das von a%0==0 ausgeht? |
if (a.signum() == -1) { |
a = a.negate(); |
} |
if (b.signum() == -1) { |
b = b.negate(); |
} |
if (n.signum() == -1) { |
n = n.negate(); |
} |
if (m.signum() == -1) { |
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.signum() == -1) { |
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/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/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/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 |