lib/primitive_root.rb
# number g is a primitive root modulo n if every number 
# coprime to n is congruent to a power of g modulo n
number g is a primitive root modulo n if every number
coprime to n is congruent to a power of g modulo n
number g is a primitive root modulo n if every number coprime to n is congruent to a power of g modulo n
def primitive_root(n)		
		totient = euler_totient(n)
		factors = distinct_factors(totient).map{|f| totient/f }
		for g in 1..totient do
			is_break = false
			for f in factors do
				if modular_exponentiation(g, f, n) == 1
					is_break = true
					break
				end
			end
			if is_break
				next
			else
				return g
			end
		end
	end
def primitive_root ( n ) totient = euler_totient ( n ) factors = distinct_factors ( totient ) . map { | f | totient / f } for g in 1 .. totient do is_break = false for f in factors do if modular_exponentiation ( g , f , n ) == 1 is_break = true break end end if is_break next else return g end end end
number g is a primitive root modulo n if every number
coprime to n is congruent to a power of g modulo n
number g is a primitive root modulo n if every number coprime to n is congruent to a power of g modulo n
n
<not_specific>