9
\$\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\$
  • \$\begingroup\$ Hmm...1 < x < q makes the challenge a lot easier imo. \$\endgroup\$ – Erik the Outgolfer 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\$ – Erik the Outgolfer 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\$ – Erik the Outgolfer 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\$
  • \$\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\$ – Erik the Outgolfer 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\$
-3
\$\begingroup\$
%MATLAB CODE
%Program to generate Z_n for an integer n
n = input('Enter a number to find modulo')
q = input ('Enter a prime number greater than the number you wished to find modulo')
if n>=q 
   fprintf('Error')
   exit(1)
end
for R=1:q-1
    fprintf(rem(n.^R, q))
    fprintf('\n')
end
\$\endgroup\$
  • 1
    \$\begingroup\$ This isn't solving the right problem. Your code should, for example, take one input and give one output. \$\endgroup\$ – user9206 Jul 2 '17 at 16:29
  • 1
    \$\begingroup\$ Also, this code isn't golfed at all. Golfed code needs to be as short as possible, so you can remove the input text and spaces around equals signs and such. \$\endgroup\$ – Comrade SparklePony Jul 2 '17 at 16:59
  • 3
    \$\begingroup\$ @ComradeSparklePony I think the first problem that it isn't solving the right problem should be tackled first :) \$\endgroup\$ – user9206 Jul 2 '17 at 17:08

Your Answer

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