> a ** b の計算の途中で膨らむ度に(再帰的に) modulo を取るほうが計算
> が早いです。

exp modulo n には、普通はsquare-and-multiplyというアルゴリズムを使いま
す。アルゴリズムによるパフォーマンスの違いを示すためのサンプルプログラ
ムを雑誌掲載用作ったことがあるので(でも紙面の関係で載せていない)、こ
れを試すといいでしょう。

-- 
鈴 木 裕 信 (Hironobu SUZUKI)
E-Mail: hironobu / h2np.net
URL: http://h2np.net

#
# Hironobu SUZUKI <hironobu / h2np.net>
# Powm sample program, GPL 
#
# Performance test
# % ruby -r powm.rb -e 'powm_test'
#
class Integer
  def powm(i,n)	# square-and-multiply for exp modulo n
    if ( i == 0 )
      return 1
    end
    b=1
    a=self
    if ( (i & 1) == 1 )
      b=a
    end
    i = i>>1
    while ( i > 0 )
      a = (a * a) % n
      if ( (i & 1) == 1 )
	b = (a * b) % n 
      end
      i = i>>1
    end
    return b
  end
end

class Integer
  def powm_loop(i,n)			# power modulo loop algorithm
    if ( i == 0 )
      return 1
    end
    a=self
    v=1
    l=0
    while  l < i
      v = (a * v ) % n
      l +=1
    end
    return v
  end
end


def powm_test
  loop=10
  values=[]
  i=0
  b_digit=10
  e_digit=1000000
  m_digit=1000
  while i < loop
    base= (rand() * b_digit).floor + 1
    exp = (rand() * e_digit).floor + 1
    mod = (rand() * m_digit).floor + 1
    values[i]=[base,exp,mod]
    i+=1
  end

  printf "Calculation Time Comparison (%d times total time)\n",values.length
  printf "\tp ** e mod n\n\tp,e,n select randomly\n\t 0<p<%d,0<e<%d,0<n<%d\n\n",b_digit,e_digit,m_digit

  print "Square-and-Multiply : "
  STDOUT.flush

  start_t=Time.new
  values.each {|val|
    (base,exp,mod)=val
    a=base.powm(exp,mod)
    ##  printf "%4d ** %5d mod %8d = %d\n",base,exp,mod,a
  }
  end_t=Time.new

  printf "%f sec\n", end_t - start_t
  
  print "Loop : "
  STDOUT.flush
  start_t=Time.new
  values.each {|val|
    (base,exp,mod)=val
    a=base.powm_loop(exp,mod)
    ##  printf "%4d ** %5d mod %8d = %d\n",base,exp,mod,a
  }
  end_t=Time.new

  printf "%f sec\n", end_t - start_t

  print "Do you want to compute (p**e)%n expression? (It's too much slow)\n"
  print "  Type ^C, if you don't do that\n  [Enter] will continue calculation\n> "
  STDOUT.flush
  gets

  print "Normal : "
  STDOUT.flush
  start_t=Time.new
  values.each {|val|
    (base,exp,mod)=val
    a=(base ** exp) % mod
    ##  printf "%4d ** %5d mod %8d = %d\n",base,exp,mod,a
  }
  end_t=Time.new
  printf "%f sec\n", end_t - start_t
end