C++ Using Bignum

[cburwell]

I am trying to do some RSA encryption and decryption for one of my classes. If you have looked at RSA encryption you know that it envolves rasing numbers to large powers (6^23 in the first problem I am doing). The answer that these exponents yeild will be too large for any standard var. in C++ (I am using Visual C++ .net).

My professor told me that if I wanted to wirte a C++ program to handle a certain portion of the encryption process then I would have to use bignum.h. I have found this library and I think I am using it right. The problem is when I go to print my answer, which is a Bignum variable, I cannot seem to do so with standard print functions.

I was wondering if anyone had any idea on how I can print this variable. Here is the code that I have written:

#include "Bignum.h"
#include <iostream>
#include <cmath>
#include <stdio.h>

void main ()
{
	Bignum answer;
	int base = 6;
	int exp  = 17;
	int divisor = 21;
	double c;

	c = pow(base,exp);
	answer = fmod(c, divisor);

	//cout << answer;

	return;
}

The cout statement that is commented out will give me an error if I try to use it. Otherwise the program will compile and run just fine. Any ideas on how I can print the Bignum answer variable?

 

[mikeblas]

What's BIGNUM.H? It isn't any standard library that I'm aware of -- searching the web for it gives lots of varied hits.

And so you have some unknown code in some unknown library. You can ask your professor (or a TA, or a tutor, or a lab assistant, or whatever support structure you students have these days) for help or documentation.

Or you can track down the docs yourself.

Maybe you can look at the source for the the library to see what interfaces it supports and figure out how you might be able to print. Maybe there's a function which returns a string, or an overloaded operator<< that will do what you want.

If you can not sort out the source yourself, post it here so we can see it and get you pointed in the right direction.

 

[cburwell]

I tryed to understand the code in the bignum.h I have found, and it is above anything I can understand.

Here is the one version of bignum.h that I am trying to use:

// 3.18.05  Modified the constructor to set the sign bit to 1 instead of 0 for constructing bignum zero.

#define MAXDIGITS 26
#define MAX ((unsigned) (-1))
#define NN 32
#define ZERO(u)  (u.ln==1 && u.digits[0]==0)
#define EVEN(u)  (!(u.digits[0] & 1))
#define ODD(u)   (u.digits[0] & 1)
#define BIT(b,i) (( b.digits[i/NN] & (1 << (i % NN))) ? 1 : 0)  // i-th bit of bignum b
typedef unsigned digit;
#define LEFTDIGIT ((unsigned)(1 << (NN-1)))     /* 1 in the leftmost place of a digit */
void longdiv(unsigned x, unsigned y, unsigned z, unsigned *q, unsigned *r);
void longmult(unsigned x, unsigned y, unsigned *lo, unsigned *hi);
#include <string>
using namespace std;

// Class Bignum works with numbers up to MAXDIGITS digits base 2^32.

// Note that we don't need division at all, which is the hardest of the arithmetic
// algorithms to implement.

// All elements of the digits array digits[k] for k >= ln will be zero.

class Bignum{
public:
  unsigned ln;
  int sign;
  unsigned digits[MAXDIGITS];
  Bignum()
    { memset(digits,0,MAXDIGITS*sizeof(int));
      ln = 1;
      digits[0] = 1;
      sign = 1;
    }
  Bignum(unsigned long long k)
    { memset(digits,0,MAXDIGITS*sizeof(int));
      sign = 1;
      if(k <= 0xffffffff)
        { ln = 1;
          digits[0] = (digit) k;
        }
      else
        { ln = 2;
          digits[0] = (digit) (k % ((long long) 1 << 32));
          digits[1] = (digit)(k >> 32);
        }
    }
  Bignum(string x);   // convert decimal representation to Bignum
  string toString();   // string representation base 1000000000  only
};

 Bignum operator+(Bignum x, Bignum y);
 Bignum operator-(Bignum x);
 Bignum operator-(Bignum x, Bignum y);
 Bignum operator*(Bignum x, Bignum y);
 Bignum operator*(Bignum x, digit y);
 Bignum operator*(digit x, Bignum y);
 Bignum operator%(Bignum x, Bignum m);
 digit operator%(Bignum x, digit m);
 int operator>(Bignum x, Bignum y);
 int operator<(Bignum x, Bignum y);
 int operator==(Bignum x, Bignum y);
 int operator<=(Bignum x, Bignum y);
 int operator>=(Bignum x, Bignum y);
 int operator!=(Bignum x, Bignum y);
 Bignum ExtGCD(Bignum u, Bignum v, Bignum *A, Bignum *B);
 Bignum BinaryGCD(Bignum u, Bignum v);
 void left_shift(Bignum x, int i, Bignum *y);
 void right_shift(Bignum x, int i, Bignum *y);
 void divide_by_digit(Bignum x, digit y, Bignum *q, digit *r);
 int bigdivide(Bignum x, Bignum y, Bignum *q, Bignum *r);
 Bignum biggcd(Bignum x, Bignum y);
 int PrimalityTest(Bignum b);

I have also found this version of bignum.h, but I can't seem to get it to work.

http://cvs.opensolaris.org/source/raw/on/usr/src/common/bignum/bignum.h

 

[HHunt]

I tried to understand the code in the bignum.h I have found, and it is above anything I can understand.

I have also found this version of bignum.h, but I can't seem to get it to work.

http://cvs.opensolaris.org/source/raw/on/usr/src/common/bignum/bignum.h

Well, I'd be really suprised if an openSolaris header worked with VC++.
(You're not supposed to drop in header files on their own; Find something that's already installed, or a package with something more than just headers.)

edit: You could try GMP, perhaps?
No, I don't have any experience with it. Documentation here.

 

[cburwell]

Thank you. I will see what I can find. As you can see I am not all that used to doing much more then printing "Hello World"!

 

[mikeblas]

Taking a closer look at your code, I don't think it's working the way you expect. You're going to compute 6^17, which is 16926659444736 according to Mathematica. That's going to take about 44 bits to represent in binary, but you're just storing the result in a double, then doing math on the double which will cause you to loose precision.

I think you want to represent everything as bignums; or at least use other types only when you're completely sure that you won't loose precision when you're doing the math. Here, you almost certainly will loose precision.

Anyway, for the header you've posted, this method looks promising:

string toString();   // string representation base 1000000000  only

Why not try something like this?

	//cout << answer;
string str = answer.toString();
cout << str << endl;

I can't guarantee that will work since the header isn't my own code and I don't know what's behind it. I have a guess at what the comment means, but I don't see a way to set the base the class is using for its storage.

For the header you linked, I would think that this function is the most interesting:

void printbignum(char *aname, BIGNUM *a);

Something like this:

//cout << answer;
char sz[100]; // number better not be more than 99 digits!
printbignum(sz, &answer);
cout << sz << endl;

is probably what the author intended you to do.

The only way to know for sure is to find the owner of the library and ask, or get the documentation for it.