Java BigInteger , number theory , modular arithmetic

Question

Anyone have an idea on how to implement such a problem in java ?

"Implement a subroutine that takes three positive integer arguments (a; b; n) and returns the value of ( (a to the power of b) mod n), where the arguments are represented by about 100 decimal digits. Using four different methods."

Thanks in advance

UPD : Methods were be as following

M1)

public BigInteger Result1(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
        Res = Res.multiply(a).mod(n);
    }
    return Res;
}

M2)

public BigInteger Result2(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
        Res = Res.multiply(a);
    }
    return Res.mod(n);
}

M3)

ublic BigInteger Result3(BigInteger a , BigInteger b , BigInteger n){
    if(b.equals(new BigInteger("0"))){
        return new BigInteger("1");
    }
    else if(b.mod(new BigInteger("2")).equals(new BigInteger("0"))){
        BigInteger Res = Result3(a,b.divide(new BigInteger("2")),n);
        return (Res.multiply(Res)).mod(n);
    }
    else{
        return ( (a.mod(n)).multiply(Result3(a, b.subtract(new BigInteger("1")), n)) ).mod(n);
    }
}

M4)

public BigInteger Result4(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    while(!b.equals(new BigInteger("0"))) {
        if(!(b.mod(new BigInteger("2"))).equals(new BigInteger("0"))) {
            Res = Res.multiply(a).mod(n);
        }
        a = a.multiply(a).mod(n);
        b = b.divide(new BigInteger("2"));
    }
    return Res;
}

Answer 1

Flustered this was put on hold...

For the sake of theory, if you wanted to write your own custom method please check the following out, based on a math trick to avoid the computation. First the solution, and then the math behind it.

Your subroutine could look something like the following:

public static BigInteger customPowMod(BigInteger a, BigInteger b, BigInteger n){
    BigInteger previous = a.mod(n);
    BigInteger runningTotal = new BigInteger("1");
    for(int i = 0; i < a.bitLength(); i++){
        if(a.testBit(i)){
            runningTotal = runningTotal.multiply(previous);
        }
        previous = previous.multiply(previous).mod(n);
    }
    return runningTotal.mod(n);
}

The following is an example of how you could call the method:

public static void main(String[] args) {
    BigInteger a = new BigInteger("1700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005");
    BigInteger b = new BigInteger("6300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005");
    BigInteger n = new BigInteger("50000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    //note the following produce the same values
    System.out.println(customPowMod(a,b,n)); 
    System.out.println(a.modPow(b,n));
}

Now for the explanation

I'm doing smaller numbers for the sake of explaining things... it's the process by hand that get's turned into the code at the end.

• let a = 17
• let b = 63
• let n = 5

First you want to see what base2 powers your power number b is composed of. For example:

63 = 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 32 + 16 + 8 + 4 + 2 + 1.

OR in binary 11111

This can be found programatically by iterating from 0 to our BigInteger b's .bitLength() and and checking with .testBit() the given bits. Hence the for-loop in the Java code.

Next we find multiples of your base modulus (n) target (you need to go as far out in value as your highest power of two from the previous segment):

let us call each simplified value a<power_of_2>.

• a mod n = a1
• a^2 mod n = a2
• a^4 mod n = (a2)^2 mod n = a4 mod n
• a^8 mod n = (a4)^2 mod n = a8 mod n
• ...

and the by hand values:

• 17^1 % 5 = 2
• 17^2 % 5 = 2^2 mod 5 = 4 mod 5 = 4
• 17^4 % 5 = 4^2 mod 5 = 16 mod 5 = 1
• 17^8 % 5 = 1^2 mod 5 = 1 mod 5 = 1
• 17^16 % 5 = 1^2 mod 5 = 1 mod 5 = 1
• 17^32 % 5 = 1^2 mod 5 = 1 mod 5 = 1

Problematically this can be done in sync with the previous step of finding the base2 powers, each iteration you also find the newest a<power_of_2>. Each additional square needs to be calculated until we've hit the max value, hence the ever increasing previous value in the loop.

Lastly, we take our neccessary a values and multiple them by each other, followed by modulus of our n. this is within the if statement of the foor-loop.

• Again, we have the powers: 32 + 16 + 8 + 4 + 2 + 1

and from the above step we have take the values and multiple them together (followed by the modulus at the end of the loop):

1 * 1 * 1 * 1 * 4 * 2 % 5 = 8 % 5 = 3

Answer 2

You can use the BigInteger class for this if you aren't desperately needing performance. BigInteger is immutable.

public static BigInteger getValue(int a, int b, int n) {
    return BigInteger.valueOf(a).modPow(BigInteger.valueOf(b), BigInteger.valueOf(n));
}

Answer 3

To answer your question directly, I think BigInteger.modPow might be what you're looking for.

public BigInteger modPow(BigInteger exponent,
                     BigInteger m)

Returns a BigInteger whose value is (this^exponent mod m)

Alternatively (and more efficiently), you could also take (a mod n) to the (b mod n) power, this should make the code run much quicker.

(a^b mod n) = ((a mod n)^(b mod n) mod n)