very large numbers for pow() and % (conflicting number types)

[mattayp]

So I'm writing my own RSA starting program, encoding program, and decryption program from scratch just for fun.

The problem I'm having is that pow() and % want different types of numbers to calculate, and that doing either function with large numbers is giving me number type errors (number type too small for calculation). For larger numbers, pow() wants to use doubles, or long doubles, but then % will not work with those number types. I'm too novice to know why or how to work around this.

Tried already: For loop for calculating my own pow manually, using std::pow over pow(), using fmod instead of %.

When I type the decryption into my TI-Nspire calculator it gives me back the correct number to decode just fine... why is c++ having such a hard time?

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <math.h>
#include <list>

using namespace std;

int main () {
    
    long int n;
    long int d;
    long int c;
    long int m=0;
    long double power=1;
    std::string message;

    cout<<"Enter n"<<endl;
    cin>>n;
    cout<<"Enter d"<<endl;
    cin>>d;
    
    ifstream inFile;
    inFile.open("encrypted.txt");
    if (!inFile) {
        cout << "Unable to open file";
        exit(1); // terminate with error
    }
    
    while (inFile >> c) 
    {

    long double std::pow(long double, long double); 
    power=pow(c,d);
    double m = std::fmod(power,n);

    cout<<"power="<<power<<" c="<<c<<" m="<<m<<endl;   
  	//letters
        if(m==1) {message += 'a';}      if(m==61){message += 'A';}
	if(m==2) {message += 'b';}	if(m==62){message += 'B';}
	if(m==3) {message += 'c';}	if(m==63){message += 'C';}
	if(m==4) {message += 'd';}	if(m==64){message += 'D';}
	if(m==5) {message += 'e';}	if(m==65){message += 'E';}
	if(m==6) {message += 'f';}	if(m==66){message += 'F';}
	if(m==7) {message += 'g';}	if(m==67){message += 'G';}
	if(m==8) {message += 'h';}	if(m==68){message += 'H';}
	if(m==9) {message += 'i';}	if(m==69){message += 'I';}
	if(m==10){message += 'j';}	if(m==70){message += 'J';}
	if(m==11){message += 'k';}	if(m==71){message += 'K';}
	if(m==12){message += 'l';}	if(m==72){message += 'L';}
	if(m==13){message += 'm';}	if(m==73){message += 'M';}
	if(m==14){message += 'n';}	if(m==74){message += 'N';}
	if(m==15){message += 'o';}	if(m==75){message += 'O';}
	if(m==16){message += 'p';}	if(m==76){message += 'P';}
	if(m==17){message += 'q';}	if(m==77){message += 'Q';}
	if(m==18){message += 'r';}	if(m==78){message += 'R';}
	if(m==19){message += 's';}	if(m==79){message += 'S';}
	if(m==20){message += 't';}	if(m==80){message += 'T';}
	if(m==21){message += 'u';}	if(m==81){message += 'U';}
	if(m==22){message += 'v';}	if(m==82){message += 'V';}
	if(m==23){message += 'w';}	if(m==83){message += 'W';}
	if(m==24){message += 'x';}	if(m==84){message += 'X';}
	if(m==25){message += 'y';}	if(m==85){message += 'Y';}
	if(m==26){message += 'z';}	if(m==86){message += 'Z';}
	
	//symobls
	if(m==27){message+=' ';}
	if(m==28){message+='.';}
	if(m==29){message+='?';}
	if(m==30){message+='!';}
	if(m==31){message+=',';}
	if(m==32){message+=';';}
	if(m==33){message+='@';}
	if(m==34){message+='#';}
	if(m==35){message+='$';}
	if(m==36){message+='%';}
	if(m==37){message+='^';}
	if(m==38){message+='&';}
	if(m==39){message+='*';}
	if(m==40){message+='(';}
	if(m==41){message+=')';}
	if(m==42){message+='-';}
	if(m==43){message+='_';}
	if(m==44){message+='=';}
	if(m==45){message+='+';}
	if(m==46){message+='[';}
	if(m==47){message+=']';}	
	if(m==48){message+='{';}
	if(m==49){message+='}';}	
	if(m==50){message+=':';}
	if(m==51){message+='<';}
	if(m==52){message+='>';}	
	if(m==53){message+='/';}
	if(m==54){message+='\\';}
	if(m==55){message+='|';}
	if(m==56){message+='`';}
	if(m==57){message+='~';}	
	
	//numbers
	if(m==100){message+='0';}
	if(m==101){message+='1';}
	if(m==102){message+='2';}
	if(m==103){message+='3';}
	if(m==104){message+='4';}
	if(m==105){message+='5';}
	if(m==106){message+='6';}
	if(m==107){message+='7';}
	if(m==108){message+='8';}
	if(m==109){message+='9';}

    }
    inFile.close();
    ofstream myFile;
    myFile.open("DEcryptedTEXT.txt");
    myFile<<message;


system("pause");
 
}

[Peter87]

Floating point numbers are often approximations so you shouldn't use them if you need the calculations to be precise. I have some vague memories of using modular arithmetic with large powers from a course in cryptography many years ago. If I remember correctly there should be a relatively efficient way of computing the combined pow/mod operation in situations when the pow operation alone would just be unreasonably big and time consuming to compute.

I think this is it: https://en.wikipedia.org/wiki/Modular_exponentiation

If long long is not enough you might have to use some kind of bignum library. In our course I think we used GMP (https://gmplib.org/). I think it had this pow/mod type of operation built in.

[lastchance]

Just some comments.

You are trying to work out c^d mod n ... by first working out c^d. You don't need to!
Just keep multiplying by c some d times ... finding the modulo result at each step. This will keep the numbers small.

#include <iostream>
using namespace std;

int cdn( int c, int d, int n )      // work out c^d mod n
{
   int value = 1;
   while( d > 0 )
   {
      value *= c;
      value %= n;
      d--;
   }
   return value;
}


int main()
{
   int c, d, n;
   cout << "Input c, d, n: ";   cin >> c >> d >> n;
   cout << "Result: " << cdn( c, d, n ) << endl;
}

Input c, d, n: 855 2753 3233
Result: 123

855²⁷⁵³ mod 3233 = 123
which is correct, according to https://simple.wikipedia.org/wiki/RSA_(algorithm)


Secondly, your long column of if statements is horrible.
Just do something like

   const string CIPHER = " abcdefgh...";   // You fill in the rest
...
   message += CIPHER[m];

[mattayp]

Thanks for both replies.

I'm trying to figure out how to install the GNU library into dev-c++ but everything I've found is confusing as hell.

For small primes I think lastchance's method should work fine.

I wouldn't say my if columns are "horrible" but probably not the most efficient. I'm not sure how your string method works (I only took one semester of c++ computer science like 10+ years ago).

[jonnin]

nevermind you already tried fmod. Missed that in the first read.

For small primes, you could just use a lookup table and binary search or a map.

the biggest thing you can use without a big num library are 10 byte floating points, if your system supports them. Most systems support 64 bit ints and a few support 128, past that you need a library again.