Subversion Repositories distributed

Rev

Rev 5 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. package de.viathinksoft.immortal.gen2.math;
  2.  
  3. import java.math.BigInteger;
  4.  
  5. public class MathUtils {
  6.  
  7.         /**
  8.          * Division with remainder method - based on the original Java<br>
  9.          * 'divideAndRemainder' method<br>
  10.          * returns an object of results (of type BigInteger):<br>
  11.          * -> the division result (q=a/b)<br>
  12.          * result[1] -> the remainder (r=a-q*b)
  13.          *
  14.          * @param a
  15.          * @param b
  16.          * @return
  17.          * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
  18.          **/
  19.  
  20.         public static DivisionAndRemainderResult divRem(BigInteger a, BigInteger b) {
  21.                 // if (b==0) {
  22.                 // -> divideAndRemainder() throws ArithmeticException when b==0
  23.                 if ((b.compareTo(BigInteger.ZERO)) == 0) {
  24.                         return new DivisionAndRemainderResult(BigInteger.ZERO,
  25.                                         BigInteger.ZERO);
  26.                 }
  27.  
  28.                 BigInteger[] x = a.divideAndRemainder(b);
  29.                 return new DivisionAndRemainderResult(x[0], x[1]);
  30.         }
  31.  
  32.         /**
  33.          * The Extended Euclidean Algorithm
  34.          *
  35.          * @param a
  36.          * @param gcd
  37.          * @return Object of "alpha" (inverse), "beta" and gcd (of type BigInteger).
  38.          * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Demos.java
  39.          */
  40.  
  41.         public static ExtEuclResult extEucl(BigInteger a, BigInteger gcd) {
  42.  
  43.                 // Coefficients
  44.                 BigInteger alpha_0 = new BigInteger("1");
  45.                 BigInteger alpha_1 = new BigInteger("0");
  46.                 BigInteger beta_0 = new BigInteger("0");
  47.                 BigInteger beta_1 = new BigInteger("1");
  48.                 BigInteger alpha = new BigInteger("0");
  49.                 BigInteger beta = new BigInteger("1");
  50.  
  51.                 if (gcd.compareTo(BigInteger.ZERO) == 0) {
  52.                         alpha = BigInteger.ONE;
  53.                         beta = BigInteger.ZERO;
  54.                         gcd = a;
  55.                 } else if (a.compareTo(BigInteger.ZERO) != 0) {
  56.                         DivisionAndRemainderResult qr = divRem(a, gcd);
  57.  
  58.                         while (qr.getRemainder().compareTo(BigInteger.ZERO) != 0) {
  59.                                 alpha = alpha_0.subtract(qr.getDivisionResult().multiply(
  60.                                                 alpha_1));
  61.                                 beta = beta_0.subtract(qr.getDivisionResult().multiply(beta_1));
  62.  
  63.                                 alpha_0 = alpha_1;
  64.                                 beta_0 = beta_1;
  65.  
  66.                                 alpha_1 = alpha;
  67.                                 beta_1 = beta;
  68.  
  69.                                 a = gcd;
  70.                                 gcd = qr.getRemainder();
  71.                                 qr = divRem(a, gcd);
  72.                         }
  73.                 }
  74.  
  75.                 return new ExtEuclResult(alpha, beta, gcd);
  76.         }
  77.  
  78.         /**
  79.          * Determinates wheter p and q are coprimes or not.
  80.          *
  81.          * @param p
  82.          * @param q
  83.          * @return
  84.          */
  85.         public static boolean isCoprime(BigInteger p, BigInteger q) {
  86.                 return p.gcd(q).compareTo(BigInteger.ONE) == 0;
  87.         }
  88.  
  89.         /**
  90.          * Solves the simultaneous congruences by means of the CR-Theorem:<br>
  91.          * M = Mp mod P and M = Mq mod Q<br>
  92.          * M = (Mq*Yp*P + Mp*Yq*Q) mod N<br>
  93.          * (Yp, Yq -> Ext.Eucl: Yp*P + Yq*Q = 1)
  94.          *
  95.          * @param Mp
  96.          * @param P
  97.          * @param Mq
  98.          * @param Q
  99.          * @return
  100.          * @throws CoPrimeExpectedException
  101.          * @see http://tupac.euv-frankfurt-o.de/www/kryptos/demos/Rsa.java
  102.          */
  103.  
  104.         public static BigInteger chineseRemainder(BigInteger Mp, BigInteger P, BigInteger Mq,
  105.                         BigInteger Q) throws CoPrimeExpectedException {
  106.  
  107.                 if (!isCoprime(P, Q)) {
  108.                         throw new CoPrimeExpectedException();
  109.                 }
  110.  
  111.                 // 1) yiMi = 1 mod mi -> computing Inverses yi (extended
  112.                 // Euclides):
  113.                 // yp*P = 1 mod Q -> yp (inverse)
  114.                 // yq*Q = 1 mod P -> yq (inverse)
  115.  
  116.                 BigInteger yq = extEucl(Q, P).getAlpha();
  117.                 BigInteger yp = extEucl(P, Q).getAlpha();
  118.  
  119.                 // 2) collecting 'M = (Mp*yq*Q + Mq*yp*P) mod N':
  120.  
  121.                 BigInteger psum = Mp.multiply(yq).multiply(Q);
  122.                 BigInteger qsum = Mq.multiply(yp).multiply(P);
  123.                 BigInteger sum = psum.add(qsum);
  124.  
  125.                 // computing 'sum mod m'
  126.                 BigInteger N = P.multiply(Q); // common modulus
  127.                 BigInteger M = divRem(sum, N).getRemainder();
  128.  
  129.                 // if remainder (a/b) is negative (cause 'a' negative) then:
  130.                 if (M.compareTo(BigInteger.ZERO) < 0) {
  131.                         M = M.add(N);
  132.                 }
  133.  
  134.                 return M;
  135.         }
  136.        
  137.         private MathUtils() {
  138.         }
  139.  
  140. }
  141.