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

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

--

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

```