목록Montgomery Reduction (1)

암호(수학) 등.. 공부한 거 잊을거 같아서 만든 블로그

[Algorithm] Montgomery Reduction Algorithm

Montgomery Form 위 이미지에 있는 계산 방식은 Montgomery From 이라고 하는 계산방법이다. 몽고메리 폼에서의 a` = aR mod N와 b` = bR mod N을 곱하면 (aR mod N) * (bR mod N) = (abR)R mod N 이고, 이를 몽고메리 폼에 맞게 하기 위해 R^(-1)을 곱해준다. (abR)R*R^(-1) mod N =(abR) mod N 이러한 계산과정은 R^(-1)을 곱하고 N을 나눠야 하기 때문에 느리다. 하지만 아래의 알고리즘을 통하여 구하면 비트 쉬프트 연산을 통해 빠른 계산으로 구할 수 있다. Montgomery Reduction Algorithm아래의 수식은 몽고메리 감산 알고리즘으로 T = (aR mod N) * (bR mod N)을 (abR..
Algorithm 2024. 3. 27. 16:38
이전 Prev 1 Next 다음