2016-12-30 7 views
-2

m^e mod (n)위한 이러한 알고리즘이있다 : 그것은 는 이제 생각한위한 오버 플로우하지 않도록C에서 모듈화로 지수화 할 숫자의 바이트 크기를 최대 두 배로 요구하는 모듈러 지수화를 구현하는 방법은 무엇입니까? 환언

// powmod(m,e,n) = m^e % n 
unsigned long long powmod(unsigned long m, unsigned long e, unsigned long long n) 

여기서 m = 2^32 - 1 E = 3, N = 2^64 - 1 gmp 또는 그런 라이브러리를 사용하지 않고?

+1

키워드 'powmod'와 SO 소식 수십개이다. 확실히 그 중 하나가 당신을 도울 것입니다. OTOH, 당신이 시도한 것을 게시하는 것이 좋을 것입니다. – chux

+1

만약'n = 2^64 - 1'이라면, 코드가''double ''크기의''n''을 필요로한다고 생각하지 않습니다. "modularly exponentiated 될 숫자"만일'0 chux

+2

@Nae 어디에 게시하든, 대답은 동일합니다 : x 비트의 n 비트에 대해 주어진 비트 레인에 대해 항상 2 * x 비트len 연산이 필요합니다. 'n에 대한'unsigned long long' 비트 레인을 감안할 때'unsigned long long long long' 정밀도 없이는 할 수 없습니다. –

답변

3

예, 가능합니다. 아래 코드는 내장 된 Exp이므로 테스트 해보십시오. 유일한 라이브러리 사용은 테스트에만 국한되므로 C 로의 변환은 매우 직관적이어야합니다. 메인 함수 에지 검사 값과 상기 코드

package main 

import (
    "fmt" 
    "math" 
    "math/big" 
    "math/rand" 
) 

// AddMod returns a + b (mod m). 
func AddMod(a, b, m uint64) uint64 { 
    a %= m 
    b %= m 
    if a >= m-b { 
     return a - (m - b) 
    } 
    return a + b 
} 

// SubMod returns a - b (mod m). 
func SubMod(a, b, m uint64) uint64 { 
    a %= m 
    b %= m 
    if a < b { 
     return a + (m - b) 
    } 
    return a - b 
} 

// Lshift32Mod returns 2^32 a (mod m). 
func Lshift32Mod(a, m uint64) uint64 { 
    a %= m 
    // Let A = 2^32 a. The desired result is A - q* m, where q* = [A/m]. 
    // Approximate q* from below by q = [A/(m+err)] for the err in (0, 2^32] such 
    // that 2^32|m+err. The discrepancy is 
    // 
    // q* - q < A (1/m - 1/(m+err)) + 1 = A err/(m (m+err)) + 1 
    // 
    // A - q m = A - q* m + (q* - q) m < m + A err/(m+err) + m < 2 m + 2^64. 
    // 
    // We conclude that a handful of loop iterations suffice. 
    m0 := m & math.MaxUint32 
    m1 := m >> 32 
    q := a/(m1 + 1) 
    q0 := q & math.MaxUint32 
    q1 := q >> 32 
    p := q0 * m0 
    p0 := p & math.MaxUint32 
    p1 := p >> 32 
    a -= p1 + q0*m1 + q1*m0 + ((q1 * m1) << 32) 
    for a > math.MaxUint32 { 
     p0 += m0 
     a -= m1 
    } 
    return SubMod(a<<32, p0, m) 
} 

// MulMod returns a b (mod m). 
func MulMod(a, b, m uint64) uint64 { 
    a0 := a & math.MaxUint32 
    a1 := a >> 32 
    b0 := b & math.MaxUint32 
    b1 := b >> 32 
    p0 := a0 * b0 
    p1 := AddMod(a0*b1, a1*b0, m) 
    p2 := a1 * b1 
    return AddMod(p0, Lshift32Mod(AddMod(p1, Lshift32Mod(p2, m), m), m), m) 
} 

// PowMod returns a^b (mod m), where 0^0 = 1. 
func PowMod(a, b, m uint64) uint64 { 
    r := 1 % m 
    for b != 0 { 
     if (b & 1) != 0 { 
      r = MulMod(r, a, m) 
     } 
     a = MulMod(a, a, m) 
     b >>= 1 
    } 
    return r 
} 

func randUint64() uint64 { 
    return uint64(rand.Uint32()) | (uint64(rand.Uint32()) << 32) 
} 

