2016/10/04 by Guangwu Xu, Bao Li, Xu, Guangwu +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Polynomial and algebraic computation #Rough Sets and Fuzzy Logic #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1610.01175
openalex publication_date 2016/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Modulo inverse is an important arithmetic operation. Many famous algorithms in public key cryptography require to compute modulo inverse. It is argued that the method of DaYan deriving one of Jiushao Qin provides the most concise and transparent way of computing modulo inverse. Based on the rule of taking the least positive remainder in division, this paper presents a more precise algorithmic description of the method of DaYan deriving one to reflect Qin's original idea. Our form of the algorithm is straightforward and different from the ones in the literature. Some additional information can be revealed easily from the process of DaYan deriving one, e.g., the invariance property of the permanent of the state, natural connection to continued fractions. Comparison of Qin'a algorithm and the modern form of the Extended Euclidean algorithm is also given. Since DaYan deriving one is the key technical ingredient of Jiushao Qin's DaYan aggregation method (aka the Chinese Remainder Theorem), we include some explanation to the latter as well.