Big numbers

[nameless987]

Hey... do anyone knows c++ function for implementation of big numbers...i tried googl it...but, i can't find nothing that solve my problem

i need to calculate a^e(mod n)

example:

125^107 (mod 187)=5

result of 125^107 is too big for standard notation in c++...

can someone please help me!

[Ancient Dragon]

try these google links

[nameless987]

Now I have problem with fmod...

i calculated with y=pow(a,e)

then fmod(y,n)... but now i seems that that fmod has to small range of results (same thing is with %)
is there some other function for mod?

[TheBeast32]

Use the GMP library. It works for me. If you're using Dev-C++, you can just search for packages online with the built in "Check for updates/packages" thing, and find it in the list. If not go here: http://gmplib.org/

[nameless987]

How to instal GMP library....dev c++ won'r downlod it, and i don't knoe how to install one i have downloaded from http://gmplib.org/

[grumpier]

Talking about using a sledgehammer to crack a nut. No need to use high precision integers at all.

(a^b) mod c can be evaluated using a loop, using modulo arithmetic.

The basic property you need to know is that (x*y) mod z is equal to ((x mod z)*(y mod z)) mod z). From that it is possible to compute (a^b) mod c. I'll leave the precise code as an exercise.

[TheBeast32]

Dev-C++ WILL download it. You have to pick the option in the package downloader that says community devpaks, scroll down and find it. Download it, and it should automatically bring you to an installer.

[nameless987]

I tried to download it in that way...but i get some error that this file doesn't exist..

i figured out that i must use this kind calculations if i want to work with big nombers:
P = Cd % n
= 62^65 % 133
= 62 * 62^64 % 133
= 62 * (62^2)32 % 133
= 62 * 3844^32 % 133
= 62 * (3844 % 133)^32 % 133
= 62 * 120^32 % 133
.
.
.
= 62 * 36^16 % 133
= 62 * 99^8 % 133
= 62 * 92^4 % 133
= 62 * 85^2 % 133
= 62 * 43 % 133
= 2666 % 133
= 6

How can i write this in c++?
please help

[TheBeast32]

i'll attack the devpak! =)

[grumpier]

i figured out that i must use this kind calculations if i want to work with big nombers:
P = Cd % n
= 62^65 % 133
= 62 * 62^64 % 133
= 62 * (62^2)32 % 133
= 62 * 3844^32 % 133
= 62 * (3844 % 133)^32 % 133
= 62 * 120^32 % 133
.
.
.
= 62 * 36^16 % 133
= 62 * 99^8 % 133
= 62 * 92^4 % 133
= 62 * 85^2 % 133
= 62 * 43 % 133
= 2666 % 133
= 6

How can i write this in c++?
please help

Try to express it as a loop construct. Your logic here is, mathematically, equivalent to what I said in my previous post.

[nameless987]

The basic property you need to know is that (x*y) mod z is equal to ((x mod z)*(y mod z)) mod z). From that it is possible to compute (a^b) mod c. I'll leave the precise code as an exercise.

can you explain me how can i this basic property use for (a^b) mod c.

i'm not that good with this kind of math :$

[grumpier]

Look at a small example

(21^5) mod 13

Step 1: 21 mod 13 = 8 (i.e remainder on dividing 21 by 13 is 8).

Step 2: ((21 mod 13) * (21 mod 13)) mod 13 = (8 * 8) mod 13 = 64 mod 13 = 12. This means 21^2 mod 13 = 12

Step 3: Use fact (from step 2) that 21^2 mod 13 is 12 and (from step 1) 21 mod 13 is 8. So 21^3 mod 13 = ((21^2 mod 13)*(21 mod 13)) mod 13 = (12*8) mod 13 = 96 mod 13 = 5.

Step 4: Use fact (from step 3) that 21^3 mod 13 = 5 and (from step 1) that 21 mod 13 = 8. So 21^4 mod 13 = ((21^3 mod 13) * (21 mod 13)) mod 13 = (5*8) mod 13 = 40 mod 13 = 1.

Step 5: Use fact (from step 4) that 21^4 mod 13 = 1 and (from step 1) that 21 mod 13 = 8. 21^5 mod 13 = ((21^4 mod 13) * (21 mod 13)) mod 13 = (1*8) mod 13 = 8 mod 13 = 8.

I've used a small values here (i.e. you can compute 21^5 by hand, and then find the remainder on dividing by 13). And you will find - if you do it that way - it is 8. The difference is that the method I've described will also work for 21^65 mod 30001 (albeit more iterations) without producing a value that can't be stored in a 32 bit integer along the way.

[nameless987]

for(i=0;i<strlen(pra);i++)
  {
     tra=c[i];
     y=1;
	 for(int u=0;u<d;u++)
	 {
         y*=tra%n;
		 y=y%n;
	 }
	 p2[i]=y;

i use this code for calculating tra^d mod n
all numbers are int (tra, y, n, d)
it works for numbers
tra=31
d=7
n=33

but for numbers
tra=64
d=233
n=781
doesn't work

[grumpier]

Ah. I forgot to take into account all the constraints to reduce overflow. You're probably using a 16 bit integer. n^2 needs to be representable in your integer type. 781^2 will not be representable in a 16 bit int, but will be with a 32 bit integer.

You can push to larger values of n by using the modulo relationship for addition (a + b) mod n = ((a mod n) + (b mod n)) mod n. If you use that, only 2*n needs to be representable in your integer type.

[iamthwee]

I would definitely recommend using the GMP library here.

I have dev-cpp and this is how I used it.

1) Download the devpack zip file provided by theBeast32
2) Unzip it.
3) Copy it into the directory C:\Dev-Cpp\Packages 4) Run it.
5) Open up Dev-cpp and create a console windows project.
6) Now the important bit.

Go to Tools > compiler options >

and paste into the box 'Add the following commands when calling the compiler':

-lgmpxx -lgmp

Make sure to tick the box is ticked.

test code

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

using namespace std;

mpz_class factorial ( mpz_class, mpz_class );

int main()
{
  mpz_class a, b, c; 
  a = "125";
  b = "107";

  c = factorial ( a, b );

  cout << c;
  getchar();
  return 0;
}

mpz_class factorial ( mpz_class a, mpz_class b )
{
  mpz_class c = a;

  for ( mpz_class i = b; i > 1; i-- )
  {
    c = c * a;
  }
  return c;
}

Now just hit the compile and run button.

output

23408381773460991635779247069293382849575116693970916581685777269301916383369998
24743317548769632316721526895315710009819587668709957465602306134616903764463545
37270758622261454531755971164574958720550057478249073028564453125

And you can even use the modulus operator as normal which is %