Số mũ lũy thừa cho số cao trong C++

Question

Vì vậy, tôi đã làm việc gần đây về việc thực hiện thử nghiệm nguyên thủy Miller-Rabin. Tôi giới hạn nó với phạm vi của tất cả các số 32 bit, vì đây là một dự án đơn giản mà tôi đang làm để tự làm quen với C++ và tôi không muốn phải làm việc với bất kỳ thứ gì 64 bit cho một lát. Một tiền thưởng thêm là thuật toán là xác định cho tất cả các số 32 bit, vì vậy tôi có thể tăng hiệu quả đáng kể bởi vì tôi biết chính xác những nhân chứng nào cần thử nghiệm.

Vì vậy đối với các số thấp, thuật toán hoạt động rất tốt. Tuy nhiên, một phần của quá trình dựa trên lũy thừa mô đun, đó là (num^pow)% mod. như vậy, ví dụ,

3^2 % 5 = 
9 % 5 = 
4 

đây là đoạn code tôi đã được sử dụng cho lũy thừa modulo này:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod) 
{ 
    unsigned test; 
    for(test = 1; pow; pow >>= 1) 
    { 
     if (pow & 1) 
      test = (test * num) % mod; 
     num = (num * num) % mod; 
    } 

    return test; 

} 

Như bạn có thể đã đoán, các vấn đề phát sinh khi các đối số đều đặc biệt với số lượng lớn. Ví dụ, nếu tôi muốn kiểm tra số 673.109 cho tính nguyên, tôi sẽ có lúc phải tìm:

(2^168277)% 673109

hiện giờ là 2^168.277 là một con số đặc biệt lớn, và ở đâu đó trong quá trình nó tràn thử nghiệm, kết quả trong một đánh giá không chính xác.

ở phía ngược lại, lập luận như

4000111222^3% 1608

cũng đánh giá không đúng cách, vì những lý do tương tự.

Có ai có đề xuất về mô đun lũy thừa theo cách có thể ngăn chặn tình trạng tràn này và/hoặc thao tác nó để tạo kết quả chính xác không? (Cách tôi nhìn thấy nó, tràn chỉ là một hình thức modulo, đó là num% (UINT_MAX + 1))

Answer 1

Exponentiation by squaring vẫn "hoạt động" cho phép tính lũy thừa modulo. Vấn đề của bạn không phải là 2^168277 là một số đặc biệt lớn, đó là một trong các kết quả trung gian của bạn là một số khá lớn (lớn hơn 2^32), bởi vì 673109 lớn hơn 2^16.

Vì vậy, tôi nghĩ những điều sau đây sẽ làm. Có thể tôi đã bỏ lỡ một chi tiết, nhưng ý tưởng cơ bản hoạt động, và đây là cách mã "mã hóa" thực sự có thể làm số mũ lũy thừa lớn (mặc dù không có số 32 bit và 64 bit, chứ không phải các bignums không bao giờ phải lớn hơn 2 * log (modulus)):

• Bắt đầu với lũy thừa theo bình phương, như bạn có.
• Thực hiện bình phương thực tế trong số nguyên không dấu 64 bit.
• Giảm modulo 673109 ở mỗi bước để quay lại trong phạm vi 32 bit, giống như bạn.

Rõ ràng đó là một chút khó xử nếu việc triển khai C++ của bạn không có số nguyên 64 bit, mặc dù bạn luôn có thể giả mạo.

Có một ví dụ trên trang trình bày 22 tại đây: http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf, mặc dù nó sử dụng số rất nhỏ (dưới 2^16), vì vậy nó có thể không minh họa bất cứ điều gì bạn chưa biết.

Ví dụ khác của bạn, 4000111222^3 % 1608 sẽ hoạt động trong mã hiện tại nếu bạn chỉ cần giảm 4000111222 modulo 1608 trước khi bắt đầu. 1608 đủ nhỏ để bạn có thể nhân một cách an toàn hai số mod-1608 trong một int 32 bit.

Answer 2

Hai điều:

