# unRSA: solve the private key

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.

• Is n given to us via its prime factors as in the sample input? May we assume n is odd?
– xnor
Mar 26 '18 at 5:59
• @xnor Challenge edited. Mar 26 '18 at 9:53
• (now the challenge had been clarified, there is no reason to close as unclear) Mar 26 '18 at 9:53
• Are we guaranteed that e>1?
– xnor
Mar 26 '18 at 10:34
• @xnor Apart from making the problem trivial, is there any other problems with it? May some algorithm only work correctly with e>1 (except one that start brute-forcing at 2, but I don't think that's very special)? Mar 26 '18 at 10:57

# 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!

# 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.

• Nope, only for square-free numbers. Mar 26 '18 at 11:11

# 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.

• Let me check how sympy.ntheory.factor_.factorint and sympy.numbers.igcdex works... Mar 26 '18 at 11:13
• It looks like you're factoring to compute (p-1)(q-1), but would totient function ÆṪ be shorter and memory-efficient enough?
– xnor
Mar 26 '18 at 11:16
• @xnor I searched for "euler" and can only find ÆE. Thanks! Mar 26 '18 at 11:16
• Now I should check this... | No problem, totient uses factorint internally, which uses "trial division, Pollard rho algorithm, or p-1 algorithm", all of them use polynomial memory (if I read correctly). Mar 26 '18 at 11:20
• The Carmichael function Æc should also work if that's any better.
– xnor
Mar 26 '18 at 11:21