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


Cover Contents Index Main page

last modified 30th July 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic