Sign in to follow this  

Dividing modular prime

Recommended Posts

Can anyone think of the quickest way (in terms of computer speed) to find the answer to this: If A,B and P are known (and P is prime) what is X in this equation:
A * X  =  B  (mod P)
A, B, X, and P can be assumed to be 32-bit integers. It doesn't matter if the solution uses floating point numbers or anything as long as the answer is correct. I can only this of a way of doing it by using a loop and trying all the numbers from 1 to P-1.

Share this post

Link to post
Share on other sites
Actually... if P is "small" you could do something like this (for P = 7):

int GetInverse(int a) {
int inverses[P] = {Undefined,1,4,5,2,3,6};
return inverses[a];

to replace the Extended Euclidean Algorithm.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this