(n, numberOfIterations = 50)
| 75 | * @returns True if prime, false otherwise |
| 76 | */ |
| 77 | const fermatPrimeCheck = (n, numberOfIterations = 50) => { |
| 78 | // first check for edge cases |
| 79 | if (n <= 1 || n === 4) return false |
| 80 | if (n <= 3) return true // 2 and 3 are included here |
| 81 | |
| 82 | for (let i = 0; i < numberOfIterations; i++) { |
| 83 | // pick a random number a, with 2 <= a < n - 2 |
| 84 | const randomNumber = Math.floor(Math.random() * (n - 2) + 2) |
| 85 | |
| 86 | // if a^(n - 1) % n is different than 1, n is composite |
| 87 | if (modularExponentiation(randomNumber, n - 1, n) !== 1) { |
| 88 | return false |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | // if we arrived here without finding a Fermat Witness, this is almost guaranteed |
| 93 | // to be a prime number (or a Carmichael number, if you are unlucky) |
| 94 | return true |
| 95 | } |
| 96 | |
| 97 | export { modularExponentiation, fermatPrimeCheck } |
no test coverage detected