I am trying to get back the proper exponent, and this program works when I plug in the example numbers(exampleA, exampleB, exampleP) as they return the value they should, but when I plug in the long numbers(A, B, p), the loop continues. I believe I should be getting 2099 when plugging in B and p. What am I doing wrong here?

public static void main(String[] args) {
        //g = 5//
        //let i run from 0 to p -1//
        //compute g^a mod p and see if it is A, if you find A, then a is the solution for A//
        //compute g^a mod p and see if it is B, if you find B, then a is the solution for B//
        long A = 1958258942L;
        long B = 670001116L;
        long p = 3267000013L;
        //example p to plug in for example a and example b//
        long exampleP = 23;
        //plugging this in should return 4//
        long exampleA = 4;
        //plugging this in should return 3//
        long exampleB = 10;
        int newNum;
        int a = 0;
        int g = 5;
        for (int i = 0; i < (p - 1); i  ) {
                a = i;
                System.out.println(a);
                newNum = powMod(g, a, exampleP);
                if (newNum == exampleB) break;
            }
        System.out.println(a);
    }
    
    public static int powMod(int g, int exponent, long p) {
        int result = 1;

        while (exponent > 0)
        {
            // exponent is odd
            if (exponent % 2 == 1)
            {
                result = (int) ((result * g) % p);
            }

            // divide exponent in half
            exponent /= 2;

            // square base and take remainder 
            g = (int) ((g * g) % p);
        }
        return result;
    }

CodePudding user response：

p is quite high. About 3 billion.

An int only goes just above 2 billion, it can never reach 3 billion.

In for (int i = 0; i < (p - 1); i ), i is an int, so i is definitely not greater than 2147483647, i cannot ever reach p - 1 which is about 3 billion. i will become negative before that, and start counting up to zero, past zero, up to just over 2 billion, and then still never reach 3 billion. So the loop condition is always true, and the loop never ends.

Simple solution: make i a long.

There are also bugs in powMod, the products (not just the remainders) must be done as longs otherwise they can wrap modulo 2³² before being reduced modulo p (and the product as an int can be negative, which does not combine well with how remainders in Java work with negative inputs). For example (int) ((g * g) % p) should be (int) (((long)g * g) % p) (see below for further modification)

modPow accepts an int as exponent, but if the loop is fixed to actually loop from 0 to p - 1 then the exponent would need to be a long too. Alternatively it could stay an int, but then it needs to be treated as an unsigned integer, that would take more changes to the code.

The highest that an intermediate product (a product before being reduced modulo p) could be is 3267000012² (both operands of the product can be p - 1 at most). That does not fit in 63 bits, so as a long it could be negative, which means you need Long.remainderUnsigned​ instead of the % operator. The product does fit in 64 bits, so there's still no need for BigInteger.
So use something like Long.remainderUnsigned​((long)g * g, p)

In this case you could avoid powMod entirely, and rather than computing modPow(g, i, p) from scratch in every iteration, compute that by multiplying the previous value by g (mod p).