I'm trying to write miller-rabin test. I found few codes such as:
https://www.sanfoundry.com/cpp-program-implement-miller-rabin-primality-test/ https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/
Of course all this codes works for 252097800623 ( which is prime number ), but this is becaouse they are parsing it to int. When I changed all ints to long long in this codes they are now returning NO. I also wrote my own code based on another article and it worked when I was testing it with small numbers like 11, 101, 17 and even 1000000007, but chrashed on greater numbers like 252097800623. I want to write program that works for all integers from 1 to 10^18
EDIT
here is modified code form 1st link:
/*
* C++ Program to Implement Milong longer Rabin Primality Test
*/
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
* calculates (a * b) % c taking long longo account that a * b might overflow
*/
long long mulmod(long long a, long long b, long long mod)
{
long long x = 0,y = a % mod;
while (b > 0)
{
if (b % 2 == 1)
{
x = (x + y) % mod;
}
y = (y * 2) % mod;
b /= 2;
}
return x % mod;
}
/*
* modular exponentiation
*/
long long modulo(long long base, long long exponent, long long mod)
{
long long x = 1;
long long y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}
/*
* Milong longer-Rabin primality test, iteration signifies the accuracy
*/
bool Miller(long long p,long long iteration)
{
if (p < 2)
{
return false;
}
if (p != 2 && p % 2==0)
{
return false;
}
long long s = p - 1;
while (s % 2 == 0)
{
s /= 2;
}
for (long long i = 0; i < iteration; i++)
{
long long a = rand() % (p - 1) + 1, temp = s;
long long mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1)
{
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0)
{
return false;
}
}
return true;
}
//Main
int main()
{
long long iteration = 5;
long long num;
cout<<"Enter long longeger to test primality: ";
cin>>num;
if (Miller(num, iteration))
cout<<num<<" is prime"<<endl;
else
cout<<num<<" is not prime"<<endl;
return 0;
}
The code in the first link, which you replicated in your question, replacing the (bad) macro ll with long long (although this produces exactly the same preprocessed code) and all int with long long, is already broken for large values, see compiler explorer here. I forced the compiler to evaluate the Miller function for 252097800623 at compile time, replacing the call to rand() with one random number 123456.
As you can see the compiler is telling me that it cannot do so, because there are integer overflows in the program. In particular:
<source>:133:17: error: static_assert expression is not an integral constant expression
static_assert(Miller(num, iteration));
^~~~~~~~~~~~~~~~~~~~~~
<source>:62:12: note: value 232307310937188460801 is outside the range of representable values of type 'long long'
y = (y * y) % mod;
^
<source>:104:14: note: in call to 'modulo(123457, 63024450155, 252097800623)'
ll mod = modulo(a, temp, p);
^
<source>:133:17: note: in call to 'Miller(252097800623, 5)'
static_assert(Miller(num, iteration));
As you can see long long is simply too small to handle inputs that large to this algorithm.