암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 $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가 발생하는 경우 곱셈 수행횟수를 획기적으로 줄이는 방법을 제안하였다.
암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 $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가 발생하는 경우 곱셈 수행횟수를 획기적으로 줄이는 방법을 제안하였다.
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 be...
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.
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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 d-ary이외에는 적용이 불가한 것으로 판단된다. 그러나 임의로 5진법을 적용해 보자. 18206926 = 14130110201(5)에 대해 사전처리는 a→a2→a4→a5, a2→a3로 4회, b10b9 = 14에서 b10 = 1로 처리하지 않으면 (a5)a4 = a9으로 1회, 나머지 b8부터 b0까지 9개 각각에 대한 누승에 3회로 27회, bi ≠ 0인 6개에 대한 6회 곱셈을 수행하여 4+1+27+6=38회를 수행하여 d-ary보다 효율적이지 못하다.
본 논문은 암호학의 암호 생성과 해독, 소수 판별법에 일반적으로 적용되는 d-ary법의 곱셈 횟수를 줄일 수 있는 방법을 제안하였다.
-진법의 d-ary법에서 2 ≤ m ≤ 16의 m-진법을 적용할 수 있도록 일반화된 알고리즘으로 확장하였다. 또한, d-ary법 적용과정에서 알고리즘을 보다 빨리 종료시킬 수 있는 방법도 제시하였다.
제안 방법
에 대해 알고리즘을 적용한 결과는 (그림 5)에 제시하였다. 표준화된 이진법은 6회의 제곱과 4회의 곱셈 수행으로 총 10회를 수행하였다. 반면에 빠른 이진법은 첫 번째 제곱에서 85를 얻어 단지 1회로 단축시킬 수 있었다.
제안된 알고리즘은 기존의 2d-진법의 d-ary법에서 2 ≤ m ≤ 16의 m-진법을 적용할 수 있도록 일반화된 알고리즘으로 확장하였다.
첫 번째로, 표준 이진법 (1-ary)의 곱셈 횟수를 줄일 수 있는 효율적으로 d-ary법을 제안하였다. 이는 ab에서 b의 이진 자리수 k에 영향을 받음을 알 수 있었으며, 자리수 범위별로 이론상으로 최적의 d-ary법을 도출하였다.
(mod n) 계산시 b의 값에 따라 표준 이진법보다 다른 진법을 적용하면 곱셈 (누승+곱셈) 횟수를 감소시킬 수 있음을 보인다. 따라서 본 논문에서는 b≡0(mod m), (m = 3,5,6,7,10,12)이면 m -진법을, 그렇지 않으면 d-ary (2d, d = 1,2,3,4)을 적용한 일반화된 m-진법을 제안한다. 2장에서는 d-ary법을 고찰한다.
이론/모형
표준 이진법의 곱셈 수행 횟수를 줄일 수 있는 방법은 다음과 같이 m-진법을 적용하고 특정 상황이 발생하면 알고리즘을 종료시키는 방법을 적용한다. 이를 “빠른 지수연산법”이라 하자.
성능/효과
(mod n) 계산시 b의 값에 따라 표준 이진법보다 다른 진법을 적용하면 곱셈 (누승+곱셈) 횟수를 감소시킬 수 있음을 보인다. 따라서 본 논문에서는 b≡0(mod m), (m = 3,5,6,7,10,12)이면 m -진법을, 그렇지 않으면 d-ary (2d, d = 1,2,3,4)을 적용한 일반화된 m-진법을 제안한다.
(1) ab에 대해 b≡0 (mod m)인 m-진법을 적용하면 이진법보다 곱셈 수행 횟수를 줄일 수도 있다.
두 번째로, b≡0 (mod m), (m = 3,5,6,7,10,12)인 경우, d-ary에 비해 m-진법을 적용하면 d-ary의 곱셈 횟수를 축소시킬 수 있음을 보였다.
세 번째로, d-ary를 적용하는 과정에서 ax(mod n) ≡ 1 또는 ax(mod n) ≡ a가 발생하면 곱셈 횟수를 보다 축소 시킬 수 있음을 보였다.
첫 번째로, 표준 이진법 (1-ary)의 곱셈 횟수를 줄일 수 있는 효율적으로 d-ary법을 제안하였다. 이는 ab에서 b의 이진 자리수 k에 영향을 받음을 알 수 있었으며, 자리수 범위별로 이론상으로 최적의 d-ary법을 도출하였다.
결론적으로, b≡0 (mod m) , 2 ≤ m ≤ 16을 계산하여 d-ary 이외의 3,5,6,7,9,10,11,12,13,14,15중에서 누승 곱셈횟수가 4까지인 3,5,6,7,9,10,12의 m-진법을 적용하면 이진법의 곱셈 수행횟수를 줄일 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
빠른 지수연산법은 어떤 방법을 말하는가?
표준 이진법의 곱셈 수행 횟수를 줄일 수 있는 방법은 다음과 같이 m-진법을 적용하고 특정 상황이 발생하면 알고리즘을 종료시키는 방법을 적용한다. 이를 “빠른 지수연산법”이라 하자.
밑 a, 지수 b의 연산을 무엇이라고 부르는가?
밑 a, 지수 b의 연산을 지수연산 (exponentiation)이라 하며, ab을 n으로 나눈 나머지를 구하는 ab(mod n)을 모듈러 지수 연산 (modular exponentiation)이라 한다. 모듈러 지수연산은 암호학 (cryptography) 분야의 암호 생성과 해독과 더불어 소수판별법 (primality test, PT)에도 널리 사용되고 있다[1,2].
모듈러 지수연산은 어디서 널리 사용되고 있는가?
밑 a, 지수 b의 연산을 지수연산 (exponentiation)이라 하며, ab을 n으로 나눈 나머지를 구하는 ab(mod n)을 모듈러 지수 연산 (modular exponentiation)이라 한다. 모듈러 지수연산은 암호학 (cryptography) 분야의 암호 생성과 해독과 더불어 소수판별법 (primality test, PT)에도 널리 사용되고 있다[1,2].
참고문헌 (10)
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 2nd Edition, McGrew-Hill Book Company, 2005.
M. Alfred, P. C. Oorschot, AND S. A. Vanstone, "Handbook of Applied Cryptography," CRC Press, 1996.
S. T. Klein, "Should One Always Use Repeated Squaring for Modular Exponentiation?." Information Processing Letters, Vol. 106, Issue. 6, pp. 232-237, 2008.
G. Saldamli and C. K. Koc, "Spectral Modular Exponentiation," Proc. of the 18th IEEE Symposium on Computer Arithmetic, pp. 123-132, 2007.
V. Gopal, J. Guilford, E. Ozturk, W. Feghali, G. Wolrich, and M. Dixon, "Fast and Constant-Time Implementation of Modular Exponentiation," 28th International Symposium on Reliable Distributed Systems, Niagara Falls, New York, U.S.A., http://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf 2009.
L. Zhong, "Modular Exponentiation Algorithm Analysis for Energy Consumption and Performance," Technical Report CE-01-ZJL, Dept. of Electrical Engineering, Princeton University, 2001.
N. Nedjah and L. M. Mourelle, "Efficient Pre-Processing for Large Window-Based Modular Exponentiation Using Ant Colony," Informatica, Vol. 29, pp. 151-161, 2005.
F. R. Henriquez, "Modular Exponentiation," Arithmetica Computacional, http://delta.cs.cinvestav.mx/~francisco/arith/ expo.pdf.
이 논문을 인용한 문헌
저자의 다른 논문 :
활용도 분석정보
상세보기
다운로드
내보내기
활용도 Top5 논문
해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다. 더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.