• Bạn có sử dụng kiểu dữ liệu thích hợp? Nói cách khác, UINT_MAX có cho phép bạn có 673109 làm đối số không?

Không, nó không có, vì tại một thời điểm bạn có mã của bạn không hoạt động vì tại một thời điểm bạn có num = 2^16 và num = ... gây tràn. Sử dụng loại dữ liệu lớn hơn để giữ giá trị trung gian này.

• Làm thế nào về việc dùng modulo ở mọi oppertunity tràn có thể như:

  test = ((test % mod) * (num % mod)) % mod;

Edit:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod) 
{ 
    unsigned long long test; 
    unsigned long long n = num; 
    for(test = 1; pow; pow >>= 1) 
    { 
     if (pow & 1) 
      test = ((test % mod) * (n % mod)) % mod; 
     n = ((n % mod) * (n % mod)) % mod; 
    } 

    return test; /* note this is potentially lossy */ 
} 

int main(int argc, char* argv[]) 
{ 

    /* (2^168277) % 673109 */ 
    printf("%u\n", mod_pow(2, 168277, 673109)); 
    return 0; 
} 

Answer 3

Bạn có thể sử dụng danh tính sau:

(a * b) (mod m) === (a (mod m)) * (b (mod m)) (mod m)

Hãy thử sử dụng nó một cách đơn giản và từng bước cải thiện.

if (pow & 1) 
     test = ((test % mod) * (num % mod)) % mod; 
    num = ((num % mod) * (num % mod)) % mod; 

Answer 4

Tôi đã viết một cái gì đó cho điều này gần đây cho RSA trong C++, bit lộn xộn mặc dù.

#include "BigInteger.h" 
#include <iostream> 
#include <sstream> 
#include <stack> 

BigInteger::BigInteger() { 
    digits.push_back(0); 
    negative = false; 
} 

BigInteger::~BigInteger() { 
} 

void BigInteger::addWithoutSign(BigInteger& c, const BigInteger& a, const BigInteger& b) { 
    int sum_n_carry = 0; 
    int n = (int)a.digits.size(); 
    if (n < (int)b.digits.size()) { 
     n = b.digits.size(); 
    } 
    c.digits.resize(n); 
    for (int i = 0; i < n; ++i) { 
     unsigned short a_digit = 0; 
     unsigned short b_digit = 0; 
     if (i < (int)a.digits.size()) { 
      a_digit = a.digits[i]; 
     } 
     if (i < (int)b.digits.size()) { 
      b_digit = b.digits[i]; 
     } 
     sum_n_carry += a_digit + b_digit; 
     c.digits[i] = (sum_n_carry & 0xFFFF); 
     sum_n_carry >>= 16; 
    } 
    if (sum_n_carry != 0) { 
     putCarryInfront(c, sum_n_carry); 
    } 
    while (c.digits.size() > 1 && c.digits.back() == 0) { 
     c.digits.pop_back(); 
    } 
    //std::cout << a.toString() << " + " << b.toString() << " == " << c.toString() << std::endl; 
} 

void BigInteger::subWithoutSign(BigInteger& c, const BigInteger& a, const BigInteger& b) { 
    int sub_n_borrow = 0; 
    int n = a.digits.size(); 
    if (n < (int)b.digits.size()) 
     n = (int)b.digits.size(); 
    c.digits.resize(n); 
    for (int i = 0; i < n; ++i) { 
     unsigned short a_digit = 0; 
     unsigned short b_digit = 0; 
     if (i < (int)a.digits.size()) 
      a_digit = a.digits[i]; 
     if (i < (int)b.digits.size()) 
      b_digit = b.digits[i]; 
     sub_n_borrow += a_digit - b_digit; 
     if (sub_n_borrow >= 0) { 
      c.digits[i] = sub_n_borrow; 
      sub_n_borrow = 0; 
     } else { 
      c.digits[i] = 0x10000 + sub_n_borrow; 
      sub_n_borrow = -1; 
     } 
    } 
    while (c.digits.size() > 1 && c.digits.back() == 0) { 
     c.digits.pop_back(); 
    } 
    //std::cout << a.toString() << " - " << b.toString() << " == " << c.toString() << std::endl; 
} 

