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