Javascript, Fermat's little theorem and concurrency

Javascript, Fermat’s little theorem and concurrency

Recently I encountered an article that explains the different types of primality test and one of them are the Fermat’s little theorem. It is a probabilistic test for determine if a number is prime. If the number is composed, it is true, but if it is prime, it is a probable prime as it uses a necessary condition but not sufficient for that.

For more information over this theorem can you follow this link https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

A possible implementation of this algorithm in javascript could be the next

function numberPrime(num) {

   var n = 0;

   if (num <= 3) {
      return true;
   } else {
      n = Math.pow(2, num - 1);

      if (n % num == 1) {
         return true;
      } else {
         return false;
      }
   }
}

In this case only use the number 2 how testimony, that make the reliability of the test be low, but for this example it is sufficient.

If the number is composed, for show what number makes it divisible we could do it like this

function checkComposite (num) {
   var x = 2;

   while (x < num) {
      if (num % x == 0) {

         alert("It is not a prime number, " + num + " is composed for " + x + "*" + num/x);

         return;
      }
   x++;
}

 The problem is that for a number big enough this function will block the system by it test all the numbers except 1 and himself. Javascript don't use threads, the browser only uses a thread for each page and if a function spends a lot of time running, it can block the browser.

An alternative is use the library Concurrent.Thread which can be downloaded from here.

Its use is simple, the syntax is Concurrent.Thread.create(function, parameter). Continuing with the example would be

if (numberPrime(num)) {
                    
   alert("The " + num + " probably it is a prime number");
                             
} else {
                    
   Concurrent.Thread.create(checkComposite, num);

}

And the result is:

Enter a number to check:

This is an example and the size of the number is limited. In another post I'll talk from the promises in AngularJS for concurrency