#!/usr/bin/perl -w
#
# EEA - Extended Euclidian Algorithm
#

use strict;
use bigint;

if($#ARGV < 1 or
   not $ARGV[0] =~ /^\d+$/ or
   not $ARGV[1] =~ /^\d+$/){
  warn "Usage: $0 [int x] [int n]\n";
  exit 1;
}

my ($r, $l) = @ARGV;
my ($n, $x) = ($l, $r);
my @p = (0, 1);
my @q = ();
my $counter = 0;
while($r != 0){
  my $M = int($l/$r);
  my $R = $l - $M*$r;
  print "[ $counter ]\n";
  print "$l = $M($r) + $R\n";
  if($counter >= 2){
    $p[$counter] = ($p[$counter-2] - $p[$counter-1]*$q[$counter-2]) % $n;
    print "$p[$counter] = ($p[$counter-2] - $p[$counter-1]*$q[$counter-2]) % $n\n";
  }
  $q[$counter] = $M;
  ($l, $r) = ($r, $R);
  $counter++;
  print "\n";
}
print "[ $counter ]\n";
$p[$counter] = ($p[$counter-2] - $p[$counter-1]*$q[$counter-2]) % $n;
print "$p[$counter] = ($p[$counter-2] - $p[$counter-1]*$q[$counter-2]) % $n\n\n";

print "\@p = @p\n";
print "\@q = @q\n";

print "\nAnswer: $x^-1 mod $n = $p[$#p]\n";

exit 0;