모듈러형 지수화

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '모듈식 지수화'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2018년 2월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

모듈러형 지수란 계수 상에서 실행되는 지수입니다.이것은 컴퓨터 과학, 특히 Diffie-Hellman 키 교환 및 RSA 공용/개인 키 모두에서 사용되는 공개 키 암호화 분야에서 유용합니다.

모듈러형 지수란 정수 b(기준)를 거듭제곱 e(지수)로 올리고 양의 정수 m(계수)로 나눈 나머지를 말합니다. 즉, c = b^e mod m입니다.나눗셈의 정의에서 보면 0 µc < m이 된다.

예를 들어, b = 5, e = 3 및 m = 13일 때, 5 = 125를 13으로 나누면³ 나머지 c = 8이 남습니다.

확장 유클리드 알고리즘을 사용하여 모듈로 m의 모듈러 곱셈 역d를 구함으로써 모듈러 곱셈은 음의 지수 e로 실행할 수 있다.즉, 다음과 같습니다.

c = b^e mod m = d^−e mod m. 여기서 e < 0 및 b ⋅ d 1 1 ( mod m ) 。

모듈러형 지수를 사용하면 매우 큰 정수에서도 효율적으로 계산할 수 있습니다.한편, 모듈러 이산 로그의 계산, 즉 b, c, m이 주어졌을 때 지수 e를 찾는 것은 어려운 것으로 생각된다.이 단방향 함수 동작으로 인해 모듈러형 지수화는 암호화 알고리즘에서 사용할 수 있습니다.

직접법

모듈러 지수를 계산하는 가장 직접적인 방법은 b를 직접 계산한^e 다음 이 숫자 modulo m을 취하는 것입니다.b = 4, e = 13, m = 497일 때 c를 계산해 보십시오.

c 4¹³ 4 (mod 497)

계산기를 사용하여 4를 계산하면¹³ 67,108,864가 됩니다.이 값 모듈로 497을 이용하여 응답 c를 445로 결정한다.

b의 길이는 1자리, e의 길이는 2자리입니다만, b의^e 길이는 8자리입니다.

강력한 암호화에서는 b는 보통 최소 1024비트입니다.^[1]b = 5 × 10⁷⁶ 및 e = 17을 고려하며, 둘 다 완전히 합리적인 값이다.이 예에서는 b의 길이는 77자리, e의 길이는 2자리입니다만, 값^e b의 길이는 1,304자리입니다.이러한 계산은 현대의 컴퓨터에서는 가능하지만, 그러한 숫자의 순전한 크기 때문에 계산 속도가 상당히 느려집니다.b와 e가 더욱 증가하여 보안이 향상됨에 따라 값^e b는 다루기 어려워집니다.

지수화를 실행하는 데 걸리는 시간은 동작 환경과 프로세서에 따라 달라집니다.위에서 설명한 방법을 완료하려면 O(e) 곱셈이 필요합니다.

메모리 효율이 뛰어난 방법

숫자를 작게 유지하려면 모듈러 방식의 추가 절감 작업이 필요하지만, 크기가 작아지면 각 작업이 더 빨라지고 전체 시간 및 메모리가 절약됩니다.

이 알고리즘은 ID를 사용합니다.

(a µb) mod m = [(a mod m) µ (b mod m)] mod m

변경된 알고리즘은 다음과 같습니다.

1. c = 1, e440 = 0으로 설정합니다.
2. e†를 1씩 늘립니다.
3. c = (b µ c) mod m을 설정합니다.
4. e' < e인 경우 스텝2로 넘어갑니다그 이외의 경우 c에는 c µ^e b(mod m)에 대한 올바른 솔루션이 포함됩니다.

스텝 3을 통과하는 모든 패스에서는 방정식 cµb^e′(mod m)가 참임을 유의하십시오.스텝 3이 e회 실행되면 c에는 원하는 답변이 포함됩니다.요약하면, 이 알고리즘은 기본적으로 e'가 e'에 도달할 때까지 e'를 1씩 카운트하고, 1을 추가할 때마다 b의 곱셈과 모듈로 연산을 수행합니다(결과를 작게 유지하기 위해).

예제 b = 4, e = 13 및 m = 497이 다시 제시됩니다.알고리즘은 스텝 3을 13회 통과합니다.

