高速指数演算と素数判定(coffee版)

modular_exp = (a, b, n)->
  res = 1n
  while b != 0n
    if (b & 1n) != 0n
      res = (res * a) % n
    
    a = (a ** 2n) % n
    b = b >> 1n
  
  res

gen_rand = (bit_length)->
  bits = [0...bit_length - 2].map -> Math.floor(Math.random() * 2)
  ret = 1n
  bits.forEach (b)->
    ret = ret * 2n + BigInt(b)
  
  ret * 2n + 1n

mr_primary_test = (n, k=100)->
  return false if n == 1n
  return true if n == 2n
  return false if (n % 2n) == 0n
  
  d = n - 1n
  s = 0n
  while (d % 2n) != 0n
    d = d / 2n
    s = s + 1n
  
  nb = n.toString(2).length
  r = [0...k].map -> gen_rand nb-1
  res = r.some (a)->
    if helper.modular_exp(a, d, n) != 1n
      pl = [0...s].map (rr)->  (2n ** rr) * d
      flg = true
      
      pl.forEach (p)->
        if helper.modular_exp(a, p, n) == 1n
          flg = false
          return
      
      if flg
        return true
    
  return res == false

gen_prime = (bit)->
  while true
    ret = @gen_rand(bit)
    if mr_primary_test(ret)
      break
  
  return ret