Rev 5 | Details | Compare with Previous | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 30 | daniel-mar | 1 | package de.viathinksoft.immortal.gen2.math; |
| 5 | daniel-mar | 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 | } |