congtuence modulo

[Lim Boon Jye]

Now i want to check that if value

int a = pow(9.0,100);
    int b = 81;
    int c = 547;

when i use a - b, the value should be can divide by c without remainder;

if( (a-b) % 547 == 0 )
         cout << "Correct" << endl;
    else
         cout << "Wrong" << endl;

but the output always go wrong and i see website links. the answer should be correct.

[Pindrought]

Here is your issue.

The max value for an int is -2147483648 to [phone]

9^10 generates a number greater than this. That being said, you can't store that value in an integer.

Another issue is that even if you change the type to long long int, you can only calculate up to 9^19 as 9^20 will be too large.


Why would you need to do 9^100 though? That's an extreme calculation

Edit: Note, I think that long long ints range from -9223372036854775808 to +9223372036854775808 but still are not even anywhere close to 9^100. 9^100 would be about 70-80 more digits.

[Lim Boon Jye]

yes. because i need to use that to check for elgamal signature.
just thinking how to handle those big numbers , any solution?

[a k n]

int can not store such a big value.(it has a range -2³¹ to 2³¹-1 on most systems.)
Further , it can't even be done using a double or any other basic data type.
You may use a multiple precision library to do it or use a different language.
See:
Modular exponentiation.

[a k n]

Lim Boon Jye wrote:

yes. because i need to use that to check for elgamal signature.
just thinking how to handle those big numbers , any solution?

Then , C++ is kinda the wrong language.
It can do such things.but its not easy.

[Lim Boon Jye]

that is an algorithm. sure can.
just someone who can help haven't see this thread.

[Pindrought]

The only way I can think of expressing that number in some form of data is by creating a different base number system and store the values in strings. It'd probably be suitable to use something like base 40 or 50. However, it would be an insane amount of work, and not only that, but you'd have to rewrite your own version of mod (%) since it wouldn't support your new base numbers.

There may be other ways, i'm just not sure how.

[Lim Boon Jye]

mean? @pindrought. how will you do it?

[a k n]

See gmp . GNU multi-precison library.

EDIT:
If you are still interested , Here's an example code using gmp and gmpxx.
Using mpz.

#include <iostream>
#include <gmp.h>
#include <gmpxx.h>

int main()
{
	mpz_class base = 9,mod = 547,ans;
	mpz_powm_ui(ans.get_mpz_t(),base.get_mpz_t(),100,mod.get_mpz_t());
	std::cout << ans << std::endl;
	return 0;
}

Output:

81

Read Further:
https://gmplib.org/
https://gmplib.org/manual/
https://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation
https://gmplib.org/manual/C_002b_002b-Interface-General.html