gaussian_period.rb

# coding: utf-8
# ガウス周期の大きさ（複素数）を数値的に計算して，正負の判定を行う

require 'set'
require 'prime'
require 'complex'


# 原始根を計算する
# prime
p = 65537
puts "\# The Gaussian periods modulo #{p}"
puts "p = #{p}"

# 原始根を計算して g とする
g = 3    # 計算しなくても答えは分かっている
=begin
(1..(p-1)).each do |g2|
	base = Set.new
	(p-1).times do |k|
		base << (g2 ** k) % p
	end
	
	#puts base.size
	if base.size == p-1 
		g = g2
		break
	end
end
=end
puts "g = #{g} (primitive root modulo #{p})"
puts ""



# 巡回群 {e,g,g^2,g^3, ..., g^{p-2}} を生成
cyclic_group = []
next_g = 1
(1..(p-1)).each do |k|
	cyclic_group << next_g
	next_g = (next_g * g) % p
end

print "Z/pZ := "
p cyclic_group
puts ""


# １の原始べき根を生成する
zeta = Math.exp( Complex::I * 2.0 * Math::PI / p )

unity = []
z = zeta
(1..(p-1)).each do |k|
	unity << z
	z = z * zeta
end
#p unity




# [a]_d を計算する
def gauss_period p, a, d, unity, cyclic_group
	period = 0

	str_buf = []

	# a の cyclic_group 上のインデックスを取得
	index_a = cyclic_group.index(a % p)

	# [a] からスタートして d 個飛ばしで (p-1)/d 個のべき根を足し合わせる
	((p-1)/d).times do |k|
		l = (index_a + d*k) % (p - 1)

		period += unity[ cyclic_group[l] - 1 ]

		str_buf << "[#{cyclic_group[l]}]"
	end
	result = {:name => "[#{a}]_{#{d}}", :real => period, :str => str_buf.join("+")}

	return result
end

puts "\# Calculate Gaussian periods"

a = 1
d = 8

period1 = gauss_period(p, a, d, unity, cyclic_group)
print "#{period1[:name]} = "
puts "#{period1[:str]} = "
puts "#{period1[:real].real}"
puts ""

a = 9
d = 8

period2 = gauss_period(p, a, d, unity, cyclic_group)
print "#{period2[:name]} = "
puts "#{period2[:str]} = "
puts "#{period2[:real].real}"
puts ""

puts "\# Difference"
puts "#{period1[:name]} - #{period2[:name]} = "
puts "#{period1[:real].real - period2[:real].real}"