T
transkawa
i wrote this here little program and it gives me misleading result. can
someone help confirm for me if my code is wrong or just because of the
nature of the test. it's a test for primality of a number using fermat's
little theorem.
the following functions are okay; they were embedded from another
program I wrote: square, fastExpt, evenOrNot and evenN.
I just want to confirm only on the fermatTest(n) function.
sorry for the long verbose below:
/*
* program for fermat's test for primality. if n is prime and a is any
positive
* integer less than n, then a raised to the nth power is congruent to
* a modulo n.
*/
function fermatTest(n){
//get a random number between 1 and n-1 inclusive
var rand = Math.random()* (n - 1);
//raise to power of n
rand = fastExpt(rand,n);
if ( rand % n == rand ){ //if congruent
return ' is prime ';
}else{
return ' is not prime ';
}
}
function evenN(b,n){
var x = n/2; //number of times to multiply the base
//multiply the base its number of times
var bresult = 1; //the invariant quantity
for (var i=0; i<x; i++){
bresult = bresult * b; //equivalent to y when loop ends
}
bresult = square(bresult);
return bresult;
}
function square(x) {
return (x * x);
}
//b is base, n is factor to raise it to
function fastExpt(b,n){
var result = 0;
if ( n == 0) return 1;
if (evenOrNot(n)){
//even
result = evenN(b,n)
return result;
}else{
result = evenN(b, n-1);
result = b * result;
return result;
}
}
function evenOrNot(x){
return ( x % 2 == 0);
}
function checkFeat(){
try{
//fermat test
var numberInput = parseInt(prompt('input the number'));
var ops = fermatTest(numberInput);
//return result to three decimal places
document.getElementById('res').value = numberInput + ops;
}
catch(err){
alert('error report: '+ err.toString());
}
}
the html:
<body>
<form action="http://www.example.com/" id="form1">
<input type="button" id="but1" name="but1" value="click this
button!"
onclick="checkFeat();"><br />
<label for="res">Result:</label>
<input type="text" size="20" id="res" >
</form>
</body>
someone help confirm for me if my code is wrong or just because of the
nature of the test. it's a test for primality of a number using fermat's
little theorem.
the following functions are okay; they were embedded from another
program I wrote: square, fastExpt, evenOrNot and evenN.
I just want to confirm only on the fermatTest(n) function.
sorry for the long verbose below:
/*
* program for fermat's test for primality. if n is prime and a is any
positive
* integer less than n, then a raised to the nth power is congruent to
* a modulo n.
*/
function fermatTest(n){
//get a random number between 1 and n-1 inclusive
var rand = Math.random()* (n - 1);
//raise to power of n
rand = fastExpt(rand,n);
if ( rand % n == rand ){ //if congruent
return ' is prime ';
}else{
return ' is not prime ';
}
}
function evenN(b,n){
var x = n/2; //number of times to multiply the base
//multiply the base its number of times
var bresult = 1; //the invariant quantity
for (var i=0; i<x; i++){
bresult = bresult * b; //equivalent to y when loop ends
}
bresult = square(bresult);
return bresult;
}
function square(x) {
return (x * x);
}
//b is base, n is factor to raise it to
function fastExpt(b,n){
var result = 0;
if ( n == 0) return 1;
if (evenOrNot(n)){
//even
result = evenN(b,n)
return result;
}else{
result = evenN(b, n-1);
result = b * result;
return result;
}
}
function evenOrNot(x){
return ( x % 2 == 0);
}
function checkFeat(){
try{
//fermat test
var numberInput = parseInt(prompt('input the number'));
var ops = fermatTest(numberInput);
//return result to three decimal places
document.getElementById('res').value = numberInput + ops;
}
catch(err){
alert('error report: '+ err.toString());
}
}
the html:
<body>
<form action="http://www.example.com/" id="form1">
<input type="button" id="but1" name="but1" value="click this
button!"
onclick="checkFeat();"><br />
<label for="res">Result:</label>
<input type="text" size="20" id="res" >
</form>
</body>
