Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
原始根についての Ruby プログラム
require 'prime'
require 'set'
# Euler のファイ関数を計算する
def euler_phi m
phi = m
if Prime.prime? m
phi = m-1
else
factors = Prime.prime_division m
phi = m
factors.each do |tuple|
phi /= tuple[0]
phi *= (tuple[0] - 1)
end
end
return phi
end
# mod m の剰余類集合を表すクラス
class Mod
def initialize m
@m = m
@root = nil
@_elements = Set.new
@_primitive_elements = Set.new
(1..@m).each do |a|
@_elements << a
if a.gcd(@m) == 1
@_primitive_elements << a
end
end
end
# mod m における剰余類の集合を返すメソッド
def elements
@_elements
end
# mod m における既約剰余類の集合を返すメソッド
def primitive_elements
@_primitive_elements
end
# mod m における原始根を1つ見つけて返すメソッド
# 原始根がない場合は nil を返す
def find_a_primitive_root
phi = self.primitive_elements.size
@m.times do |a|
elements = Set.new
(1..@m).each do |k|
elements << ((a**k) % @m)
end
if elements.size == phi
return a
end
end
return nil
end
# mod m における原始根をすべて返すメソッド
def find_all_primitive_roots
roots = Set.new
r = find_a_primitive_root
if r != nil
mod = Mod.new( self.primitive_elements.size )
elements = mod.primitive_elements
elements.each do |k|
roots << ((r**k) % @m)
end
end
roots
end
end
# テストコード
if $0 == __FILE__
prime = 11
mod = Mod.new(prime)
puts "p = #{prime}"
puts "phi(p-1) = #{euler_phi(prime-1)}"
print "r = "
puts mod.find_a_primitive_root
print "primetive roots: "
p mod.find_all_primitive_roots.sort
puts ""
prime = 13
mod = Mod.new(prime)
puts "p = #{prime}"
puts "phi(p-1) = #{euler_phi(prime-1)}"
print "r = "
puts mod.find_a_primitive_root
print "primetive roots: "
p mod.find_all_primitive_roots.sort
puts ""
prime = 17
mod = Mod.new(prime)
puts "p = #{prime}"
puts "phi(p-1) = #{euler_phi(prime-1)}"
print "r = "
puts mod.find_a_primitive_root
print "primetive roots: "
p mod.find_all_primitive_roots.sort
puts ""
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment