| Home |
| About me |
| My CV |
| Hobbies |
| Professional Experiences |
| Projects |
| Computer skills |
| My Gentoo Overlay |
| Gallery |
| Personal gallery |
| Guestbook |
| Contact me |
| Gentoo |
| *nix |
| Programming |
| Softwares |
| Misc |
| Miller-Rabin prime test in Java |
A simple Miller-Rabin prime number test I wrote in Java. Along with this method I implemented isWitness as well as the modulo power by bit shifting method. Feel free to comment ;) ================= Update: Someone requested for myBigRanNum and FactorOfTwo, I put them here as well, enjoy. =================
public static boolean MillerRabin(BigInteger n, int k){
BigInteger a; BigInteger m = n.subtract(BigInteger.ONE); boolean isPrime = true; if (n.compareTo(BigInteger.ONE) == 0) return false; if (n.mod(BigInteger.valueOf(2)).intValue() == 0) return false; for (int i = 0; i < k; i++) { a = myBigRanNum(MAX_BIT); if (a.compareTo(m) > 0) a = a.mod(m); if (a.compareTo(BigInteger.ZERO) == 0) a = BigInteger.ONE; if (isWitness(a, n)) return false; } return isPrime; } public static boolean isWitness(BigInteger a, BigInteger n) { int s; BigInteger apow; BigInteger firstEqua, secondEqua; BigInteger m = n.subtract(BigInteger.ONE); BigInteger d; s = FactorOfTwo(m); d = m.divide(BigInteger.valueOf((int)Math.pow(2, s))); firstEqua = ModExpo(a, d, n); if (firstEqua.intValue() == 1 || firstEqua.compareTo(m) == 0 ) return false; for (int r = 0; r < s; r++) { apow = d.multiply(BigInteger.valueOf((int)Math.pow(2, r))); secondEqua = ModExpo(a, apow, n); if (secondEqua.intValue() == -1 || secondEqua.compareTo(m) == 0) { return false; } } return true; } public static BigInteger ModExpo(BigInteger aBigInt, BigInteger pow, BigInteger n) { BigInteger e = pow; BigInteger a = aBigInt; BigInteger result = BigInteger.ONE; while (e.compareTo(BigInteger.ZERO) > 0 ) { if (e.and(BigInteger.ONE).compareTo(BigInteger.ONE) == 0 ){ result = (result.multiply(a)).mod(n); } e = e.shiftRight(1); a = (a.multiply(a)).mod(n); } return result; } public static int FactorOfTwo(BigInteger aNumber) { int i = 0; BigInteger myNumber = aNumber; BigInteger myRemainer; while (true) { myRemainer = myNumber.mod(BigInteger.valueOf(2)); if (myRemainer.compareTo(BigInteger.ZERO) != 0 ) break; myNumber = myNumber.divide(BigInteger.valueOf(2)); i++; } return i; } public static BigInteger myBigRanNum(int numBits) { //We only deal with positive number here BigInteger aBigInterger = new BigInteger(numBits, aRand); aBigInterger = aBigInterger.abs(); return aBigInterger; } Last update: 15-03-2008 09:14
|
| < Prev |
|---|