int BigInteger::cmpWithoutSign(const BigInteger& a, const BigInteger& b) { 
    int n = (int)a.digits.size(); 
    if (n < (int)b.digits.size()) 
     n = (int)b.digits.size(); 
    //std::cout << "cmp(" << a.toString() << ", " << b.toString() << ") == "; 
    for (int i = n-1; i >= 0; --i) { 
     unsigned short a_digit = 0; 
     unsigned short b_digit = 0; 
     if (i < (int)a.digits.size()) 
      a_digit = a.digits[i]; 
     if (i < (int)b.digits.size()) 
      b_digit = b.digits[i]; 
     if (a_digit < b_digit) { 
      //std::cout << "-1" << std::endl; 
      return -1; 
     } else if (a_digit > b_digit) { 
      //std::cout << "+1" << std::endl; 
      return +1; 
     } 
    } 
    //std::cout << "0" << std::endl; 
    return 0; 
} 

void BigInteger::multByDigitWithoutSign(BigInteger& c, const BigInteger& a, unsigned short b) { 
    unsigned int mult_n_carry = 0; 
    c.digits.clear(); 
    c.digits.resize(a.digits.size()); 
    for (int i = 0; i < (int)a.digits.size(); ++i) { 
     unsigned short a_digit = 0; 
     unsigned short b_digit = b; 
     if (i < (int)a.digits.size()) 
      a_digit = a.digits[i]; 
     mult_n_carry += a_digit * b_digit; 
     c.digits[i] = (mult_n_carry & 0xFFFF); 
     mult_n_carry >>= 16; 
    } 
    if (mult_n_carry != 0) { 
     putCarryInfront(c, mult_n_carry); 
    } 
    //std::cout << a.toString() << " x " << b << " == " << c.toString() << std::endl; 
} 

void BigInteger::shiftLeftByBase(BigInteger& b, const BigInteger& a, int times) { 
    b.digits.resize(a.digits.size() + times); 
    for (int i = 0; i < times; ++i) { 
     b.digits[i] = 0; 
    } 
    for (int i = 0; i < (int)a.digits.size(); ++i) { 
     b.digits[i + times] = a.digits[i]; 
    } 
} 

void BigInteger::shiftRight(BigInteger& a) { 
    //std::cout << "shr " << a.toString() << " == "; 
    for (int i = 0; i < (int)a.digits.size(); ++i) { 
     a.digits[i] >>= 1; 
     if (i+1 < (int)a.digits.size()) { 
      if ((a.digits[i+1] & 0x1) != 0) { 
       a.digits[i] |= 0x8000; 
      } 
     } 
    } 
    //std::cout << a.toString() << std::endl; 
} 

void BigInteger::shiftLeft(BigInteger& a) { 
    bool lastBit = false; 
    for (int i = 0; i < (int)a.digits.size(); ++i) { 
     bool bit = (a.digits[i] & 0x8000) != 0; 
     a.digits[i] <<= 1; 
     if (lastBit) 
      a.digits[i] |= 1; 
     lastBit = bit; 
    } 
    if (lastBit) { 
     a.digits.push_back(1); 
    } 
} 

void BigInteger::putCarryInfront(BigInteger& a, unsigned short carry) { 
    BigInteger b; 
    b.negative = a.negative; 
    b.digits.resize(a.digits.size() + 1); 
    b.digits[a.digits.size()] = carry; 
    for (int i = 0; i < (int)a.digits.size(); ++i) { 
     b.digits[i] = a.digits[i]; 
    } 
    a.digits.swap(b.digits); 
} 

