Math.pow() problem...

[abhi_elementx]

Hello folks,
I m trying to simulate the RSA algorithm.
This is some of my code:
System.out.println((int)Math.pow(6, 5) % 119);
System.out.println((int)Math.pow(41, 77) % 119);

The first results in 41 while the second results in -9 when the expected shud be 6.
Whats wrong?

[stephen84s]

The first results in 41 while the second results in -9 when the expected shud be 6.

Thats most probably happening due to overflow. To illustrate this simple fact try compiling and running the following code snippet:-

class OverflowDemo {
  public static void main(String[] args) {
    short a = 32767;
    a++;
    System.out.println("a = " + a);
  }
}

The above chunk of code on compiling and executing would give the following output :-

stephen@steve:~/Development/java/daniweb> javac OverflowDemo.java
stephen@steve:~/Development/java/daniweb> java OverflowDemo
a = -32768
stephen@steve:~/Development/java/daniweb>

Here when we added 1 to "a", we exceeded the capacity of "short" and it rounded off to -32768 due to overflow, similarly Math.pow(41, 77) exceeded the capacity of int.

Try casting the value returned by it to "long" to see if it fits there. If long also throws an error then the best option would be to use the BigInteger class where you will not be faced with any restriction on the value it can hold.

[BestJewSinceJC]

int is 32 bits so it can only hold whatever value 32 bits can hold. And since you want to know if it's positive or negative, there goes one bit that would've gone towards calculation. So calculate that and there's your limit.

[abhi_elementx]

Thanks guys for the replies. Now I have I more problem.
This is my RSASimulation.java
public class RSASimulation {
.
.
public static BigInteger random_prime(BigInteger num){//generates a random prime number
if(Factorize.isPrime(num))//calling isPrime() in Factorize class
return num;
else if(num.equals(new BigInteger("1")))
return random_prime(get_random(num));
else
return random_prime(get_random(num));
}//random_prime() ends
.
.
public static void main(String[] args){//MAIN function
//clrscr(); //doesnt work on gcc
//step 1 choose 2 prime numbers
//BigInteger P = new BigInteger("7"/*random_prime(900)*/);
//BigInteger Q = new BigInteger("17");//random_prime(900);

BigInteger P = random_prime(new BigInteger("10"));
BigInteger Q = random_prime(new BigInteger("10"));

System.out.println("P = "+P+"\n"+"Q = "+Q);

//step 2 calculate N = P x Q
BigInteger N = P.multiply(Q);
System.out.println("\nP X Q = "+N);

//step 3 select public key(Encryption key) E such that it is not a factor of (P - 1) and (Q - 1)
BigInteger one = new BigInteger("1");
BigInteger P_min_1 = P.subtract(one);
BigInteger Q_min_1 = Q.subtract(one);

//BigInteger E = new BigInteger("0");
BigInteger E = get_Encryption_key(P_min_1, Q_min_1); //E is Encryption key
System.out.println("\nEncryption key : "+E);

//step 4 select private key(Decryption key) D such that (D X E) mod (P_min_1) X (Q_min_1) = 1
BigInteger D = get_Decryption_key(E, P_min_1.multiply(Q_min_1));
System.out.println("\nDecryption key : "+D);

This is my Factorize class public class Factorize {
public static boolean isPrime(BigInteger num){//returns true if num is prime; false otherwise
if((num.intValue()) == 0 ||(num.intValue()) == 1 || (num.intValue()) == 2) return false;
else for(int i = 2; i < num.intValue(); i++){
if(((num.intValue()) % i) == 0)
return false;
}
return true;
}//isprime() ends

Sometimes, I get the Encryption key and the program hangs..
heres my get_Decryption_key() public static BigInteger get_Decryption_key(BigInteger E, BigInteger P_min_1_into_Q_min_1){
BigInteger key = new BigInteger("0");
while(true){
key = get_random(new BigInteger("100"));
if((key.multiply(E)).mod(P_min_1_into_Q_min_1).equals(new BigInteger("1")))break;
}
return key;
}

Is it hanging at the if statement?
Thanks again.

[BestJewSinceJC]

edit: was looking at the wrong code, nevermind

[stephen84s]

Now considering the piece of code that you say causes the problem :-

while(true){
  key = get_random(new BigInteger("100"));
  if((key.multiply(E)).mod(P_min_1_into_Q_min_1).
      equals(new BigInteger("1")))
    break;
}

Now from what I see, what **I think** is happening is that your "if" condition is never getting satisfied as a result of which your program goes into an "infinite" loop giving you the feeling that it has hung up.

My suggestion is put a System.out.print statement just in front of your "if" with its contents as the "if condition" so that you can visualize what is actually the state of your variables or where your values are drifting off track.