成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	謝朋岳 Hsieh, Peng-Yueh
論文名稱：	例外處理模型及其於長整數程式庫之應用 An Exception Handling Model and Its Application to The Multiple-Precision Integer Library
指導教授：	賴溪松 Laih, Chi-Sung
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2003
畢業學年度：	91
語文別：	英文
論文頁數：	111
中文關鍵詞：	修正的平方演算法、例外處理模型、除錯模型、除錯、標準的平方演算法、長整數、錯誤
外文關鍵詞：	Modified squaring algorithm, Bug, Debug, Debuggin model, Exception handling model, Multiple-precision integer (MPI), Standard squaring algorithm
相關次數：	點閱：81 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著近年來軟體工業的高度發展，團隊共同開發軟體的情況，將會愈來愈普遍。在程式設計的開發中，發生錯誤(Bug)而需要加以除錯(Debug)是屢見不鮮的事。若能有一個具備良好的溝通及傳承經驗的除錯模型，將能促使軟體的團隊開發邁入一新的里程。優良的程式庫(Library)或模組(Module)具備許多重要的因素，其中以正確性及高效能最為重要。利用優良的除錯模型，將能在維持正確性的前提下，實作出高效能的程式庫。

本論文針對此提出一個例外處理模型(Exception Handling Model)，用於程式庫或是模組的除錯上。另一方面，也將此模型應用在我們實驗室的長整數(Multiple-Precision Integer, MPI)程式庫的除錯上，並依據此模型來詳細記錄我們的除錯經驗，以供相關程式庫開發人員加以利用，或作為除錯經驗傳承的一個藍本。

利用本論文所提的例外處理模型來對MPI程式庫進行除錯時，我們發現了一些平方演算法的錯誤。由於標準的平方演算法(Standard Squaring Algorithm, SSA)本身有錯誤[9]，於2000年時，Guajardo及Paar提出修正的平方演算法(Modified Squaring Algorithm, MSA)[7]藉以修正SSA的錯誤；然而我們利用所提的模型偵測到MSA仍有錯誤。本論文不僅對SSA的錯誤機率加以分析，同時指出MSA的錯誤並加以修正。有鑑於SSA錯誤機率高及MSA效能不彰的情形，我們進一步提出一個新的演算法。此演算法經我們的模型檢測為正確，且可大幅地改善平方演算法的效能。

With the rapid development of software industry in the recent years, development of software in teamwork becomes more and more usual. It is not uncommon for a programmer to encounter a bug in development of a library. A good debugging model can help the programmer to identify the bug more systematically and help the sophisticated programmer to pass his experience to others. The good model will be a new milestone for the development of software in teamwork. A good library requires several key factors. Two of them are correctness and high performance. By the good model, programmers will implement a high performance library in the prerequisite of the correctness.

This thesis proposes an exception handling model to be a good reference for assisting programmers to handle exceptions when they implement a library or module. In other aspects, we apply the model to debug our MPI (Multiple-Precision Integer) library. Besides, we record our processing of the debugging that we encountered by using the model. The experiential record will not only provide programmers in the same field an excellent reference to implement MPI library but also offer a blue plot to inherit the experience of debugging.

When debugging the MPI library, we utilize the proposed model to find some bugs of squaring algorithms. Because of the bug of the SSA (Standard Squaring Algorithm), Guajardo and Paar proposed the MSA (Modified Squaring Algorithm) to correct the bug of SSA in 2000. However, we still find a bug exists in the MSA by utilizing the proposed model. This thesis not only analyze error probability of the execution of SSA but also point out the bug of the MSA and correct the bug. In consideration of high error probability of SSA and the low performance of MSA, we propose a new algorithm to greatly improve the performance of squaring. At the same time, the correctness of the proposed algorithm is further verified by utilizing the proposed model.

