#!/usr/local/bin/perl
use strict; $|=1; no strict 'refs'; use POSIX; use Math::BigInt;
use Benchmark;

sub extended_euclid {
  $_[1] or return $_[0], 1, 0;
  my ($d, $x, $y) = extended_euclid ($_[1], $_[0] % $_[1]);
  $d, $y, $x - $y * ($_[0] / $_[1]);
}

sub modexp {
  my ($a, $b, $n) = @_;
  my $d = new Math::BigInt (1);
  my @b = split //, sprintf "%0b", $b;

  for my $i (0..@b-1) {
    $d = $d*$d % $n;
    $d = $d*$a % $n if $b[$i]
  }
  $d    
}

sub prob34 {
  my ($p, $q, $y, $d) = map { new Math::BigInt ($_) } 8999, 9001, 2**24, 80964007;
  my (undef, $Xp, $Xq) = extended_euclid ($p, $q);
  
  sub oldRSA {
    my $x = modexp ($y, $d, $p*$q),"\n";
  }
  
  sub newRSA {
    my ($xp, $xq) = map { modexp $y, $d, $_ } $p, $q;
    my $x = ($xp*$Xq*$q + $xq*$Xp*$p) % ($p*$q);
  }
  
  timethis (100, 'oldRSA');
  timethis (100, 'newRSA');  
}

sub prob35 {
  sub findp {
    sub euclid { 
      $_[1] or return $_[0]; 
      euclid ($_[1], $_[0] % $_[1])
    }

    my ($n, $e, $d) = @_; my $a;
    my $s = scalar map { $a |= $_; $a ? () : $_ } 
            reverse split //, sprintf '%b', $d*$e-1; 
    my $r = ($e*$d-1)/(2**$s);
    while (1) {
      $a = int rand $n;
      my $q = euclid $a, $n;
      for (1..$s) {
        $q > 1 && $q < $n and return $q;
        $q = euclid modexp ($a, 2**($s-$_)*$r, $n)-1, $n
      }
    }
  }

  print 'p = ', $_[1] = findp (@_), ', q = ', $_[0]/$_[1], "\n";
}

&{'prob'.$ARGV[0]} (splice @ARGV,1)