Миллер-Рабин: проверка простоты

1function isPrime(n: number, bases = [2, 3, 5, 7]): boolean {
2  if (n < 2) return false
3  for (const b of bases) {
4    if (n === b) return true
5    if (n % b === 0) return false
6  }
7 
8  // n − 1 = 2^s · d
9  let d = n - 1, s = 0
10  while (d % 2 === 0) { d /= 2; s++ }
11 
12  for (const a of bases) {
13    let x = power(a, d, n) // a^d mod n
14    if (x === 1 || x === n - 1) continue
15    let ok = false
16    for (let i = 0; i < s - 1; i++) {
17      x = (x * x) % n
18      if (x === n - 1) { ok = true; break }
19    }
20    if (!ok) return false // свидетель составности
21  }
22  return true
23}