10
\$\begingroup\$

Consider the integers modulo q where q is prime, a generator is any integer 1 < x < q so that x^1, x^2, ..., x^(q-1) covers all q-1 of the integers between 1 and q-1. For example, consider the integers modulo 7 (which we write as Z_7). Then 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1 covers all the values 3, 2, 6, 4, 5, 1 covers all the integers 1..6 as required.

The task is to write code that takes an input n and outputs a generator for Z_n. You cannot use any builtin or library that does this for you of course.

The only restriction on the performance of your code is that you must have tested it to completion with n = 4257452468389.

Note that 2^n means 2 to the power of n. That is ^ represents exponentiation.

\$\endgroup\$
13
  • \$\begingroup\$ Hmm...1 < x < q makes the challenge a lot easier imo. \$\endgroup\$ Jul 2 '17 at 11:49
  • \$\begingroup\$ @EriktheOutgolfer I am not sure I know what you mean? Those are just all the distinct integers that are not 0 or 1. \$\endgroup\$
    – user9206
    Jul 2 '17 at 11:52
  • \$\begingroup\$ I mean that it's easier than what many probably think...or maybe some inactive moment on PPCG. \$\endgroup\$ Jul 2 '17 at 11:53
  • 3
    \$\begingroup\$ But I think that requiring people to test it to completion to a large number is unnecessary...basically tio would just memory-error. \$\endgroup\$ Jul 2 '17 at 11:56
  • \$\begingroup\$ @Lembik Is there any case where there is no generator for a certain number? Some test cases would be good. \$\endgroup\$
    – Mr. Xcoder
    Jul 2 '17 at 11:58
13
\$\begingroup\$

Pyth, 16 15 bytes

f-1m.^T/tQdQPtQ

Test suite

If p is the input, we know that g^(p-1) = 1 mod p, so we just need to check that g^a != 1 mod p for any smaller a. But a must be a factor of p-1 for that to be possible, and any multiple of an a with that property will also have that property, so we only need to check that g^((p-1)/q) != 1 mod p for all prime factors q of p-1. So, we check all integers g in increasing order until we find one that works.

Explanation:

f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.
\$\endgroup\$
3
  • \$\begingroup\$ Pretty awesome! \$\endgroup\$
    – user9206
    Jul 2 '17 at 12:22
  • \$\begingroup\$ Does your code perform the factorization? \$\endgroup\$
    – user9206
    Jul 2 '17 at 12:23
  • \$\begingroup\$ @Lembik It does (the PtQ part). \$\endgroup\$ Jul 2 '17 at 12:24
5
\$\begingroup\$

Mathematica, 52 bytes

Inspired by isaacg's answer.

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
\$\endgroup\$
0

Your Answer

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