m-진법 모듈러 지수연산 = Modular Exponentiation by m-Numeral System

국문 초록 (Abstract)

암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 $a^b$(mod n)의 모듈러 지수연산의 효율적 구현여부로 결정된다. 모듈러 지수연산법에는 표준 이진법이 최선의 선택으로 알려져 있다. 그러나 큰 자리수의 b에 대해서는 d-ary, (d=2,3,4,5,6)이 보다 효율적으로 적용된다. 본 논문에서는 $b{\equiv}0$(mod m), $2{\leq}m{\leq}16$인 경우 b를 m-진법으로 변환시켜 수행하는 방법과 m-진법 수행과정에서 결과 값이 1 또는 a가 발생하는 경우 곱셈 수행횟수를 획기적으로 줄이는 방법을 제안하였다.

다국어 초록 (Multilingual 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 $a^b$(mod n). To compute $a^b$(mod n), the standard binary squaring still seems to be the best choice. But, the d-ary, (d=2,3,4,5,6) method is more efficient in large b bits. This paper suggests m-numeral system modular exponentiation. This method can be apply to$b{\equiv}0$(mod m), $2{\leq}m{\leq}16$. And, also suggests the another method that is exit the algorithm in the case of the result is 1 or a.

참고문헌 (Reference)

1 G. Saldamli, "Spectral Modular Exponentiation" 123-132, 2007

2 S. T. Klein, "Should One Always Use Repeated Squaring for Modular Exponentiation" 106 (106): 232-237, 2008

3 P. Montgomery, "Modular Multiplication Without Trial Division" 44 : 519-521, 1985

4 F. R. Henriquez, "Modular Exponentiation, in Arithmtica Computacional"

5 L. Zhong, "Modular Exponentiation Algorithm Analysis for Energy Consumption and Performance" Dept. of Electrical Engineering, Princeton University 2001

6 T. H. Cormen, "Introduction to Algorithms 2nd Edition" McGrew-Hill Book Company 2005

7 M. Alfred, "Handbook of Applied Cryptography" CRC Press 1996

8 V. Gopal, "Fast and Constant-Time Implementation of Modular Exponentiation" 2009

9 N. Nedjah, "Efficient Pre-Processing for Large Window-Based Modular Exponentiation Using Ant Colony" 29 : 151-161, 2005

10 D. M. Gordon, "A Survey of Fast Exponentiation Methods" 27 (27): 129-146, 1998