Re: Miller Rabin Primality Test Wrong Result

#include <iostream>
#include <sstream>
#include <string>
#include <bitset>
#include <vector>
#include <limits>
#include <algorithm>
#include <functional>
#include <utility>
 
#include <ctime>
 
using namespace std;
 
// Remark: Please avoid including the whole std namespace.
// Remark: Include only the necessary classes/functions.
 
// Remark: What is this magical constant?
const unsigned short NITE = 50;
 
// Remark: When you are presenting a test code you shoul
// Remark: make it simple. An int would suffice here.
// Remark: In fact gcc (GCC) 4.3.2 complains about it.
// typedef unsigned long long ulong;
 
void Userinput(ulong&);
bool MillerRabinPrimeTest(const ulong&);
ulong ComputeModularExponentiation(const ulong&, const ulong&, const
ulong&);
ulong ComputeExponentiation(const ulong&, const ulong&);
 
// Remark: There is almost no benefit by making an elementary data
// Remark: type like ulong pass by reference when it is a const at the
same time.
// Remark: It is advisable to just pass them by value.
 
int main(int argc, char* argv[])
{ ulong number(0);
 
    while (1)
    {
        cout << endl;
        Userinput(number);
        cout << boolalpha << MillerRabinPrimeTest(number);
    }
 
    return 0;
}
 
// Remark: When you are presenting a test code you can cut short the
// Remark: checking of input.
void Userinput(ulong& number)
{ cout << "Enter Number : ";
    cin >> number;
 
    while (cin.fail())
    { cin.clear();
        cin.ignore(numeric_limits<int>::max(), '\n');
 
        cout << "\nEnter Number : ";
        cin >> number;
    }
}
 
bool MillerRabinPrimeTest(const ulong& number)
{
    ulong a(0), x(0), y(0), tempNumber(0);
    bool IsPrime(false);
 
    tempNumber = number - 1;
 
    if (number > 2)
    {
        // Write them as 2 ^ s * d
        while (tempNumber % 2 == 0)
        {
            // tempNumber is d
            tempNumber /= 2;
        }
 
        for (int loop = 0;loop < NITE;++loop)
        {
            srand((unsigned int)time(0));
            // rand() % upperBound + startnumber
            a = rand() % (number - 2) + 2;
            // a = primeFactor[loop];
            // Remark: Are you sure this function is working
right?
            // Remark: Narrow down your problem area before
asking.
            x = ComputeModularExponentiation(a, tempNumber,
number);
 
            y = (x * x) % number;
            if (x == 1 || y == -1)
                return true;
        }
    }
 
    return IsPrime;
}
 
// Remark: I am sorry I do not have the follow the patience to follow
// Remark: your code here anymore. But I can tell you that you
// Remark: should be able to debug it yourself. Just confirm that each
// Remark: function is working as expected Individually. Never debug
// Remark: with all those untested component put together.
 
Regards,
Jyoti

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]