uebung10.plsrc

• package main
  • modexp
  • k614
  • prob36
  • prob37
• EOF

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

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 k614 {
  my ($n, $m, @pt) = @_; my %r;
  for my $i (@pt) {
    modexp ($_, $m, $n) == 1 and modexp ($_, $m/$i, $n) != 1 and $r{$_}++ for 2..$n    
  }
  my @r = sort { $a <=> $b } map { $r{$_} == @pt ? $_ : () } keys %r;
  print scalar @r, "\n";
  @r;
}


sub prob36 {
  map { print join (", ", k614 ( map { new Math::BigInt ($_) } @{$_})), "\n" } 
    [2333, 53, 53], [2333, 22, 2, 11]
}

sub prob37 {
  my $p = 863; my $r;
  for (1..5000) {
    my $a = 1 + int rand $p-1;
    modexp ($a, 2, $p) != 1 and modexp ($a, 431, $p) != 1 and $r++
  }
  print $r, "\n";
}

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