func main() { 
    var biga, bigb, bigm, actual, bigmul, expected big.Int 
    for i := 1; true; i++ { 
     a := randUint64() 
     b := randUint64() 
     m := randUint64() 
     biga.SetUint64(a) 
     bigb.SetUint64(b) 
     bigm.SetUint64(m) 
     actual.SetUint64(MulMod(a, b, m)) 
     bigmul.Mul(&biga, &bigb) 
     expected.Mod(&bigmul, &bigm) 
     if actual.Cmp(&expected) != 0 { 
      panic(fmt.Sprintf("MulMod(%d, %d, %d): expected %s; got %s", a, b, m, expected.String(), actual.String())) 
     } 
     if i%10 == 0 { 
      actual.SetUint64(PowMod(a, b, m)) 
      expected.Exp(&biga, &bigb, &bigm) 
      if actual.Cmp(&expected) != 0 { 
       panic(fmt.Sprintf("PowMod(%d, %d, %d): expected %s; got %s", a, b, m, expected.String(), actual.String())) 
      } 
     } 
     if i%100000 == 0 { 
      println(i) 
     } 
    } 
} 

C 번역 :

#include <stdio.h> 
// AddMod returns a + b (mod m). 
unsigned long long AddMod(unsigned long long a, unsigned long long b, unsigned long long m){ 
    a %= m; 
    b %= m; 
    if (a >= m-b) { 
     return a - (m - b); 
    } 
    return a + b; 
} 

// SubMod returns a - b (mod m). 
unsigned long long SubMod(unsigned long long a, unsigned long long b, unsigned long long m){ 
    a %= m; 
    b %= m; 
    if (a < b) { 
     return a + (m - b); 
    } 
    return a - b; 
} 

// Lshift32Mod returns 2^32 a (mod m). 
unsigned long long Lshift32Mod(unsigned long long a, unsigned long long m){ 
    a %= m; 
    // Let A = 2^32 a. The desired result is A - q* m, where q* = [A/m]. 
    // Approximate q* from below by q = [A/(m+err)] for the err in (0, 2^32] such 
    // that 2^32|m+err. The discrepancy is 
    // 
    // q* - q < A (1/m - 1/(m+err)) + 1 = A err/(m (m+err)) + 1 
    // 
    // A - q m = A - q* m + (q* - q) m < m + A err/(m+err) + m < 2 m + 2^64. 
    // 
    // We conclude that a handful of loop iterations suffice. 
    unsigned long long m0 = m & 0xFFFFFFFF; 
    unsigned long long m1 = m >> 32; 
    unsigned long long q = a/(m1 + 1); 
    unsigned long long q0 = q & 0xFFFFFFFF; 
    unsigned long long q1 = q >> 32; 
    unsigned long long p = q0 * m0; 
    unsigned long long p0 = p & 0xFFFFFFFF; 
    unsigned long long p1 = p >> 32; 
    a -= p1 + q0*m1 + q1*m0 + ((q1 * m1) << 32); 
    while (a > 0xFFFFFFFF) { 
     p0 += m0; 
     a -= m1; 
    } 
    return SubMod(a<<32, p0, m); 
} 

// MulMod returns a b (mod m). 
unsigned long long MulMod(unsigned long long a, unsigned long long b, unsigned long long m){ 

    unsigned long long a0 = a & 0xFFFFFFFF; 
    unsigned long long a1 = a >> 32; 
    unsigned long long b0 = b & 0xFFFFFFFF; 
    unsigned long long b1 = b >> 32; 
    unsigned long long p0 = a0 * b0; 
    unsigned long long p1 = AddMod(a0*b1, a1*b0, m); 
    unsigned long long p2 = a1 * b1; 

    return AddMod(p0, Lshift32Mod(AddMod(p1, Lshift32Mod(p2, m), m), m), m); 
} 

// PowMod returns a^b (mod m), where 0^0 = 1. 
unsigned long long PowMod(unsigned long long a, unsigned long long b, unsigned long long m){ 
    unsigned long long r = 1 % m; 
    while (b != 0) { 
     if ((b & 1) != 0) { 
      r = MulMod(r, a, m); 
     } 
     a = MulMod(a, a, m); 
     b >>= 1; 
    } 
    return r; 
} 


int main(void){ 
    unsigned long long a = 4294967189; 
    unsigned long long b = 4294967231; 
    unsigned long long m = 18446743979220271189; 
    unsigned long long c = 0; 

    c = PowMod(a, b, m); 
    printf("%llu %llu %llu %llu", a, b, m, c); 
} 
+0

@Nae It 's Go. 연산자는 새로운 변수를 선언하고 할당하는': ='를 제외하고는 C와 동일합니다. –

+1

OK'func MulMod (a, b, m uint32) uint32'는 연산을 네 개의 n/2 수학 제품으로 나눔으로써 n 비트 곱셈보다 넓은 연산을 수행함을 알 수 있습니다. OP가 오류없이 C로 변환되기를 바랍니다. – chux

+0

@Nae 피연산자를 하프 크기 청크로 분할하고 긴 곱셈/나누기를 사용합니다. –