Shanks algorithm fails mysteriously on a certain set of numbers

Question

I am trying to implement Shank's Algorithm to find discrete logarithms. I implemented it in Java and it works…most of the time. For some reason, I find that on one of the times I try to use it, it fails. I don't see why…

Included below are the instructions from my Main method, along with the shanks() method. It solves the problem correctly for the first two problems in Main, but not the third. It returns -1 (the initial, failure-value of "answer"). I am using the squareMultiply method (which implements the Square-and-Multiply algorithm for modular exponentiation) to check the results.

From Main():

int p =809;
int theta = 3;
int beta = 525;

System.out.println("test (ex.2) = "+shanks(p, theta, beta));

p = 24691;
theta = 106;
beta = 12375;

answer = shanks(p, theta, beta);
System.out.println("1st part of Q = "+answer);
System.out.println(squareMultiply(theta, answer, p));

p = 458009;
theta = 6;
beta = 248388;

answer = shanks(p, theta, beta);    
System.out.println("2nd part of Q = "+answer);
System.out.println(squareMultiply(theta, answer, p));

The actual shanks() method:

public static int shanks(int p, int theta, int beta){

int answer = -1;
int order = p-1;    
int m = (int)Math.ceil(Math.sqrt(order));
int thetaInvMult;
int thetaRaised = squareMultiply(theta, m, p);
int thetaInv= getMIM(p, theta);
HashMap<Integer, Coords> list1 = new HashMap<Integer, Coords>();
HashMap<Integer, Coords> list2 = new HashMap<Integer, Coords>();

for(int j = 0; j <= m-1; j++){
    int thetaRaisedAgain = squareMultiply(thetaRaised, j, p);
    Coords coords = new Coords(j, thetaRaisedAgain);
    list1.put(j, coords);   
}

for(int i = 0; i <= m-1; i++){
    thetaInvMult = beta*squareMultiply(thetaInv, i, p);
    thetaInvMult = thetaInvMult % p;    
    Coords coords = new Coords(i, thetaInvMult);
    list2.put(thetaInvMult, coords);
}

for(int z = 0; z <= m-1; z++){
    Integer intZ = new Integer(z);
    Coords list1Val = list1.get(intZ);
    Coords list2Val = list2.get(list1Val.result);
    if (list2Val!=null){
        int x = list1Val.result;
        int y = list2Val.result;

        if (x==y){
            System.out.println("got it "+x+" , "+y);
            int finalJ = list1Val.counterValue;
            int finalI = list2Val.counterValue;
            answer = m*finalJ+finalI;
            answer = answer % p; 
        }else{
            System.out.println("don't");
        }
    }

}
return answer;  

}

Again, it works for the first two, but not the third…Thanks in advance for any and all help!

EDIT: "It works" means the discrete log is found. It is checked by the squareMultiply method. "It fails" means it does not solve the discrete logarithm; it does not find the appropriate exponent. Instead, it simply returns '-1', which is the default value of 'answer'.

Here is the SquareMultiply() method:

public static int squareMultiply (int encryption, int exponent, int n){

double z = 1;

//convert exponent into the binary expansion, put in array
String exponentBinary = Integer.toBinaryString(exponent);
int length = exponentBinary.length();
int [] coefficients = new int[length];
String temp;
for(int i=0; i<length;i++){
    temp = String.valueOf(exponentBinary.charAt(i));
    coefficients[i] = Integer.parseInt(temp);
}
for (int l=0; l<length; l++){
    z = (Math.pow(z,2));
    z = z%n;

    if (coefficients[l]==1){
        z = (z*encryption)%n;
    }
}
int z2 = (int)z;
return z2;
  } 

Answer 1

It was an overflow/underflow problem…I switched some variables from ints to longs and it worked, thank G-d!