certan의 힘에서 숫자의 모듈러스를 계산하십시오 (그 힘의 숫자는 꽤 큽니다)

Question

RSA 알고리즘을 직접 계산하고 싶습니다. 나는 어떤 힘에서 수의 모듈러스를 계산할 필요가있다. 것은 특정 파워에서의 숫자가 상당히 커질 수 있다는 것입니다.

x = pow(n, p) % q 

어떻게 효율적으로 X를 확인할 수 있습니다 여기에

은 내가 원하는 무엇인가?

Answer 1

는 .NET 4를 사용하는 경우, 당신이

이

BigInteger n = ...; 
BigInteger p = ...; 
BigInteger q = ...; 
BigInteger x = BigInteger.ModPow(n, p, q); 

Answer 2

이 topic이 article을 확인하시기 바랍니다 단 한 번의 작동 :)에서 모든 작업을 수행 할 ModPow 방법을 제공 BigInteger,보고 제안 그 자체로 수학 함수를보다 효율적으로 만드는 방법.

Answer 3

하찮게

... 같은 바이너리 지수보다는이 순진한 반복으로

x = 1 
for(i = 0; i < p; i++) 
    x = (x*n) % q 

Theres는보다 효율적인 방법을하지만, X로 오버 플로우 문제가 과거를 얻을 않는이는 n 개의 * q를

Answer 4

이를 경계로한다 powermod function로 알려져있다 :이 지수를 적용하여보다 효율적으로 할 수

function modular_pow(base, exponent, modulus) 
    c := 1 
    for e_prime = 1 to exponent 
     c := (c * base) mod modulus 
    return c 

제곱으로 :

function modular_pow(base, exponent, modulus) 
    result := 1 
    while exponent > 0 
     if (exponent & 1) equals 1: 
      result = (result * base) mod modulus 
     exponent := exponent >> 1 
     base = (base * base) mod modulus 
    return result 

Answer 5

BigInteger.ModPow (Fx 4+)을 참조하십시오. 여기서는 MSDN입니다.

Answer 6

당신이 Modpow()의 자신의 버전을 작성할 계획 인 경우 :

---

당신은 그래서 당신의 계산이 그 사실을 이용하여, q^2보다 숫자 더 큰 사용할 필요가 없습니다, 전원 모듈로 q를 필요

: 모든 곱셈 후 전원 n^p을 계산할 때

if a = b (mod q) then a*p = b*p (mod q) 

따라서, 귀하의 작업 변수에 (모듈로 Q) 작업을한다.

a^(q-1) = 1 (mod q) 
    (when a is not a multiple of q) 

이 p이 (많이)보다 더 큰 q

때 계산을 단축 할 수 있습니다 : q는 소수 경우

---

또한, 당신은한다고 페르마의 작은 정리를 사용할 수 있습니다

Answer 7

여기에 제공된 모든 대답은 정확하지만 모듈러 지수를 구현하는 "고전적인"방법 인 명백한 square-and-multiply 알고리즘은 잘못되었습니다.