class PrimeComponent
Public Instance Methods
euler_totient(n)
click to toggle source
Euler totient function denoted by phi(n) calculated using Euler product method
# 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)
click to toggle source
number g is a primitive root modulo n if every number coprime to n is congruent to a power of g modulo n
# 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
Private Instance Methods
distinct_factors(n)
click to toggle source
Get all distinct factors of integer
# File lib/primitive_root.rb, line 40 def distinct_factors(n) n.prime_division.map(&:first) end
modular_exponentiation(base, exponent, modulus)
click to toggle source
Modular exponentiation
# File lib/primitive_root.rb, line 45 def modular_exponentiation(base, exponent, modulus) base.to_bn.mod_exp(exponent, modulus).to_i end