in wikipedia, https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots,

it says there is no formula to compute primitive root mod n. and in the footnote 8, it seems that there are no fast algorithm neither.

but isn't that algorithm shown in this link fast enough? I mean, calculating modular exponentiation can be $O(\log n)$ fast, so this algorithm looks at most $O(n\log n)$. it's better than $O(n^2)$, so seems fast enough.

am I misunderstanding somewhere about time complexity analysis? or is it just not fast enough?

  • $\begingroup$ I believe the question is whether the primitive root of a $d$-digit number can be found quickly. If $n$ is a $d$-digit number, then $n$ is on the order of $10^d$. $\endgroup$ – Will Orrick Oct 29 '16 at 10:51
  • 1
    $\begingroup$ @WillOrrick but isn't that all same? like, the merge sort is $O(n\log n)$, if we let $n=10^d$ or something, it becomes $O(d10^d)$. for any polynomial-fast algorithm, if we replace it to use digits as input, they all go exponential. $\endgroup$ – user159234 Oct 29 '16 at 10:58
  • $\begingroup$ In sorting, the input is the list of items to be supported, which has size proportional to $n$. In arithmetic, the inputs are the numbers to be acted upon, whose length is their number of digits. Basic arithmetic operations such as addition, multiplication, and finding square roots are practical because their complexity is polynomial in the number of digits. If the algorithms were polynomial in the magnitude of the numbers themselves, arithmetic would bog down quickly. The question is whether finding primitive roots can be done as quickly as, say, finding square roots. $\endgroup$ – Will Orrick Oct 29 '16 at 11:17
  • $\begingroup$ @WillOrrick then the methods in en.wikipedia.org/wiki/Modular_exponentiation, are slow if it is $O(n)$, because in digits it is $O(10^d)$, and fast if it is $O(\log n)$, because in digits it is $O(d)$, right? $\endgroup$ – user159234 Oct 29 '16 at 11:31
  • $\begingroup$ That's right. In the linked article, the goal is to compute $b^e\mod m$. If $b$ has $r$ digits, $e$ has $s$ digits, and $m$ has $t$ digits, then the straightforward method and the memory-efficient method both take time exponential in $s$ (but only polynomial in $r$ and $t$). The right-to-left binary method is polynomial in all three. $\endgroup$ – Will Orrick Oct 29 '16 at 12:53

Your Answer

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

Browse other questions tagged or ask your own question.