• e140 = 1. c = (1 ⋅ 4 ) mod 497 = 4 mod 497 = 4.
• e440 = 2. c = (4µ4) mod 497 = 16 mod 497 = 16.
• e440 = 3. c = (16µ4) mod 497 = 64 mod 497 = 64.
• e440 = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e440 = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e490 = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e480 = 7.c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e420 = 8.c = (420) mod 497 = 1920 mod 497 = 429.
• e440 = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e440 = 10.c = (440) mod 497 = 900 mod 497 = 403.
• e140 = 11.c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e440 = 12.c = (440) mod 497 = 484 mod 497 = 484.
• e440 = 13.c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

따라서 첫 번째 방법과 마찬가지로 c의 최종 답은 445입니다.

첫 번째 방법과 마찬가지로 O(e) 곱셈을 완료해야 합니다.그러나 이러한 계산에 사용되는 숫자는 첫 번째 알고리즘의 계산에 사용된 숫자보다 훨씬 작기 때문에 이 방법에서는 계산 시간이 최소 O(e)의 계수만큼 감소한다.

의사 코드에서는, 이 방식을 다음의 방법으로 실행할 수 있습니다.

함수 modular_pow(base, 지수, 계수)는 계수 = 1이면 e_prime = 0 to exponent-1 do c : = (c * base) 계수 반환 c입니다.

오른쪽에서 왼쪽으로 이진법

세 번째 방법은 이전 방법과 동일한 메모리 풋프린트를 유지하면서 모듈러 인덱싱을 실행하는 동작의 수를 대폭 줄인다.이는 이전 방법과 제곱에 의한 지수화(이항 지수화라고도 함)라고 불리는 보다 일반적인 원리의 조합입니다.

첫째, 지수 e를 2진 표기로 변환해야 합니다.즉, e는 다음과 같이 쓸 수 있습니다.

${\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}$

이러한 표기법에서 e의 길이는 n비트입니다.a는_i 임의의 i에 대해 값 0 또는 1을 취할 수 있으므로 0 µ i < n. 정의에 따르면_{n − 1} a = 1입니다.

값^e b는 다음과 같이 쓸 수 있습니다.

$\displaystyle b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\display_{i}^{n-1}b^{a_{i}2^{i}}}$

따라서 솔루션 c는 다음과 같습니다.

${\displaystyle c\equiv \display_{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}}$

유사 코드

다음으로 Bruce Schneier의 ^[2]Applied Cryptography에 기초한 의사 코드의 예를 나타냅니다.입력 정보base,exponent,그리고.modulus위의 방정식에서 b, e, m에 대응합니다.

만약 탄성률=1그러면 0를 기능 modular_pow(기지 지수, 탄성률)::지수>(-1모듈 러스)*(-1모듈 러스):=1베이스:=기본mod 탄성 계수이고;만약(지수 모드 2== 1) 다음 결과 0:=(결과*기지)mod 탄성률 지수:)지수>>1bas 기지 결과 넘치지 않는다는 것이다.e:=(base * base) 계수 반환 결과

루프를 처음 시작할 때 코드 변수가baseb에 해당합니다.단, 코드의 세 번째 줄에 반복 스쿼어링이 이루어지면 모든 루프가 완료되면 변수가base는 b mod m에²ⁱ 해당합니다.i는 루프가 반복된 횟수입니다.(이로 인해 i는 이진수 지수의 다음 작동 비트가 됩니다.exponent여기서 가장 중요하지 않은 비트는exponent₀).

