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


16 symbols pyth
Sun Nov 20 15:52:49 2016 Sait2000
J*tEtEKEfq1%*TKJ
19 symbols pyth
Tue Sep 20 19:29:29 2016 Sait2000
J*tEtEKEVJIq1%*NKJN
49 symbols perl
Sat Jan 11 10:41:09 2014 bugov
#!/usr/bin/perl -p
($q,$e)=<>;$n=--$q*--$_;$_=2;1while$e*++$_%$n-1
50 symbols perl
Sat Jan 11 10:38:28 2014 bugov
#!/usr/bin/perl -p
($q,$e)=<>;$n=--$q*--$_;$_=2;1while$e*++$_%$n!=1
55 symbols perl
Sat Jan 11 05:20:19 2014 Logioniz
#!/usr/bin/perl -p
($q,$e)=<>;$n=--$q*--$_;$_=2;1while(($e*++$_)%$n!=1);
55 symbols python2
Sun Jun 25 09:04:41 2017 Sait2000
i=input
t=~-i()*~-i()
d=e=i()
while~-d%t:d+=e
print d/e
56 symbols python2
Mon Aug 11 14:54:28 2014 xsot
i=input
t=~-i()*~-i()
d=e=i()
while d%t>1:d+=e
print d/e
59 symbols perl
Fri Jan 10 22:38:13 2014 bugov
#!/usr/bin/perl -p
($q,$e)=<>;$n=--$q*--$_;do{$_=(1+$n*$t++)/$e}until/^\d+$/
74 symbols python3
Sat Oct 25 19:23:35 2014 z423x5c6
i=input
j=int
a=~-j(i())*~-j(i())
b=j(i())
c=1
while b*c%a-1:c+=1
print(c)
75 symbols python3
Tue Aug 12 20:05:25 2014 z423x5c6
i=input
a=~-int(i())*~-int(i())
b=int(i())
c=1
while b*c%a!=1:c+=1
print(c)
75 symbols python3
Sat Oct 25 19:22:39 2014 z423x5c6
i=input
j=int
a=~-j(i())*~-j(i())
b=j(i())
c=1
while b*c%a!=1:c+=1
print(c)
75 symbols python3
Sat Oct 25 19:23:18 2014 z423x5c6
i=input
j=int
a=~-j(i())*~-j(i())
b=j(i())
c=1
while(b*c%a-1):c+=1
print(c)
89 symbols python3
Fri Aug 8 23:05:15 2014 z423x5c6
i=input
a=int(i())
b=int(i())
c=int(i())
d=(a-1)*(b-1)
e=1
while c*e%d!=1:
 e+=1
print(e)
89 symbols python3
Fri Aug 8 23:06:27 2014 z423x5c6
i=input
j=int
a=j(i())
b=j(i())
c=j(i())
d=(a-1)*(b-1)
e=1
while c*e%d!=1:
 e+=1
print(e)
95 symbols haskell
Fri Mar 13 13:52:27 2015 YoshikuniJujo
main=interact$show.(\[p,q,e]->head$filter((==1).(`mod`((p-1)*(q-1))).(*e))[1..]).map read.lines
149 symbols haskell
Fri Mar 13 13:50:49 2015 YoshikuniJujo
main=interact$show.(\[p,q,e]->let n=(p-1)*(q-1);c=g 1 0 n e in c+(1-signum c)*n`div`2).map read.lines
g _ d _ 0=d
g b d m n=g(d-m`div`n*b)b n$m`mod`n
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), $/;

View all solutions