[논문]제곱-나눗셈 모듈러 지수연산법

이상운

doi:10.9708/jksci.2013.18.4.123

초록
AI-Helper

암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 $a^b$ (mod m)의 모듈러 지수연산의 효율적 구현여부로 결정된다. 모듈러 지수연산법에는 제곱-곱셈 방식의 표준 이진법이 최선의 선택으로 알려져 있다. 그러나 큰 자리수의 b에 대해서는 사전처리를 하는 n-ary, ($n{\geq}2$)이 보다 효율적으로 적용된다. 본 논문에서는 모듈러 지수 나눗셈 방법을 적용한 제곱-나눗셈법과 사전처리 없는 n-ary 제곱-나눗셈법을 제안하였다. 제곱-나눗셈법은 b가 $2^k+2^{k-1}$에 근접한 값 또는 $2^{k+1}$에 근접한 경우 수행횟수 측면에서 가장 효율적임을 알 수 있었다. 나머지 값들에 대해서는 사전처리 없는 n-ary 제곱-나눗셈법을 적용하는 것이 사전처리를 하는 일반적인 n-ary법에 비해 수행횟수 측면에서 효율적임을 보였다.

Abstract ▼ AI-Helper

The performance and practicality of cryptosystem for encryption, decryption, and primality test are primarily determined by the implementation efficiency of the modular exponentiation of $a^b$ (mod m). To compute $a^b$ (mod m), the standard binary squaring (square-and-multiply)...

The performance and practicality of cryptosystem for encryption, decryption, and primality test are primarily determined by the implementation efficiency of the modular exponentiation of $a^b$ (mod m). To compute $a^b$ (mod m), the standard binary squaring (square-and-multiply) still seems to be the best choice. However, in large b bits, the preprocessed n-ary, ($n{\geq}2$ method could be more efficient than binary squaring method. This paper proposes a square-and-divide and unpreprocessed n-ary square-and-divide modular exponentiation method. Results confirmed that the square-and-divide method is the most efficient of trial number in a case where the value of b is adjacent to $2^k+2^{k-1}$ or to. $2^{k+1}$. It was also proved that for b out of the beforementioned range, the unpreprocessed n-ary square-and-divide method yields higher efficiency of trial number than the general preprocessed n-ary method.

Keyword

참고문헌 (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.

상세보기
D. M. Gordon, "A Survey of Fast Exponentiation Methods," Journal of Algorithms, Vol. 27, No. 1, pp. 129-146, 1998.

상세보기
P. Montgomery, "Modular Multiplication Without Trial Division," Math. Computation, Vol. 44, pp. 519-521, 1985.

상세보기
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., 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," Arithme'tica Computacional, http://delta.cs.cinvestav.mx/-francisco/arith/expo.pdf.

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 제곱-나눗셈 모듈러 지수연산법
Square-and-Divide Modular Exponentiation 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

Keyword

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 제곱-나눗셈 모듈러 지수연산법 Square-and-Divide Modular Exponentiation 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Keyword

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

이상운 (191)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 제곱-나눗셈 모듈러 지수연산법
Square-and-Divide Modular Exponentiation 원문보기

초록
AI-Helper

활용도 Top5 논문