제곱에 의한 지수화

이 기사는 독자들에게 혼란스럽거나 불분명할 수 있습니다. 기사를 명확히 할 수 있도록 도와주시기 바랍니다. 이에 대한 논의는 다음과 같습니다.제곱에 의한 지수화 § 최하위 비트가 첫 번째입니다. (2022년 5월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

이 기사는 검증을 위해 추가적인 인용이 필요합니다. 신뢰할 수 있는 자료에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주시기 바랍니다. 출처가 밝혀지지 않은 자료에 이의를 제기하여 제거할 수 있습니다. 출처 찾기 : "제곱에 의한 표현" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2018년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학과 컴퓨터 프로그래밍에서, 제곱에 의한 지수화(exponentifieration)는 다항식이나 제곱 행렬과 같은 반군의 큰 양의 정수 거듭제곱의 빠른 계산을 위한 일반적인 방법입니다.일부 변형을 일반적으로 제곱 및 곱셈 알고리즘 또는 이진 지수화라고 합니다.모듈러 산술이나 행렬의 동력화와 같은 일반적인 용도로 사용될 수 있습니다.암호학에서 사용되는 타원 곡선처럼 가법 표기가 일반적으로 사용되는 반군의 경우 이 방법을 이중 및 덧셈이라고도 합니다.

기본법

재귀 버전

이 방법은 임의의 n> ${\displaystyle n>0}$에 대해다음을 갖는다는 관찰을 기반으로 합니다.

$${\displaystyle x^{n}={\begin{case}x\,(x^{2})^{(n-1)/2},&{\mbox{if}}},{\mbox{ is odd}},\(x^{2})^{n/2},&{\mbox{ is event}},\end{case}}}$$

지수가 0이면 답은 1이고, 지수가 음수이면 양수를 사용하여 값을 다시 작성하여 이전 공식을 다시 사용할 수 있습니다.그것은,

