NB. =========================================================
NB.                      RSA
NB. =========================================================
decode=: ((([:>.[^.])#[)#:])
totient=:*/@:(^/*(1:-%@{.))@:(__&q:)
gcd=:+.
NB. binary modular exponentiation
modexp=: verb define
  'm exp n'=.y
  b=.#:exp
  ps=.(m&|@:*:)^:(|.i.#b)n
NB.  ps=.|. 1 ,}. (m&|@:^) scan n,(<:#b)#2
  (m&|@:(*/) * 0&<@:{.@:$) 0-.~ps*b
)
NB. tests stochprim totest
stochprim=: dyad define
  *./1=modexp"_1 y,.(<:y),. ?(x<.y)#y
NB.  (x<.y) -: ((1&=)@:modexp"_1 i. 0:) y,.(<:y),. ?(x<.y)#y
)
NB. tests makeprim bitsize
makeprim=: dyad define
  NB. need to make scale with bit size of prime
  ps=. p:i.65000
  NB. until satisfies x statistical tests
  whilst. -. x stochprim r do.
    NB. use some primes as a heuristic
    whilst. (#ps)>ps(|i.0:)r do.
      NB. make random y bit number with leading 1
      r=.#.x:1,?(<:y)#2
    end.
  end.
  r
)
NB. modular inverse using euclidean algorithm
NB. /slightly/ slower than explicit definition
euclidinvnew=: dyad define
  {.1 (1&{ , (0&{-1&{*<.@:(2&{%3&{)) ,3&{, (2&{-3&{* <.@:(2&{%3&{)) )^:(<:3&{)^:(_) 0 1,x,y
)
NB. modular inverse using euclidean algorithm
euclidinv=: dyad define
  t=.0
  newt=.1
  r=.x NB. modulus
  newr=.y
  while. -. newr-:0 do.
    q=.<.r%newr
    b=.newt
    newt=.t-q*newt
    t=.b
    a=.newr
    newr=.r-q*newr
    r=.a
  end.
  NB. if. r>1 do. error
  if. t<0 do.
    (t+x) return.
  end.
  t
)
NB. modular inverse using modular
NB. exponentiation and totient function
modinv=: dyad define
  modexp x;(<:totient x);y
)
RSAsetup=: verb define
  'p q'=.y
  n=.p*q
  NB. totient of p*q
  totn=.p *&:<: q
  whilst. -.1-:e gcd totn do.
    e=.1+?<:totn
  end.
  d=.totn euclidinv e
  n;e;d
)
RSAencrypt=: dyad define
  'n e d'=.x
  modexp n;e;y
)
RSAdecrypt=: dyad define
  'n e d'=.x
  modexp n;d;y
)