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?
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.
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.
You are trying to work out cd mod n ... by first working out cd. 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>
usingnamespace 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;
}
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).
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.