Subversion Repositories distributed

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
42 daniel-mar 1 
package de.viathinksoft.immortal.bases;
2 
/**
3 
 * Powmod.java
4 
 *
5 
 * Implementation von a^b mod m durch iteriertes Quadrieren. Zum Testen: Der
6 
 * Aufruf java powmod a b m gibt a^b mod m aus.
7 
 *
8 
 * @author Thorsten Altenkirch
9 
 * @version Modified by Daniel Marschall
10 
 *
11 
 */
12 
 
13 
public class PowMod {
14 
 
15 
        /**
16 
         * Ermittelt das nte Bit von l
17 
         */
18 
        private static boolean bit(long l, int n) {
19 
                return (((l >> n) & 1) != 0);
20 
        }
21 
 
22 
        /**
23 
         * Berechnet a^b mod m durch iteriertes Quadrieren.
24 
         */
25 
        public static long powmod(long a, long m, long n) {
26 
                long y = 1;
27 
                for (int i = 62; i >= 0; i--) {
28 
                        y = y * y % n;
29 
                        if (bit(m, i)) {
30 
                                y = a * y % n;
31 
                        }
32 
                }
33 
                return y;
34 
        }
35 
 
36 
        private PowMod() {
37 
        }
38 
}