Sign in to follow this  
paulbird

Dividing modular prime

Recommended Posts

paulbird    182
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
jperalta    356
If P is prime, A < P, B < P, A != 1, B != 1 then A and B are relatively prime to P and a solution to the problem does exist.

1. Find A^(-1) mod P which is a relatively trivial task (ref: Extended Euclidean Algorithm)

2. Multiply B by A^(-1) and reduce mod P. <-- Your solution

Share this post


Link to post
Share on other sites
jperalta    356
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