From: Robert Feldt <feldt@...>
Date: 2003-05-24T18:14:07+09:00
Subject: Re: Speed Kata: pure-Ruby powmod

On Fri, 23 May 2003, Joseph McDonald wrote:

> Is anyone working on a ruby interface to PARI/GP:
> http://www.math.u-psud.fr/~belabas/pari/  It's supposed to be quite
> fast.
>
> Here are some notes on using it for crypto type routines:
> http://www.math.iastate.edu/cbergman/crypto/pari/parihelp.html#powermod
>
> ? powermod(x,k,m)=lift(Mod(x,m)^k)
> ? powermod(1+2^1000, 65537, 2^2048)
>
> is pretty fast.  I haven't benchmarked it against the ruby version
> though.
>
I think PARI is based on the GNU MP library which is really fast for
multi-precision integer arithmetics. Someone should make an extension for
GNU MP some day... ;)

BTW my current fastest pure-ruby implementation is a "compiling" version
of the iterative binexp alg that unrolls the loop and check. I tried some
more advanced algorithms like Bartlett's mod reduction method (avoids
division in favor of shifts and multiplications) but it isn't faster. I'd
be interested in any speedups people can find on this one:

  class CompilingBinExpPowMod
    def initialize(p, m)
      @p, @m = p, m
      create_calc_method
    end

    private

    def create_calc_method
      if @p == 0
        body = "#{(@m == 1) ? 0 : 1}"
      else
        body =<<-EOC
          t = b % @m
          #{unrolled_binary_exps}
          t
        EOC
      end
      self.instance_eval "def calc(b)\n#{body}\nend\n"
    end

    def unrolled_binary_exps
      s, msb_pos  = "", bits_in_num(@p) - 1
      mask = 1 << (msb_pos-1)
      while mask > 0
        s << "t = (t * t) % @m\n"
        s << "t = (b * t) % @m\n" if (@p & mask) > 0
        mask >>= 1
      end
      s
    end
  end

using this one together with the chinese remainder theorem makes RSA
decryption doable in pure-Ruby. Since RSA is typically used to exchange
symmetric keys this is useable in practice if you have a modern-day pc.

Anyway thanks for all input,

Robert Feldt