void BigInteger::divideWithoutSign(BigInteger& c, BigInteger& d, const BigInteger& a, const BigInteger& b) { 
    c.digits.clear(); 
    c.digits.push_back(0); 
    BigInteger two("2"); 
    BigInteger e = b; 
    BigInteger f("1"); 
    BigInteger g = a; 
    BigInteger one("1"); 
    while (cmpWithoutSign(g, e) >= 0) { 
     shiftLeft(e); 
     shiftLeft(f); 
    } 
    shiftRight(e); 
    shiftRight(f); 
    while (cmpWithoutSign(g, b) >= 0) { 
     g -= e; 
     c += f; 
     while (cmpWithoutSign(g, e) < 0) { 
      shiftRight(e); 
      shiftRight(f); 
     } 
    } 
    e = c; 
    e *= b; 
    f = a; 
    f -= e; 
    d = f; 
} 

BigInteger::BigInteger(const BigInteger& other) { 
    digits = other.digits; 
    negative = other.negative; 
} 

BigInteger::BigInteger(const char* other) { 
    digits.push_back(0); 
    negative = false; 
    BigInteger ten; 
    ten.digits[0] = 10; 
    const char* c = other; 
    bool make_negative = false; 
    if (*c == '-') { 
     make_negative = true; 
     ++c; 
    } 
    while (*c != 0) { 
     BigInteger digit; 
     digit.digits[0] = *c - '0'; 
     *this *= ten; 
     *this += digit; 
     ++c; 
    } 
    negative = make_negative; 
} 

bool BigInteger::isOdd() const { 
    return (digits[0] & 0x1) != 0; 
} 

BigInteger& BigInteger::operator=(const BigInteger& other) { 
    if (this == &other) // handle self assignment 
     return *this; 
    digits = other.digits; 
    negative = other.negative; 
    return *this; 
} 

BigInteger& BigInteger::operator+=(const BigInteger& other) { 
    BigInteger result; 
    if (negative) { 
     if (other.negative) { 
      result.negative = true; 
      addWithoutSign(result, *this, other); 
     } else { 
      int a = cmpWithoutSign(*this, other); 
      if (a < 0) { 
       result.negative = false; 
       subWithoutSign(result, other, *this); 
      } else if (a > 0) { 
       result.negative = true; 
       subWithoutSign(result, *this, other); 
      } else { 
       result.negative = false; 
       result.digits.clear(); 
       result.digits.push_back(0); 
      } 
     } 
    } else { 
     if (other.negative) { 
      int a = cmpWithoutSign(*this, other); 
      if (a < 0) { 
       result.negative = true; 
       subWithoutSign(result, other, *this); 
      } else if (a > 0) { 
       result.negative = false; 
       subWithoutSign(result, *this, other); 
      } else { 
       result.negative = false; 
       result.digits.clear(); 
       result.digits.push_back(0); 
      } 
     } else { 
      result.negative = false; 
      addWithoutSign(result, *this, other); 
     } 
    } 
    negative = result.negative; 
    digits.swap(result.digits); 
    return *this; 
} 

BigInteger& BigInteger::operator-=(const BigInteger& other) { 
    BigInteger neg_other = other; 
    neg_other.negative = !neg_other.negative; 
    return *this += neg_other; 
} 

BigInteger& BigInteger::operator*=(const BigInteger& other) { 
    BigInteger result; 
    for (int i = 0; i < (int)digits.size(); ++i) { 
     BigInteger mult; 
     multByDigitWithoutSign(mult, other, digits[i]); 
     BigInteger shift; 
     shiftLeftByBase(shift, mult, i); 
     BigInteger add; 
     addWithoutSign(add, result, shift); 
     result = add; 
    } 
    if (negative != other.negative) { 
     result.negative = true; 
    } else { 
     result.negative = false; 
    } 
    //std::cout << toString() << " x " << other.toString() << " == " << result.toString() << std::endl; 
    negative = result.negative; 
    digits.swap(result.digits); 
    return *this; 
} 

BigInteger& BigInteger::operator/=(const BigInteger& other) { 
    BigInteger result, tmp; 
    divideWithoutSign(result, tmp, *this, other); 
    result.negative = (negative != other.negative); 
    negative = result.negative; 
    digits.swap(result.digits); 
    return *this; 
} 

