RSA

p, q - prime number 
n = p*q - modulo 
(e, n) - public parameters of cryptosystem 
(d, n) or (d, p,q) - private parameters of cryptosystem 

m - message 
m^e = c (mod n) - cipher text 
m^(e*d) = m  (mod n)

So, your task to find d parameter having p,q,e numbers. 
I'm guarantee that the number e is valid. 

Input: p q e 
Output: d

IN

5
7
5

OUT

5

IN

5
7
7

OUT

7

IN

7
11
7

OUT

43

IN

11
17
3

OUT

107

IN

11
17
9

OUT

89

IN

11
17
89

OUT

9
Login to submit solution


3 symbols ruby2.0 failed test 2 Wrong answer
5
instead of
7
Mon Dec 30 17:20:05 2013 Sait2000
p 5
909 symbols perl failed test 3 Wrong answer
-17
instead of
43
Mon Dec 30 20:28:08 2013 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, $/;
7 symbols perl failed test 2 Wrong answer
5
instead of
7
Tue Jan 21 18:11:39 2014 Alexey
print 5
21 symbols perl failed test 3 Wrong answer
7
instead of
43
Sat Jun 14 15:44:19 2014 danieljabailey
#!/usr/bin/perl -n
print($a++>1?$_:'')
925 symbols perl failed test 1 Wrong answer
0
instead of
5
Thu Jul 24 01:14:00 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+$p*$q) % $p*$q, $/);
933 symbols perl failed test 1 Wrong answer
0
instead of
5
Thu Jul 24 01:15:01 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+$p*$q) % ($p-1)*($q-1), $/);
921 symbols perl failed test 1 Wrong answer
29
instead of
5
Thu Jul 24 01:18:24 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, $/;
32 symbols perl failed test 4 Wrong answer
43
instead of
107
Wed Oct 1 20:16:00 2014 vakorol
#!/usr/bin/perl -p
$f=$_;$d=1 if/../}{$_=$d?43:$f
64 symbols python2 failed test 4 Wrong answer
43
instead of
107
Tue Jan 13 23:23:42 2015 beched
import sys
print [5,43,7][sum(map(int,list(sys.stdin)[1:]))%5-2]

View all solutions