So I'm working on a program that'll allow ElGamal public key encryption on the 83/84/+/SE. I've got the key generation stage and the encryption stage complete, but the decryption method isn't working.

ElGamal's security is based on the difficulty of solving discrete logarithms, rather than integer factorization like RSA, and the way it works is like this:

Key generation: Bob takes prime number p, a random number g between 1 and (p-1), and decryption key x, which is also between 1 and (p-1). Bob then computes y:

(1)Then Bob sends g, p, and y to Alice.

Encryption: Alice takes her message, number m, and selects a random value k. She then calculates a:

(2)Alice also computes b:

(3)She sends a and b to Bob, and this is where I'm having the problem. The decryption algorithm works like this, and m should be the result:

(4)In all of the other stages, I used a For( loop (inefficient, I know) to keep the exponents from causing an over flow, since the modulus keeps the numbers low. However, I don't know how to do that in the decryption stage without compromising security (by making x lower and thus more predictable) or getting an overflow error (by calculating b/a^x first and then modding it). I tried things like modding a^x and b separately first and then dividing the modded b by the modded a^x, and leaving b alone and only modding a^x, but all either got me was a fraction or decimal instead of the message m (an integer).

I know I'm doing it wrong, and I'd very much appreciate a solution (possibly an alternative to the primitive exponentiation-by-looping method I've been using), and then I could post the algorithm when I'm done, allowing people to finally use a decent public key algorithm for the 83/84/+/SE Basic family.