$${\displaystyle x^{-n}=\left ({\frac {1}{x}}\right)^{n}\",}$$

이들은 함께 다음과 같은 재귀 알고리즘으로 직접 구현될 수 있습니다.

In: 정수 x; 정수 n Out: x exp_by_squaring(x, n) n < 0이면 exp_by_squaring(1 / x, -n)을 반환하고, 그렇지 않으면 n = 0이면 1을 반환하고, 그렇지 않으면 n이 짝수이면 exp_by_squaring(x * x, n / 2)을 반환하고, n이 홀수이면 x * exp_by_squaring(x * x, (n - 1) / 2)을 반환하고, 함수를 종료합니다.

각 재귀 호출에서 n의 이진법 표현의 최하위 숫자가 제거됩니다.다음은 재귀 호출의 수가 ⌈ ${\displaystyle {\log }_{}}$ ${\displaystyle 2_{}}$ ⁡ ${\displaystyle n}$ ⌉${\displaystyle ,}$ n의 이진 표현의 비트 수 ${\displaystyle \lceil \log _{2}n\rceil,}$입니다.따라서 이 알고리즘은 이 제곱의 수와 n의 이진법에서 1의 수와 같은 수의 곱셈을 계산합니다.이 로그 연산 수는 n - 1 곱셈이 필요한 사소한 알고리즘과 비교해야 합니다.

이 알고리즘은 꼬리가 반복적이지 않습니다.이는 재귀적 호출의 수에 거의 비례하는 보조 메모리의 양이 필요하다는 것을 의미하며, 반복당 데이터의 양이 증가하는 경우에는 더 많을 수도 있습니다.

다음 섹션의 알고리즘은 다른 접근 방식을 사용하며, 결과 알고리즘은 동일한 수의 연산이 필요하지만 결과를 저장하는 데 필요한 메모리와 거의 동일한 보조 메모리를 사용합니다.

일정한 보조 메모리 사용

이 섹션에서 설명하는 변형은 공식에 기초합니다.

${\displaystyle yx^{n}={\begin{case}(yx)\,(x^{2})^{(n-1)/2},&{\mbox{if}}},\y\,(x^{2})^{n/2},&{\mbox{if }},&{\mbox{iseven}}.\end{case}}$

이 공식을 재귀적으로 적용하면 y = 1로 시작하면 결국 0과 같은 지수를 얻게 되고 원하는 결과는 왼쪽 요인이 됩니다.

이 기능은 꼬리 재귀적 기능으로 구현될 수 있습니다.

  기능. exp_by_squaring(x, n)     돌아가다 exp_by_squaring2(1, x, n)   기능. exp_by_squaring2(y, x, n)     한다면 n < 0 그리고나서 돌아가다 exp_by_squaring2(y, 1 / x, - n);     또 다른 한다면 n = 0 그리고나서 돌아가다 y;     또 다른 한다면 n 가 심지어. 그리고나서 돌아가다 exp_by_squaring2(y, x * x, n / 2);     또 다른 한다면 n 가 이상한 그리고나서 돌아가다 exp_by_squaring2(x * y, x * x, (n - 1) / 2). 

알고리즘의 반복 버전은 또한 유계 보조 공간을 사용하며, 다음과 같이 주어집니다.

  기능. exp_by_squaring_(x, n)     한다면 n < 0 그리고나서       x := 1 / x;       n := -n;     한다면 n = 0 그리고나서 돌아가다 1     y := 1;     하는 동안에 n > 1 하다       한다면 n 가 이상한 그리고나서         y := x * y;         n := n - 1;       x := x * x;       n := n / 2;     돌아가다 x * y 

알고리즘의 정확성은 $y$ ${\displaystyle x^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle yx^{n}}$이(가) 계산 중에 불변하고, $처음$에는 1${\displaystyle }$⋅ ${\displaystyle {}^{}}$ ${\displaystyle n^{}{}^{}}$= ${\displaystyle {}^{}}${\$displaystyle$ 1$\cdot$ x$^{n$}= $x^{n}$이고, $끝$에는 ${\displaystyle {}^{}}$ ${\displaystyle x^{}}$ 1 = ${\displaystyle x}$ ${\displaystyle yx^{1$}= $xy}$이기 때문입니다.

이 알고리즘들은 앞 절의 알고리즘과 정확히 동일한 연산 수를 사용하지만 곱셈은 다른 순서로 수행됩니다.

계산 복잡도

간단히 분석하면 이러한 알고리즘은 ⌊ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle 2_{}}$ ⁡ ${\displaystyle n}$ ⌋${\displaystyle \log$ _${2}n\rfloor}$ 제곱을 사용하고 최대 ⌊ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle 2_{}}$ ⁡ ${\displaystyle \log _{2}n\rfloor}$ ${\displaystyle \mathrm{곱셈}}$을 사용하며, 여기서 ⌊ ⌋ $displaystyle \lfloor \;\rfloor}$는 바닥 함수를 나타냅니다.더 정확하게 말하면, 곱셈의 수는 n의 이진 확장에 존재하는 곱셈의 수보다 1 적습니다.n이 약 4보다 클 경우, 이는 베이스와 자신을 반복적으로 순진하게 곱하는 것보다 계산적으로 더 효율적입니다.

각 제곱은 이전의 자릿수의 약 두 배가 되므로, 두 d자리 숫자의 곱이 어떤 고정 k에 대한 O(d^k) 연산으로 구현된다면, xⁿ 연산의 복잡도는 다음과 같이 주어집니다.

${\displaystyle \sum \limits _{i=0}^{O(\log n)}{\big (}2^{i}O(\log x){\big )}^{k}=O{\big (}(n\log x)^{k}}{\big )}}$

2진법^k

이 알고리즘은 기저 2에서^k 지수를 확장한 후 x의ⁿ 값을 계산합니다.그것은 1939년에 브라우어에 의해 처음으로 제안되었습니다.아래 알고리즘에서 우리는 다음 함수 f(0) = (k, 0) 및 f(m) = (s, u)를 사용합니다. 여기서 m = u·2는 u가 홀수입니다.

알고리즘:

인풋

G의 원소 x, 매개 변수 k > 0, 음이 아닌 정수 n = (n, n, ..., n) 및 미리 계산된 값 $x$ ${\displaystyle 3^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 5^{},}$ ...,${\displaystyle {{}^{}}^{}}$x $2$ ${\displaystyle {\mathrm{k}}^{}}$ -$$1 {\$displaystyle x^{3},$ x^{5}, $..., x^{2$k$}-1}.$

산출량

G의 원소ⁿ x

y := 1; i := l - 1인 반면 i ≥ 0 do(s, u) := f(n) j := 1 to k - s do y := y y := y * x to s y := y i := i - 1 return y

