頁籤選單縮合
| 題 名 | New Method of Computing Multiplicative Inverse=乘法反元素新計算方法 |
|---|---|
| 作 者 | 王中全; | 書刊名 | 中州學報 |
| 卷 期 | 23 民95.06 |
| 頁 次 | 頁69-77 |
| 分類號 | 311.1 |
| 關鍵詞 | 乘法反元素; 小費馬定理; 延伸歐幾里德演算法; 尤拉演算法; 最大公因數; Multiplicative inverse; Euler's generation of fermat's little theorem; Extended euclidean algorithm; Euclid's algorithm; GCD; |
| 語 文 | 英文(English) |
| 中文摘要 | 在過去，當人們提到數論中的乘法反元素時他們總會想到小費馬定理 (Little Fermat's Theorem)，延伸歐幾里德演算法與尤拉演算法逆向推導方式求得。然而，更多人仍沿用一般求最大公因數 (GCD-Greatest Common Divisor) 輾轉相除回推至兩原始整數的方法求之。主要的理由是，(1) 小費馬定理雖然關念簡單但不適合實做。(2) 延伸歐幾里德演算法為能關連到原始的兩整數而記錄每一除法步驗，而使得原本簡單的尤拉演算法變得複雜。雖然用求最大公因數 (GCD-Greatest Common Divisor) 的輾轉相除回推至兩原始整數的方法依然繁瑣，但卻一直都未能有有效的方法來求出乘法反元素。為了改善這些缺點，本新計算方法能在兩步驟就可求出乘法反元素，第一、利用尤拉定理的簡單性，僅用一堆疊記錄每一除法的商。第二、導出一有效簡單的演算法快速求出乘法反元素。 |
| 英文摘要 | In past, as people mentioned multiplicative inverse (inverse for short) in Numerical Theorem, they always think of Euler's Generation of Fermat's Little Theorem, Extended Euclidean Algorithm and reverse deduct from Euclid's algorithm. However, most people still use reverse deductive expression from GCD (Greatest Common Divisor) to the two original integers. The main reasons are (1) Euler's Generation of Fermat's Little Theorem adopting exponent expression is not good for practicing. (2) Since Extend Euclidean Algorithm tries to keep every division step related to the original two integers, it makes the concise Euclid's Algorithm complicated. Although reverse deductive expression from GCD to the two original integers is not easy to get the final inverse, there is no good method to support it. To improve the weakness, it could be solved the inverse into two stages. First, keep the concise property of Euclid Algorithm in intuitive way by only using one stack to record all quotients in every division step. Second, deduce an efficient algorithm and easily use it to get the final inverse. |
本系統中英文摘要資訊取自各篇刊載內容。