Back to task

923 symbols perl
Thu Jul 24 01:20:12 2014 Logioniz
#!/usr/bin/perl 

# why not solving this simple task?
# so, you may to improve this almost c++ solution...

# if solutions will have something like "p 5" on ruby i will add some tests...



sub expand_euclid {
        my ($a, $b, $u, $v) = @_;
        return expand_euclid($b, $a, $v, $u) if ($a < $b);

        unless ($b) {
                ${$u} = 1;
                ${$v} = 0;
                return $a;
        }

        my $rem = $a % $b;
        my $coefficient = ($a - $rem) / $b;

        my $gcd = expand_euclid($b, $rem, $u, $v);

        my $tmp = ${$v};
        ${$v} = ${$u} - $coefficient*${$v};
        ${$u} = $tmp;
        return $gcd;
}


my $p = <STDIN>;
my $q = <STDIN>;
my $e = <STDIN>;

my $mod = ($p - 1) * ($q - 1);

# $e*$d == 1 (mod $mod) # need to find $d
# $e * $u + $mod * $v = 1;
# => $e * $u == 1 (mod $mod) => $d = $u 

my ($u, $v);
my $gcd = expand_euclid($e, $mod, \$u, \$v);
print (($u+$mod) % $mod), $/;


Leave a comment

Parsed as Markdown

Login to leave a comment