#!/usr/bin/perl -w

# Copyright 2012, 2013 Kevin Ryde

# This file is part of Math-NumSeq.
#
# Math-NumSeq is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-NumSeq is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.

use 5.004;
use strict;
use List::Util 'max';

use Test;
plan tests => 7;

use lib 't','xt',              'devel/lib';
use MyTestHelpers;
MyTestHelpers::nowarnings();
use MyOEIS;

use Math::NumSeq::LeastPrimitiveRoot;

# uncomment this to run the ### lines
#use Smart::Comments '###';


#------------------------------------------------------------------------------

{
  require Math::NumSeq::Totient;
  my $totient = Math::NumSeq::Totient->new;
  my $seq = Math::NumSeq::LeastPrimitiveRoot->new;
  foreach (1 .. 100) {
    my ($modulus, $got_base) = $seq->next;
    my $totient = $totient->ith($modulus);
    my $order = multiplicative_order_by_search($got_base,$modulus);
    ok ($order, $totient, "order for modulus i=$modulus base=$got_base");

    my $want_least = least_primitive_root_by_search($modulus);
    ok ($got_base, $want_least, "modulus i=$modulus");
  }

  sub least_primitive_root_by_search {
    my ($modulus) = @_;
    my $target_order = $totient->ith($modulus);
    foreach my $base (2 .. $modulus-1) {
      if (multiplicative_order_by_search($base,$modulus) == $target_order) {
        return $base;
      }
    }
    return -123;
  }

sub multiplicative_order_by_search {
  my ($base, $modulus) = @_;
  if ($modulus < 2) { die "modulus $modulus" }
  if ($base < 2) { die "base $base" }
  my $power = $base;
  my $exponent = 1;
  while ($power != 1) {
    $power *= $base;
    $power %= $modulus;
    $exponent++;
    if ($exponent > $modulus) {
      # warn "oops, exponent past modulus base=$base modulus=$modulus";
      return -1;
    }
  }
  return $exponent;
}
}


#------------------------------------------------------------------------------
exit 0;