4
\$\begingroup\$

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.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Is n given to us via its prime factors as in the sample input? May we assume n is odd? \$\endgroup\$
    – xnor
    Mar 26, 2018 at 5:59
  • \$\begingroup\$ @xnor Challenge edited. \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 9:53
  • \$\begingroup\$ (now the challenge had been clarified, there is no reason to close as unclear) \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 9:53
  • \$\begingroup\$ Are we guaranteed that e>1? \$\endgroup\$
    – xnor
    Mar 26, 2018 at 10:34
  • \$\begingroup\$ @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)? \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 10:57

3 Answers 3

3
\$\begingroup\$

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!

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Nope, only for square-free numbers. \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 11:11
1
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Let me check how sympy.ntheory.factor_.factorint and sympy.numbers.igcdex works... \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 11:13
  • \$\begingroup\$ It looks like you're factoring to compute (p-1)(q-1), but would totient function ÆṪ be shorter and memory-efficient enough? \$\endgroup\$
    – xnor
    Mar 26, 2018 at 11:16
  • \$\begingroup\$ @xnor I searched for "euler" and can only find ÆE. Thanks! \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 11:16
  • \$\begingroup\$ 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). \$\endgroup\$
    – DELETE_ME
    Mar 26, 2018 at 11:20
  • \$\begingroup\$ The Carmichael function Æc should also work if that's any better. \$\endgroup\$
    – xnor
    Mar 26, 2018 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.