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.