Modification of Euclidian Algorithm for Solving ModularEquations

Authors: I. Ž. Milovanović, Ć. B. Dolićanin, M. K. Stojčcev, E. I. Milovanović

Keywords: Euclidian algorithm; residue; Chinese reminder theorem

Abstract:

In this paper we propose a modification of extended Euclid’s algorithms with aim to reduce the number of iteration steps when solving modular equations. Obtained result is used to solve the system of linear modular equations in one variable (Chinese Remainder Theorem). The proposed modification is convenient for parallel implementation.

References:

[1] Akl, S.G. (1989) Design and analysis of parallel algorithms. London: Prentice-Hall [2] Akritas, A.G. (1989) Elements of computer algebra with applications. New York: John Wiley and Sons [3] Anderson, J.M. (2004) Discrete mathematics with combinatorics. New Jersey: Prentice Hall [4] Borodin, A., Gathen, J., Hopcroft, J. (1982) Fast parallel matrix and GCD computations. u: Annual Symposium on Foundations of Computer Science (23rd), Proc., New York: IEEE, 65-71 [5] Brent, R.P., Kung, H.T. (1982) Systolic VLSI arrays for polynomial GCD computation. Carnegie-Mellon University, Report CMU-CS-82-118 [6] Brent, R.P., Kung, H.T., Luk, F.T. (2010) Some linear-time algorithms for systolic arrays. arXiv: 1004.3716V1, [CS.DS], 21.Apr [7] Knuth, D.E. (1981) The art of computer programming. Reading, Massachusetts: Addison-Wesley [8] Kuo, S.M., Lee, B.H., Tian, W. (2006) Real-time digital signal processing: Implementations and applications. John Wiley & Sons [9] Stojcev, M.K., Milovanovic, E.I., Milovanovic, I.Z. (2012) A Unified Approach in Manipulation with Modular Arithmetic. 2012 28th International Conference On Microelectronics (Miel), : 423-426