1-1hit |
An algorithm is presented to solve the congruence equation of the type AX B (mod M) using Fermat's theorem, where M is any prime. It uses only integer multiplication mod M. If p is an integer such that 2p11M2p1, and M3 or p3, the number N of necessary multiplications mod M satisfies p1N2p2.