原始根についての Ruby プログラム

primitive_root.rb

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 における原始根を１つ見つけて返すメソッド
	#   原始根がない場合は 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