unRSA: solve the private key

Question

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, (m^e)^d ≡ m (mod n).

Your program should handle n up to 2⁴⁰⁹⁶ 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.

Answer 1

Python 3, 77 bytes

def f(n,e):r=range(n);all(any(m-pow(m,e*d,n)for m in r)or print(d)for d in r)

Try it online!

Direct translation of the requirement. any(...) becomes false when the smallest correct d is found, and print(d) returns None, making all(...) stop running.

76 bytes, if unlimited memory is allowed

def f(n,e):r=range(n);all(any(m**(e*d)%n-m for m in r)or print(d)for d in r)

Try it online!

Answer 2

Python 2, 65 bytes

n,e=input()
p=s=1
while n%~p:p+=1
while s%e:s-=p*n/~p+p
print s/e

Try it online!

Finds a prime factor p of n to obtain the order φ(n)=(p-1)(n/p-1). Then, solves the modular equation d * e % φ(n) == 1 by counting up values s of the form s = 1 + c * φ(n) until a multiple of eis obtained. Since all expressions are arithmetical without exponents, only log-space is used.

The code actually uses p to stand for one below the prime to save bytes on initialization.

---

Python 2, 78 bytes

lambda n,e:pow(e,F(F(n))-1,F(n))
F=lambda n:sum(k/n*k%n==1for k in range(n*n))

Try it online!

A direct expression using Dennis's totient function implementation.

Answer 3

Jelly, 5 bytes

Thanks to xnor for -2 bytes! (pointing out ÆṪ, totient function)

ÆṪæi@

Try it online!

Previously I used Æf’Pæi@ at 7 bytes.