Solving modular linear equations
PROBLEM
Find solutions to the equations MOD(A*X,N)=MOD(B,N)
IMPLEMENTATION
Unit: program
Parameters:
an arbitrary integers A, B, a positive integer N
Output: program displays on the screen all solutions to the equations
MOD(A*X,N)=MOD(B,N)
Interface: functions EXEUCLID and MOD
/* Solving modular linear equations */
parse arg A B N
parse value EXEUCLID(A, N) with D X Y
if MOD(B, D) = 0
then do
X = MOD(X * (B / D), N)
do I = 0 to D - 1
say MOD(X + I * (N / D), N)
end
end
else say "No solutions"
exit
|
CONNECTIONS
Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms The MIT Press, Cambridge, 1990
|
