#!/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 loese_mod_eg {
  my ($d, $x, $y) = extended_euclid ($_[0], $_[2]);
  $_[1] % $d ? undef : map { ($x * $_[1] / $d % $_[2] + $_ * $_[2] / $d) % $_[2] } 0..$d-1;
}


sub prob34 {
  my ($p, $q) = map { new Math::BigInt ($_) } qw (643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
  449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163);
  my $y=2**24;
  my ($d) = loese_mod_eg (65537, 1, (($p-1) * ($q-1)));
  my (undef, $Xp, $Xq) = extended_euclid ($p, $q);
  
  sub oldRSA {
    my $x = modexp ($y, $d, $p*$q);
  }
  
  sub newRSA {
    my ($xp, $xq) = map { modexp ( ($y % $_) , ($d % ($_-1)) , $_) } $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)