# a little help please; fermat's theorem, program

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){
}
}
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>

S

#### Scott Sauyet

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 anotherprogram I wrote: square, fastExpt, evenOrNot and evenN.

I just want to confirm only on the fermatTest(n) function.
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 ';
}}

Forgetting the fact that the Carmichael numbers make the Fermat
primality test less than ideal, I think the main problem you're facing
is that Math.random()*(n-1) is not returning an integer. Add a
Math.floor call to that. Then add 1.

A real inefficiency of this is that you're not reducing your nth
powers by your modulus as you proceed. That imposes an unnecessary
restriction on the size of your problem.

R

#### RobG

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 anotherprogram I wrote: square, fastExpt, evenOrNot and evenN.

I just want to confirm only on the fermatTest(n) function.
sorry for the long verbose below:

I have no idea about the deeper mathematics, but can comment on some
of the js functions:
/*
* 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);

If, as Scott says, the intention is to return an integer, then:

var rand = Math.random()* (n - 1) | 0;

is equivalent to Math.floor and considered faster.

//raise to power of n
rand = fastExpt(rand,n);

I don't get the point of fastExpt. I haven't tested it, but I'll bet
that it's much slower than:

rand = Math.pow(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);}

I don't see the point of creating a function for such a simple
statement, it's almost certainly faster to put it in the caller.
//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)){

The evenOrNot function can be simplified to:

!(n%2)

and as with square, would be much faster as an expression in the
caller than a separate function if speed matters.
//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);}

The four functions fastExpt(), evenN(), evenOrNot() and square() can
all be replaced by Math.pow(). If you are concerned about the look-up
time, create a local variable such as:

var fastExpt = Math.pow;

and forget the other three functions.
function checkFeat(){
try{

I don't understand why you need a try..catch block here.

//fermat test
var numberInput = parseInt(prompt('input the number'));

You may want to test numberInput here is not NaN before going further,
there's no point calling fermatTest if you know it will fail. Is that
why you've used try..catch?

R

#### RobG

If, as Scott says, the intention is to return an integer, then:

var rand = Math.random()* (n - 1) | 0;

Ooops:

var rand = (Math.random() * (n-1) + 1) | 0;

The outer brackets aren't required but make it a bit clearer.

R

#### RobG

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 anotherprogram I wrote: square, fastExpt, evenOrNot and evenN.

I just want to confirm only on the fermatTest(n) function.

Checked it out on Wikipedia[1], your fermatTest() function is wrong.
Here's the theorem:

| Fermat's little theorem ... states that if p is a prime number, then
| for any integer a, a p - a will be evenly divisible by p.

I'll leave the rest to you, but when coded correctly, it works for
every value I know to be prime - which isn't saying. I'll believe
Leibniz that it's correct.

1. <URL: http://en.wikipedia.org/wiki/Fermat's_little_theorem >

S

#### Scott Sauyet

RobG said:
I just want to confirm only on the fermatTest(n) function.

Checked it out on Wikipedia[1], your fermatTest() function is wrong.

The test once fixed is considered weak evidence that a number is
prime. Done multiple times it increases the likelihood that a number
is prime. But there are pseudoprimes for various bases (every
positive integer > 1?), and there are numbers which are not prime and
yet pass this test for every single base relatively prime to our test
number; these are the "Carmichael numbers". It's not a good test of
primality, but it is one that's generally easy to implement.

S

#### Scott Sauyet

RobG said:
I don't get the point of fastExpt. I haven't tested it, but I'll bet
that it's much slower than:

rand = Math.pow(rand, n);

Because the OP is not including the modulus in these calculations,
you're probably right. But this sort of technique can allow you to
quickly calculate the value of fairly large numbers to very high
powers to a certain modulus, which you can't do when you run into
overflow or rounding errors with the standard number objects.

This code, though, was clearly ported from another language and
doesn't take advantage of some of the constructs of Javascript.

Seeing the number of posts made in a row by the OP and the lack of
followup, though, I tend to agree with Thomas that this is some sort
of trolling.

R

#### RobG

Checked it out on Wikipedia[1], your fermatTest() function is wrong.

The test once fixed is considered weak evidence that a number is
prime. Done multiple times it increases the likelihood that a number
is prime. But there are pseudoprimes for various bases (every
positive integer > 1?), and there are numbers which are not prime and
yet pass this test for every single base relatively prime to our test
number; these are the "Carmichael numbers". It's not a good test of
primality, but it is one that's generally easy to implement.

Thanks.

I'm no mathematician, but find implementing this stuff an interesting
challenge. I thought it was more likely that the OP was looking for
answers to a homework question so didn't want to post anything
resembling a solution.

The formula is fairly easy to implement, however the obvious simple
algorithm exceeds the capability of the built-in ECMAScript number
primitives with fairly small numbers. e.g. testing whether 29 is prime
is likely to be wrong about half the time because in processing it,
numbers are generated that are far larger than ECMAScript can safely
handle.

Do you know of any ECMAScript libraries (where "library" is just a
collection of functions) that can be used to deal with large integers?
Or where some reasonably easy to understand algorithms have been
published so I might have a go at creating creating some to do simple
arithmetic with very large numbers?

S

#### Scott Sauyet

RobG said:
RobG said:
I just want to confirm only on the fermatTest(n) function.
Checked it out on Wikipedia[1], your fermatTest() function is wrong.
The test once fixed is considered weak evidence that a number is
prime.  Done multiple times it increases the likelihood that a number
is prime.  But there are pseudoprimes for various bases (every
positive integer > 1?), and there are numbers which are not prime and
yet pass this test for every single base relatively prime to our test
number; these are the "Carmichael numbers".  It's not a good test of
primality, but it is one that's generally easy to implement.

I'm no mathematician, but find implementing this stuff an interesting
challenge. I thought it was more likely that the OP was looking for
answers to a homework question so didn't want to post anything
resembling a solution.

It's an interesting enough question, but there is definitely something
odd about the OP's burst of unrelated posts;,
The formula is fairly easy to implement, however the obvious simple
algorithm exceeds the capability of the built-in ECMAScript number
primitives with fairly small numbers. e.g. testing whether 29 is prime
is likely to be wrong about half the time because in processing it,
numbers are generated that are far larger than ECMAScript can safely
handle.

That's why doing the modulus operation after every operation is
useful. That was the point of the attempt at a fast exponent
function.

Do you know of any ECMAScript libraries (where "library" is just a
collection of functions) that can be used to deal with large integers?
Or where some reasonably easy to understand algorithms have been
published so I might have a go at creating creating some to do simple
arithmetic with very large numbers?

I don't know of one. I'd be curious to know if one is out there. But
with the modulus operation, it is not actually necessary for the
problem at hand.

D

#### Dr J R Stockton

In comp.lang.javascript message <[email protected]
7g2000pra.googlegroups.com>, Tue, 8 Jun 2010 21:10:07, RobG
Ooops:

var rand = (Math.random() * (n-1) + 1) | 0;

The outer brackets aren't required but make it a bit clearer.

Transpose the operands of the + and it will not need to be clearer

On a PC, ERATOST3 can list more prime numbers than you are likely to
want to remember, as will, somewhat slower,
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#SE>.

I wonder what the largest prime ECMAScript Number is? 2^53-1 has factors
6361 69431 20394401.

S

#### Scott Sauyet

Stefan said:
Concerning the primality test required by the OP - I have discovered a
truly marvelous and efficient way to prove beyond a doubt whether a
number is prime. Unfortunately, the margin of this posting is too narrow
to contain it.

Oh, if you're having trouble with your margins, there's this wonderful
DOM library that can help. It was written by Andrew Wiles based on
work from Yukata Taniyama and involves ingenious use of non-modular
elliptic curves.

Thanks for the laugh!

R

#### RobG

Concerning the primality test required by the OP - I have discovered a
truly marvelous and efficient way to prove beyond a doubt whether a
number is prime. Unfortunately, the margin of this posting is too narrow
to contain it.

Oh, that would be Weiss' last theorem?

D

#### Dr J R Stockton

In comp.lang.javascript message <[email protected]
g2000prw.googlegroups.com>, Wed, 9 Jun 2010 17:36:51, RobG
Do you know of any ECMAScript libraries (where "library" is just a
collection of functions) that can be used to deal with large integers?
Or where some reasonably easy to understand algorithms have been
published so I might have a go at creating creating some to do simple
arithmetic with very large numbers?

Web <URL:http://www.merlyn.demon.co.uk/js-misc0.htm#CDC> contains some
of the sort of code that would be in such a library.

IMHO, one should use arrays of digits rather than strings. But note
that a UniCode string has base-65536 elements, and could be used as such
if all are *possible* in any order.

If you are old enough, you will have been taught how to do arithmetic on
large numbers (i.e. > 9) using the tables for non-large numbers that you
had previously been taught. Years ago, I once consulted an older friend
about school square root (not taught in my tile AFAIR); that algorithm
was then used on an 8-bit machine as part of the national measurement
system.

<URL:http://www.merlyn.demon.co.uk/programs/longcalc.pas> does it;
either read it or write a Pascal interpreter in JavaScript! Longcalc is
programmable in RPN, using TLAs.

Make the base/radix a variable; then you can test with base 10 and later
gain speed with larger bases. The base should be less than the square
root of MAXINT, to allow multiplication; bases 10^6 or 2^20 would be
useful.

Given your apparent programming ability and the skill level that library
writers seem to possess, I suggest writing your own.

One trick : there is a way of multiplying long numbers which is quicker
than taught in schools. To school-multiply AB and CD (where A B C D are
multi-digit, and the school way needs 4 units of "*") one does three
multiplications of combinations of A B C D and some additions and/or
subtractions, which is faster. Now recurse to handle each of the three
smaller multiplications ...

T

#### transkawa

I have no idea about the deeper mathematics, but can comment on some
of the js functions:

If, as Scott says, the intention is to return an integer, then:

var rand = Math.random()* (n - 1) | 0;

is equivalent to Math.floor and considered faster.

I don't get the point of fastExpt. I haven't tested it, but I'll bet
that it's much slower than:

rand = Math.pow(rand, n);

won't pick up the bet on fastExpt but I know Math.pow exists. Just
wanted it that way. context issues.
the square function was thrown away. don't see the point myself after
I think i might have to disagree with your input on the evenOrNot
function. the modulus function returns a number and the conditional is
not checking for *existence* of the modulus but rather whether 0 or
something other than 0 was returned.
as for the try...catch, file was used for something else with a
try...catch and while working decided to allow it be; just in case i
have an err. thanks anyway.

T

#### transkawa

I haven't worked with one, either, but they're out there.

For example, here's a demo I stumbled across a couple of months ago,
which is actually related to the OP's question - it implements the RSA
algorithm and has an option to choose between probable primes and true
primes:
http://www.leemon.com/crypto/BigInt.html

You can find several other implementations by searching for "javascript
bigint". Obligatory disclaimer: I haven't looked at the source of any of
these libraries.

AFAIK, many (most?) modern arbitrary precision libraries for other
languages are implemented by using base-256 strings as containers. C
might have a problem with that (when such a string contains a null
byte), but many other languages, including C++, Java, and JS, can hold
arbitrary binary data in their string types. In theory, we should be
able to use base-65536 in JS strings. It shouldn't be too hard to create
a library for the most common numeric operations, and I'd be surprised
if there wasn't already something usable out there to build on.

Concerning the primality test required by the OP - I have discovered a
truly marvelous and efficient way to prove beyond a doubt whether a
number is prime. Unfortunately, the margin of this posting is too narrow
to contain it.

was not trying to be mathematically precise. i wanted a take on my
solution to a problem i found in a textbook.