BigInteger& BigInteger::operator%=(const BigInteger& other) { 
    BigInteger c, d; 
    divideWithoutSign(c, d, *this, other); 
    *this = d; 
    return *this; 
} 

bool BigInteger::operator>(const BigInteger& other) const { 
    if (negative) { 
     if (other.negative) { 
      return cmpWithoutSign(*this, other) < 0; 
     } else { 
      return false; 
     } 
    } else { 
     if (other.negative) { 
      return true; 
     } else { 
      return cmpWithoutSign(*this, other) > 0; 
     } 
    } 
} 

BigInteger& BigInteger::powAssignUnderMod(const BigInteger& exponent, const BigInteger& modulus) { 
    BigInteger zero("0"); 
    BigInteger one("1"); 
    BigInteger e = exponent; 
    BigInteger base = *this; 
    *this = one; 
    while (cmpWithoutSign(e, zero) != 0) { 
     //std::cout << e.toString() << " : " << toString() << " : " << base.toString() << std::endl; 
     if (e.isOdd()) { 
      *this *= base; 
      *this %= modulus; 
     } 
     shiftRight(e); 
     base *= BigInteger(base); 
     base %= modulus; 
    } 
    return *this; 
} 

std::string BigInteger::toString() const { 
    std::ostringstream os; 
    if (negative) 
     os << "-"; 
    BigInteger tmp = *this; 
    BigInteger zero("0"); 
    BigInteger ten("10"); 
    tmp.negative = false; 
    std::stack<char> s; 
    while (cmpWithoutSign(tmp, zero) != 0) { 
     BigInteger tmp2, tmp3; 
     divideWithoutSign(tmp2, tmp3, tmp, ten); 
     s.push((char)(tmp3.digits[0] + '0')); 
     tmp = tmp2; 
    } 
    while (!s.empty()) { 
     os << s.top(); 
     s.pop(); 
    } 
    /* 
    for (int i = digits.size()-1; i >= 0; --i) { 
     os << digits[i]; 
     if (i != 0) { 
      os << ","; 
     } 
    } 
    */ 
    return os.str(); 

Và sử dụng ví dụ.

BigInteger a("87682374682734687"), b("435983748957348957349857345"), c("2348927349872344") 

// Will Calculate pow(87682374682734687, 435983748957348957349857345) % 2348927349872344 
a.powAssignUnderMod(b, c); 

Nhanh quá và có số chữ số không giới hạn.

Answer 5

package playTime; 

    public class play { 

     public static long count = 0; 
     public static long binSlots = 10; 
     public static long y = 645; 
     public static long finalValue = 1; 
     public static long x = 11; 

     public static void main(String[] args){ 

      int[] binArray = new int[]{0,0,1,0,0,0,0,1,0,1}; 

      x = BME(x, count, binArray); 

      System.out.print("\nfinal value:"+finalValue); 

     } 

     public static long BME(long x, long count, int[] binArray){ 

      if(count == binSlots){ 
       return finalValue; 
      } 

      if(binArray[(int) count] == 1){ 
       finalValue = finalValue*x%y; 
      } 

      x = (x*x)%y; 
      System.out.print("Array("+binArray[(int) count]+") " 
          +"x("+x+")" +" finalVal("+    finalValue + ")\n"); 

      count++; 


      return BME(x, count,binArray); 
     } 

    } 

Answer 6

LL là dành cho long long int

LL power_mod(LL a, LL k) { 
    if (k == 0) 
     return 1; 
    LL temp = power(a, k/2); 
    LL res; 

    res = ((temp % P) * (temp % P)) % P; 
    if (k % 2 == 1) 
     res = ((a % P) * (res % P)) % P; 
    return res; 
} 

Sử dụng chức năng đệ quy trên cho việc tìm kiếm exp mod của số. Điều này sẽ không dẫn đến tràn vì nó tính toán theo cách từ dưới lên.

mẫu thử nghiệm chạy cho: a = 2 và k = 168277 cho thấy sản lượng là 518.358 đó là chính xác và chức năng chạy trong O(log(k)) thời gian;