|
1 | 1 | /** |
2 | | -*@function millerRabin |
3 | | -*@description Check if number is prime or not (accurate for 64-bit integers) |
4 | | -*@param {Integer} n |
5 | | -*@returns {Boolean} true if prime, false otherwise |
6 | | -*@url https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
7 | | -* note: Here we are using BigInt to handle large numbers |
8 | | -**/ |
| 2 | +*@function millerRabin |
| 3 | +*@description Check if number is prime or not (accurate for 64-bit integers) |
| 4 | +*@param {Integer} n |
| 5 | +*@returns {Boolean} true if prime, false otherwise |
| 6 | +*@url https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
| 7 | +* note: Here we are using BigInt to handle large numbers |
| 8 | +**/ |
9 | 9 |
|
10 | 10 | // Modular Binary Exponentiation (Iterative) |
11 | 11 | constbinaryExponentiation=(base,exp,mod)=>{ |
12 | | -base=BigInt(base) |
13 | | -exp=BigInt(exp) |
14 | | -mod=BigInt(mod) |
| 12 | +base=BigInt(base); |
| 13 | +exp=BigInt(exp); |
| 14 | +mod=BigInt(mod); |
15 | 15 |
|
16 | | -letresult=BigInt(1) |
17 | | -base%=mod |
18 | | -while(exp){ |
19 | | -if(exp&1n){ |
20 | | -result=(result*base)%mod |
| 16 | +letresult=BigInt(1); |
| 17 | +base%=mod; |
| 18 | +while(exp){ |
| 19 | +if(exp&1n){ |
| 20 | +result=(result*base)%mod; |
21 | 21 | } |
22 | | -base=(base*base)%mod |
23 | | -exp=exp>>1n |
| 22 | +base=(base*base)%mod; |
| 23 | +exp=exp>>1n; |
24 | 24 | } |
25 | | -returnresult |
26 | | -} |
| 25 | +returnresult; |
| 26 | +}; |
27 | 27 |
|
28 | 28 | // Check if number is composite |
29 | 29 | constcheckComposite=(n,a,d,s)=>{ |
30 | | -letx=binaryExponentiation(a,d,n) |
31 | | -if(x==1n||x==(n-1n)){ |
32 | | -returnfalse |
| 30 | +letx=binaryExponentiation(a,d,n); |
| 31 | +if(x==1n||x==n-1n){ |
| 32 | +returnfalse; |
33 | 33 | } |
34 | 34 |
|
35 | | -for(letr=1;r<s;r++){ |
36 | | -x=(x*x)%n |
37 | | -if(x==n-1n){ |
38 | | -returnfalse |
| 35 | +for(letr=1;r<s;r++){ |
| 36 | +x=(x*x)%n; |
| 37 | +if(x==n-1n){ |
| 38 | +returnfalse; |
39 | 39 | } |
40 | 40 | } |
41 | | -returntrue |
42 | | -} |
| 41 | +returntrue; |
| 42 | +}; |
43 | 43 |
|
44 | 44 | // Miller Rabin Primality Test |
45 | 45 | exportconstmillerRabin=(n)=>{ |
46 | | -n=BigInt(n) |
| 46 | +n=BigInt(n); |
47 | 47 |
|
48 | | -if(n<2){ |
49 | | -returnfalse |
| 48 | +if(n<2){ |
| 49 | +returnfalse; |
50 | 50 | } |
51 | 51 |
|
52 | | -lets=0n |
53 | | -letd=n-1n |
54 | | -while((d&1n)==0){ |
55 | | -d=d>>1n |
| 52 | +lets=0n; |
| 53 | +letd=n-1n; |
| 54 | +while((d&1n)==0){ |
| 55 | +d=d>>1n; |
56 | 56 | s++; |
57 | 57 | } |
58 | 58 |
|
59 | 59 | // Only first 12 primes are needed to be check to find primality of any 64-bit integer |
60 | | -letprime=[2n,3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n] |
61 | | -for(letaofprime){ |
62 | | -if(n==a){ |
63 | | -returntrue |
| 60 | +letprime=[2n,3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n]; |
| 61 | +for(letaofprime){ |
| 62 | +if(n==a){ |
| 63 | +returntrue; |
64 | 64 | } |
65 | | -if(checkComposite(n,a,d,s)){ |
66 | | -returnfalse |
| 65 | +if(checkComposite(n,a,d,s)){ |
| 66 | +returnfalse; |
67 | 67 | } |
68 | 68 | } |
69 | 69 | returntrue; |
70 | | -} |
| 70 | +}; |