Different from the extended Euclidean algorithm which can compute directly only the multiplicative inverse of an element in Zm^＊ and the greatest common divisor of two integers, a recursive algorithm called REESSE is...Different from the extended Euclidean algorithm which can compute directly only the multiplicative inverse of an element in Zm^＊ and the greatest common divisor of two integers, a recursive algorithm called REESSE is designed by the authors, which can not only seek directly the multiplicative inverse and the greatest common divisor, but also solve directly a simple congruence for general solutions. This paper presents the definition and the two valuable properties of a simple congruence, analyzes in detail the reduction and recursion process of solving simple congruences, induces the recursive formula for solving simple congruences, and describes formally and implements in C language the recursive algorithm. At last, the paper compares REESSE with the extended Euclidean algorithm in thought, applicability and time complexity.展开更多
基金Supported by the National Key Promotion Plan for Science and Technology Results (2003EC000001)
文摘Different from the extended Euclidean algorithm which can compute directly only the multiplicative inverse of an element in Zm^＊ and the greatest common divisor of two integers, a recursive algorithm called REESSE is designed by the authors, which can not only seek directly the multiplicative inverse and the greatest common divisor, but also solve directly a simple congruence for general solutions. This paper presents the definition and the two valuable properties of a simple congruence, analyzes in detail the reduction and recursion process of solving simple congruences, induces the recursive formula for solving simple congruences, and describes formally and implements in C language the recursive algorithm. At last, the paper compares REESSE with the extended Euclidean algorithm in thought, applicability and time complexity.