최적의 효율성을 위해 k는 다음을^[1] 만족하는 가장 작은 정수여야 합니다.

${\displaystyle \lg n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-1}}+1.}$

슬라이딩 윈도우 방식

이 방법은 2-ary^k 방법의 효율적인 변형입니다.예를 들어, 이진 확장(110001 110)을 가지는 지수 398을 계산하기 위해 ₂2진법^k 알고리즘을 사용하여 길이 3의 윈도우를 구하고 1, x³, x⁶, x, x¹², x, x²⁴, x⁴⁸, x, x⁴⁹¹⁹⁸, x, x⁹⁸⁹⁹, x, x¹⁹⁹²⁴, x, x, x, x³⁹⁸, x, x⁴⁸, x, x, x, x, x, x, x⁹⁶¹⁹², x, x³⁹⁸, x, x, x, x¹⁹⁹, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,₂ x, x, x, x³, x, x, x, x⁶, x, x, x, x¹²

일반적인 알고리즘은 다음과 같습니다.

알고리즘:

인풋

G의 원소 x, 음이 아닌 정수 n=(n, n, ..., n), 매개 변수 k > 0 및 사전 computed 값 x ${\displaystyle 3^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 5^{}}$ ${\displaystyle ...,}$x $2$ ${\displaystyle {\mathrm{k}{}^{}}^{}}$- 1 ${\displaystyle$ x$^{3}, x^{5},$ ..., x$^{2^{k}-1$

산출량

원소 x는 G ∈.

알고리즘:

y := 1; i := l - 1인 반면 i > -1이면 n = 0이면 y := y' i := i - 1이면 s := max{i - k + 1, 0}이고 n = 0이면 s := s + 1이면 h := 1 ~ i - s + 1이면 y := y := (n, n, ..., n) y := y * x i := s - 1 리턴 y

몽고메리의 사다리 기술

지수화를 위한 많은 알고리즘은 측면 채널 공격에 대한 방어를 제공하지 않습니다.즉, 제곱과 곱셈의 순서를 관찰하는 공격자는 계산에 관련된 지수를 (부분적으로) 복구할 수 있습니다.많은 공개 키 암호 시스템과 마찬가지로 지수를 비밀로 유지해야 하는 경우 이 문제가 발생합니다."몽고메리의 사다리"^[2]라고 불리는 기술이 이 문제를 해결해 줍니다.

n = 1인 양의 0이 아닌 정수 n = (n...n)의 이진 확장을 고려하면 다음과 같이 x를 계산할 수 있습니다.

x = x; x = x for i = k - 2 ~ 0이면 n = x = x * x; x = x 기타 x = x * x; x = x 반환 x

알고리즘은 고정된 연산 시퀀스(로그 n까지)를 수행합니다. 즉, 비트의 특정 값에 관계없이 지수의 각 비트에 대해 곱셈과 제곱이 이루어집니다.두 배로 곱하기 위한 비슷한 알고리즘이 존재합니다.

Montgomery의 Ladder의 이 특정 구현은 아직 캐시 타이밍 공격으로부터 보호되지 않습니다. 비밀 지수의 비트 값에 따라 서로 다른 변수가 액세스되기 때문에 메모리 액세스 지연 시간이 공격자에게 여전히 관찰 가능할 수 있습니다.최신 암호화 구현에서는 "산란" 기법을 사용하여 프로세서가 항상 더 빠른 캐시를 놓치도록 합니다.^[3]

고정 기저 지수

기저가 고정되고 지수가 변화할 때 x를ⁿ 계산하는 데 사용할 수 있는 몇 가지 방법이 있습니다.보시다시피 사전 계산은 이러한 알고리즘에서 핵심적인 역할을 합니다.

야오의 방법

Yao의 방법은 radix b = 2에서 지수를 확장하고 계산은 위의 알고리즘에서 수행된 것과 같은 2진법과 직교합니다.n, n_i, b, b를_i 정수라 하자.

지수 n을 다음과 같이 쓰도록 합니다.

${\displaystyle n=\sum _{i=0}^{w-1}n_{i}b_{i}}$

여기서 $i$ ∈${\displaystyle }$[${\displaystyle 0,}$ ${\displaystyle w}$ -${\displaystyle 1]}$ ${\displaystyle i\in [0,w-1]$에 대해 0 ⩽ ni < {\$displaystyle 0\leqslant n_{i}<h}.$

x를 = x라고 합니다.

그러면 알고리즘은 동일성을 사용합니다.

${\displaystyle x^{n}=\prod _{i=0}^{w-1}x_{i}^{n_{i}}=\prod _{j=1}^{h-1}{\bigg [}\prod _{n_{i}=j}x_{i}{\bigg ]}^{j}}}}$

G의 원소 x와 위의 형태로 쓰여진 지수 n이 미리 계산된 값 x^b₀...x와^b_w−1 함께 주어지면, 원소 x는ⁿ 아래의 알고리즘을 사용하여 계산됩니다.

y = 1, u = 1, j = h - 1인 반면 i = 0 ~ w - 1인 경우 n = j, u = u x x y = y x u j = j - 1 반환 y

만약 우리가 h = 2이고 b = h를 설정한다면, n개의 값은 단순히 n개의 숫자(베이스 h)가 됩니다.Yao의 방법은 가장 높은 출력 ${\displaystyle \mathrm{h}}$ -${\displaystyle }$1 ${\displaystyle h-1}$에 나타나는 x를_i u에서 먼저 수집합니다$.$ 다음 라운드에서는 $출력{\displaystyle }$ h -${\displaystyle 2}$ ${\displaystyle h-1}$에 나타나는 x를 u 등에서도 수집합니다$$.변수 y는 $초기{\displaystyle }$ u와 h${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle h-1}$번$$ 곱하고, $h{\displaystyle }$ -${\displaystyle 2}$ ${\displaystyle h-1}$번 곱하고, 그 다음으로 높은 검정력을 갖는 h - 2 {\displaystyle h-1}회$$ 곱합니다.알고리즘은 +${\displaystyle h}$ -${\displaystyle 2}$ ${\displaystyle$w$+h-2}$번의$$ 곱셈을 $사용$하며 x를ⁿ 계산하려면 $w{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle w+1}$개의$$ 요소를 저장해야 합니다.^[1]

유클리드법

유클리드 방법은 P에 의해 사전 계산과 벡터 덧셈 체인을 사용한 효율적 지수화에서 처음 도입되었습니다.루이즈 박사님.

group G에서 x ${\displaystyle n^{}}$ ${\$을 계산하는 방법(n은 자연 정수이며 알고리즘은 아래와 같습니다)은 다음과 같은 등식을 재귀적으로 사용합니다.

${\displaystyle x_{0}^{n_{0}}\cdot x_{1}^{n_{1}}=\left(x_{0}\cdot x_{1}^{q}\right)^{n_{0}}\cdot x_{1}^{n_{1}\mod n_0}}$

여기서 $q$ = ⌊ ${\displaystyle n}$ ${\displaystyle \frac{1_{}}{}}$ n ${\displaystyle \frac{0_{}}{}}$ ⌋ ${\displaystyle$q =\$left\l$ floor ${\frac {n_{1}}{n_{0}}\right\rfloor }.$즉, 지수 n을 n으로 나눈 유클리드식 분할은 몫 q와 휴식 n modn을 반환하는 데 사용됩니다.

그룹 G의 기본 요소 x와 야오의 방법과 같이 쓰인$$ 지수 $n{\displaystyle }$ ${\displaystyle n}$이 주어지면, 요소 x ${\displaystyle n^{}}$ ${\$은 $l{\displaystyle }$ ${\displaystyle l}$ 사전 계산$$ 값 x ${\displaystyle {b{}_{}}^{}}$ ${\displaystyle {{0\mathrm{}}_{}}^{}}$ ${\displaystyle ...,}$ ${\displaystyle {{x{}_{}}_{}}^{}}$ ${\displaystyle {{b_{}}_{}}^{}}$ ${\$}}, $..., x^{b_{l_{i}}}$를 사용하여 계산됩니다$$.

$루프$ ${\displaystyle i}$가 [0${\displaystyle ,}$ l${\displaystyle }$- ${\displaystyle 1]}$ ∀ [${\displaystyle 0,}$ l - ${\displaystyle 1}$ ] {\${\displaystyle {displaystyle}_{}}$ $M\in [0,$ ${\displaystyle l}$ -${\displaystyle }$$1$${\displaystyle ]\},}$ ${\displaystyle {}_{}}$ M ≥ ${\displaystyle n_{}}$ ${\displaystyle$ \$forall i\in [0,l-1], n_{M}\geq n_{i}.$${\displaystyle N}$ ∈ 찾기${\displaystyle }$(${\displaystyle }$[${\displaystyle 0,}$ l${\displaystyle }$- ${\displaystyle 1}$] -${\displaystyle }$M${\displaystyle }$) ${\displaystyle N\in {\big$ ${\displaystyle (\}[0}$$,$ ${\displaystyle \mathrm{l-1}]}$$$- M ${\big}},$n ≥ i $forall$ i$\in {\big (}[0,$ - ${\displaystyle M\{\backslash }$big}},${\displaystyle n_{}}$ ∀ ${\displaystyle {}_{}}$ ${\displaystyle${\$big$ (}[0, l-1] - M${\big}}, n_{N$}$}\geq n_{i$ N $=$${\displaystyle {}_{}0}$ ${\displaystyle n_{N}$$=$$0$$\}$이면 $루프$를 끊습니다. q $=$$$$⌊$$$${\displaystyle {}_{}^{}}$ M${\displaystyle }$/ ${\displaystyle N{}_{}}$$⌋$ $displaystyle$ q $=$\$lfloor$ n_${M}/$n_{$N}\rfluor$}}라고$하고$ N $=$ (${\displaystyle {}_{}}$ ${\displaystyle M_{}}$ ${\displaystyle {mod}_{}}$ N${\displaystyle {}_{}}$) ${\displaystyle n_{N$}$=$ ($n_{M$} ${\bmod {n}}_{N}}$이라고 합니다$.$ 재귀적으로 ${\displaystyle x_{}^{}}$ $M$ ${\displaystyle {}_{}^{}}$ ${\displaystyle x_{M}^{q$를 계산한 다음 x ${\displaystyle N_{}}$ $=$ x ${\displaystyle N_{}}$ $⋅$ x${\displaystyle {}_{}{M}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle x_{N}$$=$ x_${N}\cdot x_{M}^{q$ 끝 lop; x $n$ =$$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {M_{}}_{}^{}}$ ${\displaystyle$ x$^{n$}= x_${M}^{n_{M}}을($를$)$ 반환합니다.

알고리즘은 먼저 n 중에서 가장 큰 값을 찾은 다음 {n \i ≠ M}의 집합 내에서 최댓값을 찾습니다. 그런 다음 x를 거듭제곱 q로 올리고 이 값을 x와 곱한 다음 x에 이 계산의 결과를 할당하고 n 모듈론 값을 할당합니다.

추가 응용프로그램

이 접근법은 또한 큰 지수 모듈로 수를 빠르게 계산할 수 있는 등 특성이 0이 아닌 세미그룹과도 작동합니다.특히 암호학에서는 정수 모듈 q의 링에서 거듭제곱을 계산하는 것이 유용합니다.예를 들어, 다음의 평가.

13789 (mod 2345) = 2029

13789를⁷²²³⁴¹ 계산한 다음 2345로 나누었을 때 나머지를 가져가는 순진한 방법을 사용한다면 매우 오랜 시간과 많은 저장 공간이 소요될 것입니다.더 효과적인 방법을 사용하더라도 시간이 오래 걸립니다: 제곱 13789, 2345로 나누었을 때 나머지를 구하고 결과에 13789를 곱하는 식입니다.

x * y = xy mod 2345 (즉, 곱셈 뒤에 나머지가 있는 나눗셈)로 해석되는 "*"를 사용하여 위의 exp-by-squaring 알고리즘을 적용하면 정수의 곱셈과 나눗셈이 27개만 생성되며, 이는 모두 하나의 기계어에 저장될 수 있습니다.일반적으로, 이러한 접근 방식들 중 어느 것이든 2log₂ (722340) ≤ 40 모듈러 곱셈보다 적은 수의 시간이 소요됩니다.

이 접근법은 또한 규칙을 사용하여 그룹의 정수 거듭제곱을 계산하는 데 사용될 수 있습니다.

검정력(x, -n) = (검정력(x, n)).

이 접근법은 비상호화 세미그룹에서도 사용되며 종종 행렬의 거듭제곱을 계산하는 데 사용됩니다.

보다 일반적으로, 이 접근법은 이진 연산이 전력 연상인 모든 마그마에서 작동합니다.

부호화된 자리수의 녹음

특정 계산에서 음의 계수를 허용하는 것이 더 효율적일 수 있으며, 따라서 G의 반전이 "빠른" 또는 미리 계산된 경우에는 기저의 역을 사용할 수 있습니다.예를 들어, x를^2k−1 계산할 때 이항법은 k-1 곱셈과 k-1 제곱을 필요로 합니다.그러나 사람은 x를^2k 얻기 위해 k개의 제곱을 수행한 다음 x를⁻¹ 곱하여 x를^2k−1 얻을 수 있습니다.

이를 위해 정수 n의 부호화된 숫자 표현을 radix bas로 정의합니다.

${\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }} n_{i} <b.}$

서명된 이진 표현은 특정 선택 b = 2 및 ${\displaystyle {ni}_{}}$ ∈${\displaystyle }${${\displaystyle }$- ${\displaystyle 1,}$ ${\displaystyle 0,}$ ${\displaystyle 1\}}$ ${\displaystyle n_{i}\in \{-1,$ 0,$1\}$에 해당합니다$.$ (${\displaystyle {}_{}}$ ${\displaystyle l_{}}$- ${\displaystyle 1_{}}$… n ${\displaystyle {}_{}}$)${\displaystyle s_{}}$ ${\displaystyle (n_{l-1}\$dots$n_{0})_{s}$로 표시됩니다$.$이 표현을 계산하는 몇 가지 방법이 있습니다.표현이 고유하지 않습니다.예를 들어 n = 478: 두 개의 구별된 부호가 있는 binary 표현은 $({\displaystyle 101\stackrel{}{}}$¯ ${\displaystyle 1100}$ ${\displaystyle 1}$ ¯ ${\displaystyle 10{}_{}}$)의 ${\displaystyle(10{\bar {1}},$1100 ${\bar {1}}_{s$} 및$$(${\displaystyle 100}$ 1 ¯ ${\displaystyle 1000}$ 1 ¯$$0 $)$의 {\$displaystyle(100{\bar$ {1$}}, 1000{\bar {1}}_{s}$이며$,$ $여기$서 1 ¯ ${\displaystyle {\bar {1}}$은 -1을 나타냅니다.이진법은 n의 기본-2 표현에서 0이 아닌 모든 항목에 대한 곱셈을 계산하기 때문에 0이 아닌 항목의 수가 가장 적은 부호화된 이진 표현, 즉 해밍 가중치가 최소인 표현을 찾는 데 관심이 있습니다.이를 위한 한 가지 방법은 ${\displaystyle {}_{}}$, 즉 ${\displaystyle \mathrm{줄여서}}$ ${\displaystyle {\mathrm{NAF}}_{}}$로 표현을 계산하는 것인데, 이는 ${\displaystyle \mathrm{모든}}$ ${\displaystyle i{}_{}}$⩾ 0 ${\displaystyle n_{i}n_{i+1}$=$0{\text{for$ all $}i\geqslant$ 0$}$을(를) 만족하며$$(${\displaystyle n_{}}$l -${\displaystyle 1_{}}$ … ${\displaystyle n_{}}$0 ) ${\displaystyle {\text{NAF}}_{}}${\$displaystyle (n_{l-1}\$dots$n_{0})_{\text{$$NAF}}.$예를 들어 478의 NAF 표현은 $($ ${\displaystyle 1000}$ ${\displaystyle 1}$ $¯$ ${\displaystyle 000}$ ${\displaystyle 1}$ $¯$ 0${\displaystyle {}_{}}$) ${\displaystyle {\text{NAF}}_{}}$ ${\displaystyle (1000{\bar {1}},000{\bar {1}}_{\text{$$NAF}}.$이 표현은 항상 최소 해밍 무게를 가집니다.지정된 $정수$ n =${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {\mathrm{l}}_{}}$- ${\displaystyle {}_{}{}_{}}$… ${\displaystyle n_{}}$ 0${\displaystyle {}_{}}$) 2 ${\displaystyle$n = ($n_{l}n_{l-1}\n_{0})_{2}}($$n$ ${\displaystyle l_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle l_{}}$- ${\displaystyle 1_{}}$ = ${\displaystyle 0}$ ${\displaystyle n_{l$}= $n_{l-1$}= $0)$의 NAF 표현을 계산하는 간단한 알고리즘은 다음과 같습니다.

${\displaystyle c_{}}$ ${\displaystyle 0_{}}$ ${\displaystyle =}$ i의 경우 0 ${\displaystyle$}=$0}$ {\displaystyle ${\displaystyle c_{}}$_{0${\displaystyle {\}=}_{}\frac{0}{}}$} ${\displaystyle c_$${\displaystyle {\{}_{}}$$i+1$ floor ${\frac {1}{2}}(c_{i}+n_{i}+n_{i$+1$})\right$\$rfloor$ $}$${\displaystyle {}_{}}$n $=$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ -${\displaystyle {}_{}2}$ ${\displaystyle {\mathrm{c}}_{}}$ ${\displaystyle {}_{}}$+ 1 ${\displaystyle$${\displaystyle n_{}}$$_{i$}=$c_{i}+n_2c_{i+1}$ 반환$$(${\displaystyle n_{}^{}}$ l${\displaystyle {}_{}^{}}$- ${\displaystyle 1_{}^{}}$… n ${\displaystyle 0_{}^{}\text{'})}$ ${\displaystyle {\text{NAF}}_{}}$ ${\displaystyle (n_{l-1}'\text{0}')$$NAF}}}$

Koyama and Tsuroka의 또 다른 알고리즘은 ${\displaystyle {ni}_{}}$ = ${\displaystyle \mathrm{ni}{}_{}}$+ ${\displaystyle 1_{}}$ = 0 ${\displaystyle n_{i$} =$n_{i+1$} = $0}$ 조건을 요구하지 않지만 그래도 해밍 가중치를 최소화합니다$.$

대안 및 일반화

제곱에 의한 지수화는 차선의 추가 체인 지수화 알고리즘으로 볼 수 있습니다. 반복되는 지수 이중화(제곱) 및/또는 증가 지수를 1만큼(x를 곱한) 추가 체인에 의해 지수를 계산합니다.보다 일반적으로, 이전에 계산된 지수를 합산할 수 있다면(이러한 x의 거듭제곱을 곱함으로써) 때때로 더 적은 곱셈을 사용하여 지수화를 수행할 수 있습니다(일반적으로 더 많은 메모리를 사용함).n = 15의 경우 가장 작은 전력이 발생합니다.

${\displaystyle x^{}}$ ${\displaystyle {15}^{}}$ $=$ ${\displaystyle x}$× (${\displaystyle x}$×${\displaystyle }$[ x${\displaystyle }$× ${\displaystyle 2^{}}$] ${\displaystyle 2^{}}$) ${\displaystyle 2^{}}$ ${\displaystyle x$}= x$\times (x\times x^{2}]^{2})^{2}}($제곱, 6배수),

${\displaystyle x^{}}$ ${\displaystyle {15}^{}}$ $=$ ${\displaystyle {}^{}}$ ${\displaystyle 3^{}}$×${\displaystyle }$(${\displaystyle }$[ ${\displaystyle {}^{}}$ ${\displaystyle 3^{}}$] 2${\displaystyle {}^{}}$) ${\displaystyle 2^{}}$ ${\displaystyle$ x${15$}= $x^{3}\times ([x^{3}]^{2})^{2}}$ (최적 덧셈 체인, x를 재사용할 경우 5배수).

일반적으로 주어진 지수에 대한 최적의 덧셈 체인을 찾는 것은 어려운 문제이며, 이에 대해 효율적인 알고리즘이 알려져 있지 않기 때문에 최적의 체인은 일반적으로 작은 지수에만 사용됩니다(예: 작은 거듭제곱에 대한 체인이 미리 표로 작성된 컴파일러).그러나 최적은 아니지만 추가 부기 작업 및 메모리 사용 비용을 제곱하여 지수화하는 것보다 곱셈 수가 적은 휴리스틱 알고리즘이 많이 있습니다.그럼에도 불구하고, 곱셈의 수는 θ(log n)보다 더 느리게 증가하지 않으므로, 이러한 알고리즘은 기껏해야 일정한 인자로만 제곱하여 지수화할 때 점근적으로 개선됩니다.

참고 항목

• 모듈 지수화
• 벡터 덧셈 사슬
• 몽고메리 환원
• 비인접형태
• 덧셈 체인

메모들

참고문헌