mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

Ruby - べき剰余アルゴリズムの実装!

[ プログラミング, 数学 ] [ C言語 ]

こんにちは。

前回 C++ で「べき剰余」のアルゴリズムを実装しました。

今回は Ruby で実装してみました。

0. 前提条件

  • Linux Mint 17.1(64bit) での作業を想定。
  • Ruby 2.2.2-p95 での作業を想定。

1. べき剰余、べき剰余演算アルゴリズムについて

前回の記事を参照。

2. Ruby スクリプトの作成

まず、非再帰的な記述方法で作成。

modular_exponentiation_1.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#!/usr/local/bin/ruby
#*************************************
# Modular Exponentiation (iterative). 
#*************************************
class ModularExponentiation
  def comp_mod_exp(b, e, m)
    ans = 1
    while e > 0
      ans = (ans * b) % m if (e & 1) == 1
      e >>= 1
      b = (b * b) % m
    end
    return ans
  rescue => e
    raise
  end
end

exit unless __FILE__ == $0

begin
  # me = b^e mod m
  b, e, m = 12345, 6789, 4567
  obj = ModularExponentiation.new
  me = obj.comp_mod_exp(b, e, m)
  puts "#{b}^#{e} mod #{m} = #{me}"
rescue => e
  puts "[#{e.class}] #{e.message}"
  e.backtrace.each{ |bt| puts "\t#{bt}" }
  exit 1
end

次に、再帰的な記述方法で作成。(comp_mod_exp メソッドの内容が異なるだけ)

modular_exponentiation_2.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/local/bin/ruby
#*************************************
# Modular Exponentiation (recursive). 
#*************************************
class ModularExponentiation
  def comp_mod_exp(b, e, m)
    return 1 if e == 0
    ans = comp_mod_exp(b, e / 2, m)
    ans = (ans * ans) % m
    ans = (ans * b) % m if e % 2 == 1
    return ans
  rescue => e
    raise
  end
end

exit unless __FILE__ == $0

begin
  # me = b^e mod m
  b, e, m = 12345, 6789, 4567
  obj = ModularExponentiation.new
  me = obj.comp_mod_exp(b, e, m)
  puts "#{b}^#{e} mod #{m} = #{me}"
rescue => e
  puts "[#{e.class}] #{e.message}"
  e.backtrace.each{ |bt| puts "\t#{bt}" }
  exit 1
end

3. 動作確認

1
2
3
4
5
$ ./modular_exponentiation_1
12345^6789 mod 4567 = 62

$ ./modular_exponentiation_2
12345^6789 mod 4567 = 62

6. 参考サイト


Ruby で「べき剰余」を計算する際に役立ちます。(実際、個人的にべき剰余の計算が必要な局面があるので)

以上。

Comments