How to deal with 128 bit variable in C++ with mingw32 bit compiler on qt platform ?

Question

0.00/5 (No votes)

See more:

Hi all, i am stuck in one euqation in cpp code, please help me to solve it,,

I am using,
Qt 4.8.7
Compiler MinGW32
(checked with boost library boost 1.70)

I want to use below equation in one of the code
A = g^a mod p; //g raise to a modulus p. (something like 2^5 % 3) = 32%3 = 2
(This equation looks like Diffie Hellman algorithm for security)

Where,
^(power)
g is fixed number 0x05
a is 128bit(16bytes) randomely generated number,
and p is fixed hex number of 128bit(16bytes) = (0xD4A283974897234CE908B3478387A3).

I am using Qt 4.8.7
with MinGW32 bit compiler,

I know this operation seems way to long(it is supposed to take some time), but this is requirement
from client, can`t be changed,

So does any one of you have any idea how to tackle this proble, then please let me know.

Thank you in advance.

What I have tried:

Solution i found which didn`t worked for me are listed below:
I got to know,
1 one can use __int128 but to support that one should have used
latest gcc compiler or MinGW64 bit compiler, neither of that i am using now.

2 I found one latest version of Qt has QSslDiffieHellmanParameters class,
but again not supported in our Qt version.

3 I found some libraries like boost/multiprecision/cpp_int.hpp (boost 1.70))
that does have data type such as int128_t and int256_t, but due to
our compiler isssue or something else, we are not able to store
128bit number, meaning
if i do,

C++

int128_t ptval128 = 0xAB1232423243434343BAE3453345E34B;
cout << "ptval128 = " << std::hex << ptval128 << endl;
//will print only 0xAB12324232434343;//half digits only,

4 I tried using Bigint which much more useful, but again
5^(128bit number) is way too big, it takes hours to compute things,
(I waited till 1 hour and 16 mins and kill the application).

Posted 9-May-19 22:59pm

Member 13663267

Updated 10-May-19 0:54am

Afzaal Ahmad Zeeshan

v2

Add a Solution

Comments

Richard MacCutchan 10-May-19 6:30am

The answer is obvious: you need to upgrade to a compiler that supports your requirements.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Answer 1 · 2019-05-10T00:54:00

First of all, you can significantly speed up the calculation of a power expression with a high integer exponent, by repeatedly squaring intermediate results, rather than just multiplying with the base. Here's a sample implementation that you can adapt to your prefered integer type:

C++

#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;
}

If you like, you can just paste it into this online C++ compiler[^] to see the results. As you can see, the number of multiplications are significantly less than the exponent. For a 128 bit exponent, the number of multiplications should be reduced to no more than 256.

With such a high exponent, it may be necessary to eliminate the recursion in this function and turn it into a loop instead. But that shouldn't be too hard.

Second, you don't need to calculate the total of g^a (which will be tricky to store), instead you can just insert a modulo p operation after every multiplication that puts the intermediate result above the value of p. This doesn't change the end result.