3
\$\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\$
  • 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 '18 at 5:59
  • \$\begingroup\$ @xnor Challenge edited. \$\endgroup\$ – user202729 Mar 26 '18 at 9:53
  • \$\begingroup\$ (now the challenge had been clarified, there is no reason to close as unclear) \$\endgroup\$ – user202729 Mar 26 '18 at 9:53
  • \$\begingroup\$ Are we guaranteed that e>1? \$\endgroup\$ – xnor Mar 26 '18 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\$ – user202729 Mar 26 '18 at 10:57
2
\$\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\$
  • \$\begingroup\$ @l4m2 Right, since the bit-size of m**(e*d) is e*d*log(m), where e*d is already close to n. I added an answer that doesn't need that much memory (luckily at just 1 byte cost). \$\endgroup\$ – Bubbler Mar 26 '18 at 7:10
1
\$\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\$
  • \$\begingroup\$ Nope, only for square-free numbers. \$\endgroup\$ – user202729 Mar 26 '18 at 11:11
0
\$\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\$
  • \$\begingroup\$ Let me check how sympy.ntheory.factor_.factorint and sympy.numbers.igcdex works... \$\endgroup\$ – user202729 Mar 26 '18 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 '18 at 11:16
  • \$\begingroup\$ @xnor I searched for "euler" and can only find ÆE. Thanks! \$\endgroup\$ – user202729 Mar 26 '18 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\$ – user202729 Mar 26 '18 at 11:20
  • \$\begingroup\$ The Carmichael function Æc should also work if that's any better. \$\endgroup\$ – xnor Mar 26 '18 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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