Skip to content

Instantly share code, notes, and snippets.

@ertugrulozcan
Last active January 9, 2018 21:44
Show Gist options
  • Save ertugrulozcan/7776833 to your computer and use it in GitHub Desktop.
Save ertugrulozcan/7776833 to your computer and use it in GitHub Desktop.
Binary Method
package com.aero.Math;
import java.math.BigInteger;
public abstract class BinaryModularExponentiation
{
public static BigInteger ModPower(BigInteger m, BigInteger e, BigInteger n)
{
BigInteger c;
// Mesajın bit dizisine dönüştürülmesi;
Boolean[] bitArray = ConvertToBinary(e);
if(bitArray[0])
c = m;
else
c = BigInteger.ONE;
for(int i = bitArray.length - 2; i > 0; i--)
{
c = c.multiply(c).mod(n);
if(bitArray[i])
c = c.multiply(m).mod(n);
}
return c;
}
//
// BigInteger sayının binary formata dönüştürülmesi
//
private static Boolean[] ConvertToBinary(BigInteger n)
{
// Bit uzunluğunun tespiti;
int bitLength = GetBitLength(n);
//
// Bit dizisinin oluşturulması
//
Boolean[] result = new Boolean[bitLength];
result[0] = true;
BigInteger t = BigInteger.valueOf(2).pow(bitLength - 1);
for(int i = 1; i < bitLength; i++)
{
if(t.add(BigInteger.valueOf(2).pow(bitLength - i - 1)).compareTo(n) == 1)
{
result[i] = false;
}
else
{
result[i] = true;
t = t.add(BigInteger.valueOf(2).pow(bitLength - i - 1));
}
}
return result;
}
//
// Bit uzunluğunun tespiti;
//
private static int GetBitLength(BigInteger n)
{
int bitLength = 1;
// Tek sayı mı? Çift sayı mı?
Boolean isDouble = n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0;
while(n.compareTo(BigInteger.ONE) == 1)
{
if(!isDouble)
n = n.subtract(BigInteger.ONE);
n = n.divide(BigInteger.valueOf(2));
bitLength++;
isDouble = n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0;
}
return bitLength;
}
}
@caslnyrk
Copy link

caslnyrk commented Jan 9, 2018

Kolay gelsin. Kodunuz da herhangi bir hata var mı acaba?Doğru sonuç alamıyorum da.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment