Solving a Single Congruence Equation

[Bunuel66]

I apologize for being too lazy for analyzing the algorithm given in the topic. Then please, forgive me if the following discussion is redundant.

Strictly from an algorithmic standpoint (I haven't checked in terms of speed), it could be more straightforward to use Fermat's little theorem who says in a nutshell that if A is prime relatively to N then A^(N-1)=1 Mod N which is equivalent to say that A^(N-2) is an inverse of A Mod N.
Then, as the equation is unchanged if we consider A Mod N in case A>N, the solution is : x=B*A^(N-2) Mod N.
As A^(N-2) can be computed Mod N at every step the risk of overflow is reduced.
In addition, for reducing the number of times that the modulo is computed one can go through a test on the calculation of A^n and compute the modulo only when the product is near the accuracy limit of the machine.

Example: with the given equation 5*x=3 Mod 17 one gets x=3*5^(15) Mod 17
5^15 Mod 17=7 and 3*7 Mod 17=4

There is another approach using the extended Euclid Algorithm and the Bezout/Merignac theorem but it will be more complex to program. This alternate approach will be the faster at the price of an expense in memory and the use of a structure array like ;-(

My 2 cents...