# 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 on other sites
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 on other sites
Is there nothing faster? This still takes quite a few steps...

##### Share on other sites
No, this is the standard (and I believe fastest) way of doing division mod P

##### 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628306
• Total Posts
2981948

• 10
• 11
• 12
• 11
• 10