Chapter 1 Introduction...........................................................1
1 The Concept of Exception Handling............................................1
2 Our Main Contribution........................................................4
3 The Organization of the Thesis..............................................10
Chapter 2 The Operations of Multiple-Precision Integer (MPI)....................11
1 The Structure of Multiple-Precision Integer.................................12
2 Multiple-precision Integer Basic Arithmetic.................................15
3 Fast Modular Algorithm......................................................20
3.1 Modular Reduction.........................................................20
3.2 Modular Multiplication....................................................23
3.3 Modular Exponentiation....................................................24
3.4 Modular Inverse...........................................................29
4 Probabilistic Prime Generation..............................................32
4.1 Prime Number..............................................................32
4.2 Probabilistic Primality Test..............................................32
4.3 Advanced Probabilistic Prime Generation...................................34
Chapter 3 Proposed Squaring Algorithm...........................................38
1 Modified Squaring Algorithm.................................................38
2 Advanced Squaring Algorithm.................................................45
3 Analysis and Simulation.....................................................49
Chapter 4 Constructing an Exception Tree........................................55
1 An Exception Tree...........................................................55
2 The Procedures to Constructing an Exception Tree............................59
3 Definition of Abstract Exception Nodes......................................60
4 The Exception Tree of Our MPI Library.......................................65
5 An Example to Add a New Exception Node......................................67
Chapter 5  Exception Handling Mechanism and Its Application to MPI Library.......69
1 Exception Handling Mechanism................................................69
2 Visible Exception...........................................................72
2.1 System Exception..........................................................73
2.2 Time Consumption Exception................................................77
3 Invisible Exception.........................................................85
3.1 Algorithm Bug Exception...................................................85
3.2 Improper Coding Exception.................................................87
4 An Example to Do Recording Phase............................................98
Chapter 6 Conclusion and Future Work...........................................103
Bibliography...................................................................105
Appendix A.....................................................................108
                                    

[1]
E. Bach and J. Shallit, Algorithmic Number Theory, Volume I : Efficient Algorithms, MIT Press, Cambridge, Massachusetts, 1996.

[2]
P. Barrett, "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor," Advances in Cryptology–CRYPTO '86, LNCS 263, pp. 311-323, 1987.

[3]
A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular Reduction Functions," In D. Stinson, editor, Advances in Cryptology - CRYPTO '93, Santa Barbara, California, LNCS 773, pp. 175-186, Springer, 1994.

[4]
B. B. Brey, Programming the 80286, 80386, 80486 and Pentium-based Personal Computer, Prentice Hall, 1996.

[5]
H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993.

[6]
T. Granlund, "GNU MP: The GNU Multiple Precision Arithmetic Library," version 4.1, 2002. Available from: http://swox.com/gmp/.

[7]
J. Guajardo and C. Paar, "Modified Squaring Algorithm," ECE Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA. Available from: http://www.crypto.ruhr-uni-bochum.de/~guajardo/, http://www.crypto.ruhr-uni-bochum.de/~guajardo/publications/squaringManuscript.pdf.

[8]
D. E. Knuth, The art of computer programming: Seminumerical Algorithms, volume 2, Addison-Wesley, 1981.

[9]
C. K. Koc, "High Speed RSA Implementation," RSA Laboratories, Version 2.0, November 1994.

[10]
D. H. Lehmer, "Euclid’s Algorithm for Large Numbers," American Mathematical Monthly, vol.45, pp. 227-233,1938.

[11]
A. J. Menezes, P. C. V. Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.

[12]
P. L. Montgomery, "Modular Multiplication Without Trial Division," Mathematics of computation, vol. 44, pp. 519-521, 1985.

[13]
R.L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-key Cryptosystems," Communications of ACM, vol. 21, pp. 120-126, 1978.

[14]
K. H. Rosen, Elementary Number Theory and Its Applications 4th, Addison-Wesley, 2000.

[15]
W. C. Yang, P. Y. Hsieh and C. S. Laih, "The Efficient Squaring Large Integers," Submitted to IEEE Trans. on Computers.

[16]
D. Zuras, "On Squaring and Multiplying Large Integers," ARITH-11: IEEE Symposium on Computer Arithmetic, pp. 260-271, 1993.

[17]
D. Zuras, "More on Squaring and Multiplying Large Integers," IEEE Trans. Computers, vol. 43, no. 8, pp. 899-908, Aug. 1994.

[18]
楊吳泉，現代密碼學入門與程式設計，全華科技圖書股份有限公司，1996年。

[19]
賴溪松、韓亮與張真誠，近代密碼學及其應用，旗標出版股份有限公司，2003年。

校內：2004-07-21公開
校外：2004-07-21公開

簡易檢索 / 詳目顯示

相關論文