Member 13663267 Ответов: 1

Как работать со 128-битной переменной в C++ с помощью mingw32-битного компилятора на платформе qt ?

Привет всем, я застрял в одном euqation в коде cpp, пожалуйста, помогите мне решить эту проблему,,

Я использую,
Qt 4.8.7
Компилятор MinGW32
(проверено с помощью boost library boost 1.70)

Я хочу использовать приведенное ниже уравнение в одном из кодов
A = g^a mod p; //g поднять до модуля p. (что-то вроде 2^5 % 3) = 32%3 = 2
(Это уравнение выглядит как алгоритм Диффи Хеллмана для обеспечения безопасности)

Где,
^(сила)
g - фиксированное число 0x05
a-это 128-битное(16 байт) случайно сгенерированное число,
и P является фиксированной шестнадцатиричное число из 128 бит(16-байтовая) = (0xD4A283974897234CE908B3478387A3).

Я использую Qt 4.8.7
с помощью MinGW32 битного компилятора,


Я знаю, что эта операция кажется слишком долгой(предполагается, что она займет некоторое время), но это требование
от клиента, не может быть изменен,

Так что если у кого-нибудь из вас есть идеи, как решить эту проблему, пожалуйста, дайте мне знать.

Заранее спасибо.

Что я уже пробовал:

Решение, которое я нашел, которое не сработало для меня, перечислены ниже:
Я должен знать,
1 можно использовать __int128, но для поддержки этого нужно было использовать
последний компилятор gcc или MinGW64-битный компилятор, ни то, ни другое я сейчас не использую.

2 я нашел одну последнюю версию Qt с классом QSslDiffieHellmanParameters,
но опять же не поддерживается в нашей версии Qt.

3 я нашел некоторые библиотеки, такие как boost/multiprecision/cpp_int.hpp (boost 1.70))
это действительно имеет тип данных, такой как int128_t и int256_t, но из-за
наш компилятор isssue или что-то еще, мы не можем хранить
128-битное число, означающее
если я это сделаю,
int128_t ptval128 = 0xAB1232423243434343BAE3453345E34B;
cout << "ptval128 = " << std::hex << ptval128 << endl;
//will print only 0xAB12324232434343;//half digits only,


4 я попробовал использовать Bigint, который гораздо полезнее, но опять же
5^(128-битное число) - это слишком много, на вычисления уходят часы,
(Я подождал до 1 часа и 16 минут и убил приложение).

Richard MacCutchan

Ответ очевиден: вам нужно перейти на компилятор, поддерживающий ваши требования.

1 Ответов

Рейтинг:
2

Stefan_Lang

Прежде всего, вы можете значительно ускорить вычисление степенного выражения с высоким целочисленным показателем, многократно возведя в квадрат промежуточные результаты, а не просто умножая с базой. Вот пример реализации, которую вы можете адаптировать к вашему предпочтительному целочисленному типу:

#include <iostream>

using namespace std;

#define TEST_PERFORMANCE 1

#ifdef TEST_PERFORMANCE
int n_mult;
#endif
int fast_power(int base, unsigned int exponent)
{
    if (exponent == 0)
       return 1;
    int result = fast_power(base, exponent/2);
    result *= result; // result = base ^ (2 * base/2)
#ifdef TEST_PERFORMANCE
    n_mult++; // counting multiplications to get an estimate for performance
#endif
    if (exponent & 1) // is exponent odd ?
    {
        result *= base;
#ifdef TEST_PERFORMANCE
        n_mult++;
#endif
    }
    return result;
}

int main()
{
#ifdef TEST_PERFORMANCE
    n_mult = 0;
#endif
    cout << "2^10 = " << fast_power(2,10) << endl;
#ifdef TEST_PERFORMANCE
    cout << "multiplications used: " << n_mult << endl;
    n_mult = 0;
#endif
    cout << "2^17 = " << fast_power(2,17) << endl;
#ifdef TEST_PERFORMANCE
    cout << "multiplications used: " << n_mult << endl;
    n_mult = 0;
#endif
    cout << "2^30 = " << fast_power(2,30) << endl;
#ifdef TEST_PERFORMANCE
    cout << "multiplications used: " << n_mult << endl;
#endif

    return 0;
}
Если хотите, вы можете просто вставить его в этот онлайн-компилятор C++ [^] чтобы увидеть результаты. Как видите, число умножений значительно меньше показателя степени. Для 128 - битной экспоненты число умножений должно быть уменьшено не более чем до 256.

При таком высоком показателе может потребоваться устранить рекурсию в этой функции и вместо этого превратить ее в цикл. Но это не должно быть слишком сложно.

Во-вторых, вам не нужно вычислять общее число g^a (которое будет сложно хранить), вместо этого вы можете просто вставить операцию по модулю p после каждого умножения, которая ставит промежуточный результат выше значения p. Это не меняет конечного результата.