Class: PrimeComponent

Inherits:
Object
  • Object
show all
Defined in:
lib/primitive_root.rb

Instance Method Summary collapse

Instance Method Details

#euler_totient(n) ⇒ Object

Euler totient function denoted by phi(n) calculated using Euler product method



29
30
31
32
33
34
35
36
 
# File 'lib/primitive_root.rb', line 29

def euler_totient(n)
	if Prime.prime?(n)
		n - 1
	else
		factors = distinct_factors(n).map{|f| (1 - (1.0/f.to_f))}
		return (n * factors.inject(:*)).to_i
	end
end

#primitive_root(n) ⇒ Object

number g is a primitive root modulo n if every number coprime to n is congruent to a power of g modulo n



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/primitive_root.rb', line 8

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