| REESSE Unified Recursive Algorithm for Solving Three Computational Problems |
| |
| 作者姓名： | SU Shenghui YANG Bingru |
| |
| 作者单位： | School of Information Engineering, University of Scienceand Technology Beijing, Beijing 100083, China |
| |
| 基金项目： | Foundation item： 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.
|
| 关 键 词： | 递归算法 计算机 算法理论 乘性 |
| 文章编号： | 1007-1202（2007）01-0172-05 |
| 收稿时间： | 2006-05-20 |
REESSE unified recursive algorithm for solving three computational problems |
| |
| SU Shenghui YANG Bingru.REESSE Unified Recursive Algorithm for Solving Three Computational Problems[J].Wuhan University Journal of Natural Sciences,2007,12(1):172-176. |
| |
| Authors: | Su Shenghui Yang Bingru |
| |
| Institution: | (1) School of Information Engineering, University of Science and Technology Beijing, Beijing, 100083, China |
| |
| Abstract: | Different from the extended Euclidean algorithm which can compute directly only the multiplicative inverse of an element in Z *m 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 congru- ence 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 con- gruences, induces the recursive formula for solving simple con- gruences, 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. |
| |
| Keywords: | simple congruence recursive algorithm general solution multiplicative inverse greatest common divisor |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
