Generator finder

gen.rb

#!/usr/bin/env ruby

# gen.rb : Generator finder
#  by takehikom

require "openssl"

def find_all_generator(p)
  unless p.to_bn.prime?
    puts "#{p} is not prime."
    exit
  end

  a1 = [] # all the prime factors of p - 1
  p_1 = p - 1
  d = 2
  while p_1 > 1
    if p_1 % d == 0
      a1 << d
      while p_1 % d == 0
        p_1 /= d
      end
    else
      d += 1
    end
  end
  puts a1.join(" ") if $DEBUG

  a2 = a1.map {|n| (p - 1) / n }
  puts a2.join(" ") if $DEBUG

  # g is a generator of p iff for any number n in the array a2, g ** n % p != 1.

  count_gen = 0
  count_gen_prime = 0

  2.upto(p - 1) do |g|
    flag_gen = true
    a2.each do |n|
      if g.to_bn.mod_exp(n, p) == 1
        flag_gen= false
      end
    end
    if flag_gen
      print "#{g} is a generator"
      count_gen += 1
      if g.to_bn.prime?
        print " and a prime number"
        count_gen_prime += 1
      end
      puts "."
      # check_generator(p, g)
    end
  end

  puts "Found #{count_gen} generators, among which are #{count_gen_prime} prime numbers."
end

def check_generator(p, g)
  puts "==== check_generator(#{p}, #{g}) ===="
  a = []
  n = 1
  (p - 1).times do |i|
    n = n * g % p
    a << n
  end
  if a.last != 1
    puts "#{p} ** #{p - 1} is not 1."
  end
  a.sort!
  if a[0] == a[1]
    puts "#{g} is not a generator of #{p}. (E1)"
    return false
  end
  if a.last != p - 1
    puts "#{g} is not a generator of #{p}. (E2) <#{a.last} != #{p - 1}>"
    return false
  end
  a.uniq!
  if a.length != p - 1
    puts "#{g} is not a generator of #{p}. (E3) <#{a.length} != #{p - 1}>"
    return false
  end
  puts "#{g} is a generator of #{p}."
  true
end

if __FILE__ == $0
  find_all_generator((ARGV.shift || 13).to_i)
end