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.
1 < x < q
makes the challenge a lot easier imo. \$\endgroup\$