Dividing modular prime

This topic is 4864 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 = {Undefined,1,4,5,2,3,6};    return inverses[a];}

to replace the Extended Euclidean Algorithm.

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
18

• 13
• 10
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632997
• Total Posts
3009801
• Who's Online (See full list)

There are no registered users currently online

×