Модульное экспонент для больших чисел в C ++
https://stackoverflow.com/questions/2207006
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Итак, я недавно работал над реализацией теста первичности Миллера. Я ограничиваю это на сферу всех 32-битных цифр, потому что это просто проект, который я делаю, чтобы познакомиться с C ++, и я не хочу работать с чем-либо 64-битами для какое-то время. Дополнительный бонус заключается в том, что алгоритм является детерминированным для всех 32-битных чисел, поэтому я могу значительно повысить эффективность, потому что я точно знаю, на что свидетельствуют.
Таким образом, для низких чисел алгоритм работает исключительно хорошо. Однако часть процесса зависит от модульного экспоненты, то есть (num ^ pow) % мод. Так, например,
3 ^ 2 % 5 =
9 % 5 =
4
Вот код, который я использовал для этого модульного экспоненты:
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;
}
Как вы уже догадались, проблемы возникают, когда аргументы являются исключительно большими числами. Например, если я хочу проверить номер 673109 на первичность, я в какой -то момент должен найти:
(2 ^ 168277) % 673109
Теперь 2 ^ 168277 - это исключительно большое количество, и где -то в процессе он переполняет тест, что приводит к неправильной оценке.
С обратной стороны аргументы, такие как
4000111222 ^ 3 % 1608
Также неправильно оцените по той же причине.
Есть ли у кого -нибудь предложения по модульному экспоненты таким образом, чтобы это могло предотвратить переполнение и/или манипулировать им для получения правильного результата? (Как я его вижу, переполнение - это просто еще одна форма модуля, то есть num % (uint_max+1)))
Решение
Экспонент в квадрате до сих пор «работает» для экспоненты модуля. Ваша проблема не в этом 2 ^ 168277 является исключительно большим числом, это то, что одним из ваших промежуточных результатов является довольно большое количество (больше 2^32), потому что 673109 больше, чем 2^16.
Так что я думаю, что следующее подойдет. Возможно, я пропустил детали, но основная идея работает, и именно так «реальный» крипто-код может сделать большую мод-эксппониацию (хотя не с 32 и 64-битными числами, скорее, с биньями, которые никогда не должны становиться больше, чем 2 * log (modulus)):
- Начните с экспоненты с квадрата, как у вас есть.
- Выполните фактический квадрат в 64-битном целом без знака.
- Уменьшите модул 673109 на каждом шаге, чтобы вернуться в 32-разрядную диапазон, как вы.
Очевидно, что это немного неловко, если ваша реализация C ++ не имеет 64 -битного целого числа, хотя вы всегда можете придумать.
Здесь есть пример на слайде 22: http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf, хотя он использует очень маленькие числа (менее 2^16), поэтому он может не иллюстрировать ничего, чего вы еще не знаете.
Ваш другой пример, 4000111222 ^ 3 % 1608 будет работать в вашем текущем коде, если вы просто уменьшите 4000111222 модуло 1608 прежде чем ты начнешь. 1608 достаточно мало, чтобы вы могли безопасно умножить любые два числа MOD-1608 в 32-битном INT.
Другие советы
Я написал кое -что для этого недавно для RSA в C ++, хотя немного грязно.
#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();
И пример использования.
BigInteger a("87682374682734687"), b("435983748957348957349857345"), c("2348927349872344")
// Will Calculate pow(87682374682734687, 435983748957348957349857345) % 2348927349872344
a.powAssignUnderMod(b, c);
Это тоже быстро и имеет неограниченное количество цифр.
Две вещи:
- Вы используете соответствующий тип данных? Другими словами, позволяет ли Uint_max иметь 673109 в качестве аргумента?
Нет, это не так, поскольку в какой -то момент у вас есть код, не работает, потому что в какой -то момент у вас есть num = 2^16 и num = ... вызывает переполнение. Используйте больший тип данных для сохранения этого промежуточного значения.
Как насчет того, чтобы принять модуло при каждом возможном переполнении, например:
test = ((test % mod) * (num % mod)) % mod;
Редактировать:
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;
}
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);
}
}
LL для 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;
}
Используйте вышеуказанную рекурсивную функцию для поиска модного эксплуатации числа. Это не приведет к переполнению, потому что оно рассчитывается внизу вверх.
Образец тестового запуска для:a = 2 а также k = 168277 Показывает вывод 518358, который является правильным, и функция работает в O(log(k)) время;
Вы можете использовать следующую идентичность:
(a * b) (mod m) === (a (mod m)) * (b (mod m)) (mod m)
Попробуйте использовать его прямо и постепенно улучшить.
if (pow & 1)
test = ((test % mod) * (num % mod)) % mod;
num = ((num % mod) * (num % mod)) % mod;
