Given positive integer n
and e
, knowing that e<n
and that n
is the product of two different odd primes(but the primes are not directly given to you), find such a positive integer d
smaller than n
that, for each integer m
, (me)d ≡ m (mod n).
Your program should handle n
up to 24096 in 1TB space, but not necessary reasonable time. You can assume such a d
exist.
Sample Input: n=53*61=3233, e=17
Sample output: d=413
Note that your program will not be given the prime factor of n
.
Shortest code in bytes win.
n
given to us via its prime factors as in the sample input? May we assumen
is odd? \$\endgroup\$e>1
? \$\endgroup\$e>1
(except one that start brute-forcing at2
, but I don't think that's very special)? \$\endgroup\$