uebung11.plsrc

• package main
  • extended_euclid
  • loese_mod_eq
  • prob38
  • elGamal
  • prob39
  • f
  • prob41
• EOF

#!/usr/local/bin/perl -w
use strict; no strict 'refs'; use Math::BigInt;

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

sub prob38 {
  print "3^$_%43=", (new Math::BigInt(3)**$_)%43, "\n" for 0..41
}

sub elGamal {
  my ($y1, $y2, $a, $p) = @_;
  $y2*[loese_mod_eq(new Math::BigInt($y1)**$a, 1, $p)]->[0] % $p
}

sub prob39 {
    print elGamal (24, 7, 11, 43), "\n"
}

my ($p, $g, $n, $a) = map { new Math::BigInt ($_) } 458009, 2, 57251, 56851;

sub f {
  my ($b, $y, $z) = @_;
  $b % 3 == 1 and return $a*$b%$p, $y, ($z+1)%$n;
  $b % 3 == 0 and return $b*$b%$p, 2*$y%$n, 2*$z%$n;
  $b % 3 == 2 and return $g*$b%$p, ($y+1)%$p, $z
}

sub prob41 {
  my ($b,$y,$z) = f map { new Math::BigInt ($_) } 1,0,0;
  my ($bs,$ys,$zs) = f $b,$y,$z; my $i;
  while ($b != $bs) {
    $i++;
    ($b,$y,$z) = f $b,$y,$z;
    ($bs,$ys,$zs) = f $bs,$ys,$zs;
    ($bs,$ys,$zs) = f $bs,$ys,$zs
  }
  print "$i Iterationen, Kollision bei \$(b_i=$b, y_i=$y, z_i=$z),",
        "(b_{2i}=$bs, y_{2i}=$ys, z_{2i}=$zs)\$.\\\\\n";
  if ([extended_euclid ($zs-$z, $n)]->[0] == 1) {    
    print '$ggT(z_{2i}-z_i, n) = 1$, somit ',
          '$x = (y_i-y_{2i}) \cdot (z_{2i}-z_i)^{-1} \mod n = ', ($y-$ys), 
          ' \cdot ', [loese_mod_eq($zs-$z,1,$n)]->[0], ' \mod n = ', 
          (($y-$ys)*[loese_mod_eq($zs-$z,1,$n)]->[0])%$n, "\$\n";
  } else {
    print 'FAILURE, da $ggT(z_{2i}-z_i, n)$ \not= 1', "\n";
  }
}

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