코드의 첫 번째 행은 단순히${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{\mathrm{i}}}}$ ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{0}}}$ ${\displaystyle \underset{}{\overset{}{}}{}^{}}$ - ${\displaystyle {{}_{}{\mathrm{}}^{}}^{}}$ b${\displaystyle {{}^{}}^{}{a^{}}^{}}$ ${\displaystyle 2}$ ${\displaystyle i}$ (${\displaystyle }$mod$$m ) { $displaystyle$\$display$ _ { i$$=$$0$}^{ a$_ { $i$} 2^ { i } { \$pmod$ { m$}$에서의 곱셈을 수행하며, a가 0일 경우 실행 중인 코드의 합계는 1을 곱하지 않습니다.대신 가 1인 경우 변수는base(원기치의 b²ⁱ mod m을 포함한다)는 간단히 곱한다.

이 예에서 기저 b는 지수 e = 13으로 상승합니다.지수는 이진법으로 1101입니다.4자리 이진수가 있으므로 루프는 값₀ a = 1, a = 0, a₁₂ = 1, a = 1로₃ 4번 실행됩니다.

$먼저$ $R을$$$1로 초기화하고 변수 x의 b 값을 유지합니다.

${\displaystyle R}$ ${\displaystyle \leftarrow }$ ${\displaystyle 1}$( ${\displaystyle =}$ ${\displaystyle {}^{}{0\mathrm{}}^{}}$ )${\displaystyle 및}$ x ${\displaystyle \leftarrow }$ {\$displaystyle$ R$\left 화살표$ 1$,(=b^{0}){\text{및$}}$x\left 화살표$b$\}.$

스텝 1) 비트1은 1이므로 R ${\displaystyle \leftarrow }$ ${\displaystyle Rx}$x ( $=$ ${\displaystyle {b\mathrm{}}^{}}$1) ${{displaystyle$ R$\left 화살표$ R$\cdot$ x$\cdot$ text{ }}(=$b^{1$로 설정합니다.

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {x\mathrm{}}^{}{}^{}}$2 ( $=$ ${\displaystyle {}^{}{2\mathrm{}}^{}}$ $)({displaystyle$x\$left 화살표$ x$^{2}{\text${}}(=$b^{2$

스텝 2) 비트2는 0이므로 R을 리셋하지 마십시오.

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$ ( $=$ ${\displaystyle {b\mathrm{}}^{}}$4 $){$ $displaystyle x\left arrow$ x$^{2}{\$text${}}(=b^{$4$\})\}.$

3단계) 비트3은 1이므로 ${\displaystyle R}$ ${\displaystyle \leftarrow }$ ${\displaystyle R(}$ x ( $=$ ${\displaystyle {}^{}}$){ $displaystyle$R\$left 화살표$R\$cdot$ x$\cdot$ text{ }}(=$b^{5$로 $설정$합니다.

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {x\mathrm{}}^{}{}^{}}$2 ( $=$ ${\displaystyle {b\mathrm{}}^{}}$8$$) {\$displaystyle$x\$left 화살표 x^{2}{\$text{}}(=$b^{8$

스텝 4) 비트는 1이므로 R ${\displaystyle \leftarrow }$ ${\displaystyle Rx}$x ( ${\displaystyle =}$ ${\displaystyle {}^{}}$ ${\displaystyle {13}^{}}$로 $설정$합니다.{ $displaystyle$R \ $left arrow$ R \ $cdot$ x$text$ text { } （ =$b^$ { $13$} $）$ ;

이것은 마지막 단계이므로 x를 제곱할 필요가 없습니다.

완료: R은 b $({$ b$^{13$입니다.

위의 계산은 b = 4의 거듭제곱 e = 13으로 계산하여 모듈로 497을 수행한 것입니다.

초기화:

${\displaystyle R}$ ${\displaystyle \leftarrow }$ ${\displaystyle 1}$( ${\displaystyle =}$ ${\displaystyle {}^{}{0\mathrm{}}^{}}$ $)({displaystyle$ R$\left 화살표$ 1,(=$b^{0}))$ 및$$${\displaystyle }$ ${\displaystyle x}$ ${\displaystyle \leftarrow }$ b ${\displaystyle =}$({$displaystyle$ x$\left 화살표$ b$=4$

스텝 1) 비트1은 1이므로 $R{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle R4}$ 4${\displaystyle 4}$ ${\displaystyle 4}$ ( ${\displaystyle \mathrm{mod}}$ 497$){$ $display style$R \ $left arrow R$ \ $cdot$ 4 \ $equiv$4 $pmod${$497$ ;

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$ ( $=$ ${\displaystyle {b\mathrm{}}^{}}$2)${\displaystyle {\mathrm{}}^{}}$ 4 ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 16}$ ${\displaystyle (}$ ${\displaystyle \mathrm{mod}}$ $){$ $displaystyle$x\$left$ 화살표 $x^{2}{\text{}}}\equiv$ 4$^{2}\equiv 16gpmod {497$

스텝 2) 비트2는 0이므로 R을 리셋하지 마십시오.

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$ ( $=$ ${\displaystyle {}^{}{4\mathrm{}}^{}}$ ${\displaystyle )\equiv }$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle 16{}^{}}$2 ${\displaystyle (}$ ${\displaystyle \mathrm{256}}$ ( ${\displaystyle \mathrm{mod}}$ 497$){$ $displaystyle$x\$left 화살표$ x$^{2}{\text{}}{=b^{4}}\equiv 16^{$2}\equiv $256gpmod {497$

스텝 3) 비트3은 1이므로 R ${\displaystyle \leftarrow }$ ${\displaystyle Rx}$x ( ${\displaystyle =}$ ${\displaystyle {b\mathrm{}}^{}}$5 )${\displaystyle 4}$ 4$$ ${\displaystyle 25630}$ 30${\displaystyle }$( ${\displaystyle \mathrm{mod}}$ 497$){$ $displaystyle R$ \ $cdot$x \ $cdot$text { } （ =$b^$ { 5 } \ $equiv$4 \ $cdot 256$\ $cdpmod$ { 497$}$ }$$} 를 $설정$합니다.

$set{\displaystyle }$ x ${\displaystyle \leftarrow }$ ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$ ( $=$ ${\displaystyle {b\mathrm{}}^{}}$8 ${\displaystyle )\equiv }$ ${\displaystyle {256}^{}}$ ${\displaystyle {256\mathrm{}}^{}}$ 2${\displaystyle {}^{}\mathrm{29}}$429 ( ${\displaystyle \mathrm{mod}}$497$$){ $display x$ \ $left arrow$ x$^{2}{\text{$}}}\$equiv$ 256$^{2}\equiv 429gpmod {497$

스텝 4) 비트는 1이므로 R ${\displaystyle \leftarrow }$ ${\displaystyle Rx}$x ( ${\displaystyle =}$ ${\displaystyle {\mathrm{b}}^{}}$ 13 )${\displaystyle {}^{}30}$ 30${\displaystyle 29}$ 429${\displaystyle 45\mathrm{445}}$ ( ${\displaystyle \mathrm{mod}}$ 497$$){ $display R$\ $leftarrow$ x ${$ text { } ( =$b^$ { $13}$ \ $equiv 30$ \ $cdot 429$ \ $equiv 445 pmod$ { $497$} } ${\displaystyle \}}$ 로 설정합니다.

종료했습니다.R은 $현재{\displaystyle {\mathrm{}}^{}}$ 4 ${\displaystyle {13}^{}45}$ 445 ${\displaystyle (}$ ${\displaystyle \mathrm{mod}}$ 497$){$ $displaystyle$ 4$^{13}\equiv 445{\pmod {497$입니다.이 결과는 이전 알고리즘에서 얻은 것과 같습니다.

이 알고리즘의 실행 시간은 O(log)입니다.exponent)의 큰 값을 사용하는 경우exponent이는 O(시간)인 앞의 2개의 알고리즘에 비해 상당한 속도의 이점을 얻을 수 있습니다.exponent예를 들어, 지수가 2 = 1048576인 경우²⁰ 이 알고리즘에는 1048576 스텝이 아닌 20 스텝이 포함됩니다.

Lua에서의 구현

m == 1이면 modPow(b, e, m)가 0을 반환하고 그렇지 않으면 로컬 r = 1 b = 1 b % m = 1이면 e > 0 do를 반환하는 동안 r = (r*b) % m end b = (b*b) % m e = e > 1 -- = lu 2 이상의 반환 끝에서 'e = math.floor(e / 2'를 사용합니다.

왼쪽에서 오른쪽으로 이진법

왼쪽에서 오른쪽 순서로 지수의 비트를 사용할 수도 있습니다.실제로, 우리는 보통 결과 모듈로 약간의 모듈러스 m을 원합니다.이 경우 각 곱셈 결과(mod m)를 줄이고 진행합니다.단순화를 위해 여기서는 계수 계산이 생략됩니다.다음으로 왼쪽에서 오른쪽으로 2진수 $인수$를 ${\displaystyle {\mathrm{사용}}^{}}$하여 b 13(\style b 13 ${$ $style$ b^ { $13$$$}지수는 2진수 1101입니다.비트는 4비트이므로 4회 반복됩니다.

결과를 1: $r{\displaystyle }$ ${\displaystyle \leftarrow 1}$ ( $=$ ${\displaystyle {}^{}{0\mathrm{}}^{}}$) {$displaystyle$ r$\left$ 화살표 1,(= $b^{0$ 로 초기화합니다.

$1단계{\displaystyle }$) ${\displaystyle {}^{}}$ ${\displaystyle \leftarrow {}^{}{r\mathrm{}}^{}}$ 2 ( ${\displaystyle ={}^{}{b\mathrm{}}^{}}$ 0$$) { $displaystyle$r\$left 화살표 r$^{2} , ( =$b^{0$ ) ; 비트 1 ${\displaystyle =}$ $1$이므로 ${\displaystyle r}$ ${\displaystyle (}$ b ( ${\displaystyle {}^{}}$ $b$ 1$$) { $displaystyle$r\$left 화살표 r\cdot$ b , ( = b$^{1$} )$$; ;

$2단계{\displaystyle }$) ${\displaystyle {}^{}}$ ${\displaystyle \leftarrow }$ ${\displaystyle {r\mathrm{}}^{}{}^{}}$2 ( ${\displaystyle =}$ ${\displaystyle {b\mathrm{}}^{}}$ 2$$) { $displaystyle$r\$left$ 화살표 r^{2} , ( =$b^{2$}$$) ; 비트 2 ${\displaystyle =}$ 1이므로 $r{\displaystyle b}$b ( ${\displaystyle =}$ ${\displaystyle {b\mathrm{}}^{}}$3$$) { $displaystyle$r\$left 화살표$r\$cdot$ b , ( =$b^{3$} )$$; ;

$스텝{\displaystyle }$ 3) r ${\displaystyle \leftarrow }$ ${\displaystyle {r\mathrm{}}^{}{}^{}}$2 ( ${\displaystyle =}$ ${\displaystyle {b\mathrm{}}^{}}$ 6 $){$ $displaystyle$ r$\left 화살표$ r$^{2$},(=$b^{6$ ;비트 3 = 0이므로 이 스텝은 종료됩니다.

$4단계{\displaystyle }$) r ${\displaystyle \leftarrow }$ ${\displaystyle {r\mathrm{}}^{}{}^{}}$2 ( ${\displaystyle =}$ ${\displaystyle {\mathrm{b}}^{}}$ 12$$) { $displaystyle$r\$left$ 화살표 r$^{2$} , ( =$b^{12}$) ; 비트 4 ${\displaystyle =}$ 1이므로 r${\displaystyle b}$b ( ${\displaystyle =}$ ${\displaystyle {\mathrm{b}}^{}}$ 13$$) { $displaystyle$ r$\left 화살표$ r$\cdot$ b , ( =$b^{13$ ) .

최소 승수

The Art of Computer Programming, Vol.2, Seminumumerical Algorithms, 463페이지에서 Donald Knuth는 일부 주장과 달리 이 방법이 항상 가능한 최소 곱셈 수를 제공하는 것은 아니라고 지적한다.가장 작은 반례는 15의 거듭제곱에 대한 것으로, 이진법에는 6의 곱이 필요합니다.대신 두 곱셈에서 x를 만들고³, 그 다음⁶ x를 제곱하고³, 그¹² 다음 x를 제곱하고⁶, 마지막으로¹⁵ x와³ x를 곱하여¹² 5 곱셈만으로 원하는 결과를 얻을 수 있습니다.그러나 많은 페이지가 이러한 시퀀스가 일반적으로 어떻게 구성될 수 있는지를 설명합니다.

일반화

매트릭스

각 항이 k개의 이전 항의 선형 함수인 모든 상수 반복 시퀀스의 m번째 항(피보나치 수 또는 페린 수 등)은 A mod n을 계산하여^m 효율적으로 모듈 n을 계산할 수 있다. 여기서 A는 대응하는 k×k 동반 행렬이다.위의 방법은 이 응용 프로그램에 쉽게 적응합니다.예를 들어 큰 숫자 n의 primity 테스트에 사용할 수 있습니다.

유사 코드

재귀 알고리즘ModExp(A, b, c)= A^b mod c. 여기서 A는 정사각형 행렬입니다.

함수 Matrix_ModExp(행렬 A, int b, int c)는 b == 0이면 I// (b mod 2 == 1)이면 Identity Matrix를 반환한다(A * Matrix_ModExp(A, b - 1, c) mod Matrix D : == Matrix_ModExp(A, D, D / d)

유한 순환군

Diffie-Hellman 키 교환에서는 유한 사이클 그룹 내에서의 지수를 사용합니다.모듈러 매트릭스 지수화를 위한 위의 방법들은 이 컨텍스트까지 명확하게 확장된다.모듈식 행렬 곱셈 C µ AB(mod n)는 모든 곳에서 그룹 곱셈 c = ab로 간단히 대체된다.

가역 및 양자 모듈식 지수

양자컴퓨팅에서 모듈러형 지수는 쇼어 알고리즘의 병목현상으로 나타나며, 여기서 가역 게이트로 구성된 회로에 의해 계산되어야 하며, 이 회로는 특정 물리 디바이스에 적합한 양자 게이트로 더욱 세분화될 수 있다.게다가 쇼어의 알고리즘에서는, 모든 콜의 베이스와 지수 계수를 알 수 있기 때문에, 다양한 회선 ^[3]최적화가 가능하게 됩니다.

소프트웨어 구현

모듈러형 인수는 컴퓨터 과학에서 중요한 연산이며, 단순히 인수가 되고 나머지를 취하는 것보다 훨씬 빠른 효율적인 알고리즘(위 참조)이 있기 때문에 많은 프로그래밍 언어와 임의 정밀도 정수 라이브러리는 모듈러형 인수가 실행되는 전용 함수를 가지고 있습니다.

• Python의 빌트인pow()(반복) 함수 [1]는 옵션의 세 번째 인수인 계수입니다.
• .NET Framework의BigInteger클래스에는ModPow()모듈러 지수화를 실행하는 방법
• 자바어java.math.BigInteger클래스에는modPow()모듈러 지수화를 실행하는 방법
• MATLAB의powermod심볼릭 산술 도구 상자의 함수
• Wolfram Language에는 PowerMod 기능이 있습니다.
• Perl의Math::BigInt모듈에는bmodpow()모듈러 지수를 실행하는 방법 [2]
• Raku는 루틴이 내장되어 있습니다.expmod.
• Go'sbig.Inttype에는,Exp()(환산) 방법 [3]으로, 세 번째 파라미터가 비환산인 경우 계수
• PHP의 BC Math 라이브러리에는bcpowmod()함수 [4]를 사용하여 모듈식 지수를 수행합니다.
• GNU Multiple Precision 산술 라이브러리(GMP) 라이브러리에는mpz_powm()함수 [5]를 사용하여 모듈식 지수를 수행합니다.
• 커스텀 기능@PowerMod()FileMaker Pro의 경우(1024비트 RSA 암호화 예)
• 루비즈openssl패키지에는OpenSSL::BN#mod_expmethod [6]: 모듈러 지수를 실행합니다.
• HP Prime Calculator에는 모듈러 인수를 실행하기 위한 CAS.powmod() 함수[7]가 있습니다.a^b mod c에 대해 a는 1 EE 12 이하가 될 수 있다.이것은 Prime을 포함한 대부분의 HP 계산기의 최대 정밀도입니다.

「 」를 참조해 주세요.

• Montgomery reduction: 계수가 매우 클 때 나머지를 계산합니다.
• Kochanski 곱셈, 계수가 매우 클 때 나머지를 계산하는 직렬화 가능한 방법
• 배럿 감소, 계수가 매우 클 때 나머지를 계산하는 알고리즘입니다.

레퍼런스

외부 링크

• Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.
• Paul Garrett, 고속 모듈러 지수화 Java 애플릿
• Gordon, Daniel M. (1998). "A Survey of Fast Exponentiation Methods" (PDF). Journal of Algorithms. Elsevier BV. 27 (1): 129–146. doi:10.1006/jagm.1997.0913. ISSN 0196-6774.