dimanche 29 mars 2015

Odd math error in Java



I'm writing a program to demonstrate Miller-Rabin probability testing in Java. The code is pretty much done...



import java.util.Random;
import java.util.Scanner;

/**
* Program to demonstrate Miller-Rabin primality testing
*
* @author Nick Gilbert
*/
public class MillerRabin
{
public static void main(String[] args)
{
//Setting up for algorithm
Scanner in = new Scanner(System.in);
Random rn = new Random();
int n = 0, k = 0, m = 0, a = 0;
double b = 0;
boolean probablyPrime = false;

//Asking user for an odd n
do
{
System.out.print("Enter an odd number to test for primality: ");
n = in.nextInt();
}
while(n % 2 == 0);

//Calculating k and m
m = n - 1;
while(m % 2 == 0)
{
m /= 2;
k++;
}

//Generating random a
//a = rn.nextInt(n-1);

//Outputting numbers that will be used in algorithm
System.out.println("k = " + k);
System.out.println("m = " + m);
System.out.println();
a = 86;
System.out.println("A = " + a);

//Running the algorithm
//b_{0}
b = Math.pow(a, m) % n;
System.out.println("b0 = " + b);
if(Math.abs(b) == Math.abs(1 % n)) //Dealing with +/- case via absolute value
{
probablyPrime = true;
}
else
{
//b_{1-(k-1)}
for(int i = 1; i < k; i++) //Going to k-1
{
b = Math.pow(b, 2) % n;
System.out.println("b" + i + " = " + b);
if(Math.abs(b) == Math.abs(1 % n)) //Dealing with +/- case via absolute value
{
probablyPrime = true;
break;
}
}
}

//Printing result
if(probablyPrime)
{
System.out.println("Probably Prime");
}
else
{
System.out.println("Definitely Composite");
}


}
}


I've hard-coded 86 as my a value to demonstrate my problem. Where it calculates b for the first time by raising a to the m and taking the modulus n the math is incorrect. Instead of giving a b0 of 86 which is the correct answer to 86^19 % 153 it gives me b0 equals 107. I've checked my values in the debugger and they are right. I've also checked the value of a^m and it gives me 86^19 so the problem occurs with the modulus part. Unfortunately I don't know what is throwing the math off.




Aucun commentaire:

Enregistrer un commentaire