Модульное экспонирование

Question

Модульное экспонирование

Я пытаюсь использовать Этот метод чтобы разбить базы с большими показателями, потому что типы данных в стандартной библиотеке C ++ не хранят такие большие числа.

Проблема в последнем цикле, где я использую fmod() функция мод моих больших чисел. Ответ должен быть 1, но я получаю 16. Кто-то видит проблему?

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

typedef vector<int> ivec;
ivec binStorage, expStorage;

void exponents()
{
for (int j=binStorage.size(); j>=0; j--)
if(binStorage[binStorage.size()-j-1]!=0)
expStorage.push_back(pow(2, j));
}

void binary(int number)
{
int remainder;

if(number <= 1)
{
cout << number;
return;
}

remainder = number%2;
binary(number >> 1);
cout << remainder;
binStorage.push_back(remainder);
}

int main()
{
int num = 117;
int message = 5;
int mod = 19;
int prod = 1;
binary(num);
cout << endl;
exponents();

cout << "\nExponents: " << endl;
for (int i=0; i<expStorage.size(); i++)
cout << expStorage[i] << " " ;

cout << endl;
cout << "\nMessage" << "-" << "Exponent" << endl;
for (int i=0; i<expStorage.size(); i++)
{
cout << message << "-" << expStorage[i] << endl;
prod *= fmod(pow(message, expStorage[i]), mod);
}
cout << "\nAnswer: " << fmod(prod, mod) << endl;
return 0;
}

Вот мои результаты:

1110101

Exponents:
64 32 16 4 1

Message-Exponent
5-64
5-32
5-16
5-4
5-1

Answer: 16

Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.

Редактировать:
Вот проблема цикла.

for (int i=0; i<expStorage.size(); i++)
{
cout << message << "-" << expStorage[i] << endl;
prod *= fmod(pow(message, expStorage[i]), mod);
}

1

c++math modular

Решение

Другие решения

Источник

Accepted Answer

Вы разместили алгоритм модульный алгоритм возведения в степень. Следуя шагам в ссылке, которую вы разместили, алгоритм сводится к следующему коду:

#include <iostream>
#include <cmath>

// B : Base
// E : Exponent
// M : Modulo
constexpr int powermod(int const B, int const E, int const M) {
return ((E > 1) ? (powermod(B, E / 2, M) * powermod(B, E / 2, M) * powermod(B, E % 2, M)) % M
: (E == 0) ? 1 : B % M);
}

int main() {
int const e = 117;
int const b = 5;
int const m = 19;

std::cout << "Answer: " << powermod(b, e, m) << std::endl;

return 0;
}

Обратите внимание, что я использовал constexpr, Если ваш компилятор не поддерживает его, вы можете удалить его. С помощью constexpr и при условии, что входные аргументы являются константными выражениями, как в примере выше, вычисление степенной экспоненты будет происходить во время компиляции.

Теперь относительно кода, который вы разместили:

Кажется, что fmod плохо работает с большими числами лайк (5^32 а также 5^64) и дает ложные результаты.
Также ваш код страдает от ошибок компиляции и ошибок времени выполнения, поэтому я исправил это.
Я кодировал алгоритм, который вычисляет по модулю на основе рекурсии. По сути, это вариант алгоритма, который я выложил выше, с защитной силой 4 (см. Функцию safemod() ниже):

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef vector<int> ivec;

// B : Base     (e.g., 5)
// E : Exponent (e.g., 32)
// M : Modulo   (e.g., 19)
double safemod(double B, double E, double M) {
return ((E > 4) ? fmod(safemod(B, E / 2, M) * safemod(B, E / 2, M), M)
:
fmod(pow(B, E), M));
}

void exponents(ivec const &binStorage, ivec &expStorage) {
int j(pow(2.0, binStorage.size() - 1));
for (vector<int>::const_iterator it(binStorage.begin()), ite(binStorage.end()); it != ite; ++it) {
if (*it != 0) expStorage.push_back(j);
j /= 2;
}
}

void binary(int const number, ivec &binStorage) {
if (number > 0) {
int remainder = number % 2;
binary(number / 2, binStorage);
binStorage.push_back(remainder);
}
}

int main() {
int num     = 117;
int message = 5;
int mod     = 19;
int prod    = 1;
ivec binStorage, expStorage;

binary(num, binStorage);
for (size_t i(0); i < binStorage.size(); ++i) cout << binStorage[i];
cout << endl;

exponents(binStorage, expStorage);
cout << "\nExponents: " << endl;
for (size_t i(0); i<expStorage.size(); ++i) cout << expStorage[i] << " ";
cout << endl;

cout << "\nMessage" << "-" << "Exponent" << endl;
for (size_t i(0); i<expStorage.size(); ++i) {
cout << message << "-" << expStorage[i] << endl;
prod *= safemod(message, expStorage[i], mod);
}

cout << "\nAnswer: " << fmod(prod, mod) << endl;

return 0;
}

Выход:

1110101

Экспоненты:
64 32 16 4 1

Message-экспонент

5 — 64

5 — 32

5 — 16

5 — 1

Ответ: 1

1