m-진법 모듈러 지수연산
Modular Exponentiation by m-Numeral System
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 의 모듈러 지수연산의 효율적 구현여부로 결정된다. 모듈러 지수연산법에는 표준 이진법이 최선의 선택으로 알려져 있다. 그러나 큰 자리수의 에 대해서는 이 보다 효율적으로 적용된다. 본 논문에서는 , 인 경우 를 -진법으로 변환시켜 수행하는 방법과 -진법 수행과정에서 결과 값이 또는 가 발생하는 경우 곱셈 수행횟수를 획기적으로 줄이는 방법을 제안하였다.
Abstract
The performance and practicality of cryptosystem for encryption, decryption, and primality test is primarily determined by the implementation efficiency of the modular exponentiation of . To compute , the standard binary squaring still seems to be the best choice. But, the method is more efficient in large bits. This paper suggests -numeral system modular exponentiation. This method can be apply to , . And, also suggests the another method that is exit the algorithm in the case of the result is 1 or .
참고문헌 (10)
- T. H. Cormen, "Introduction to Algorithms 2nd Edition" (2005), McGrew-Hill Book Company
- M. Alfred, "Handbook of Applied Cryptography" (1996), CRC Press
- S. T. Klein, "Should One Always Use Repeated Squaring for Modular Exponentiation", Information Processing Letters, 106(6), pp.232~237 (2008)
- D. M. Gordon, "A Survey of Fast Exponentiation Methods", Journal of Algorithms, 27(1), pp.129~146 (1998)
- P. Montgomery, "Modular Multiplication Without Trial Division", Math. Computation, 44, pp.519~521 (1985)
- G. Saldamli, "Spectral Modular Exponentiation", Proc. of the 18th IEEE Symposium on Computer Arithmetic, pp.123~132 (2007)
- V. Gopal, "Fast and Constant-Time Implementation of Modular Exponentiation", 28th International Symposium on Reliable Distributed Systems, Niagara Falls (2009)
- Modular Exponentiation Algorithm Analysis for Energy Consumption and Performance, "L. Zhong", Dept. of Electrical Engineering, Princeton University, ~, pp.CE-01-ZJL (2001)
- N. Nedjah, "Efficient Pre-Processing for Large Window-Based Modular Exponentiation Using Ant Colony", Informatica, 29, pp.151~161 (2005)
- "Modular Exponentiation, in Arithmtica Computacional"[URL]