5
$\begingroup$

In the AKS paper, the authors based on the Lemma

There exist constants $c > 0$ and $n_0$ such that, for all $x\ge n_0$: $$\bigl|\{q \mid \text{$q$ is prime, $q\le x$ and $P(q − 1) > q^{2/3}$}\}\bigr|\ge c\frac{x}{\ln x},,円$$ where $P(q-1)$ denotes the greatest prime divisor of number $q-1$.

to conclude that the AKS primality test will find an integer $r=O((\log n)^3)$ with $\operatorname{ord}_r(n)>(\log n)^2$.

My question is how can we determine the hidden constant in the BigOh $r=O((\log n)^3)$? I have read papers involving the AKS algorithm but none of them mention the hidden constant!

asked Nov 2 at 14:58
$\endgroup$
2
  • 1
    $\begingroup$ Quick comment though I guess you are aware of this already. The $c$ constant you mention here comes from this paper link.springer.com/article/10.1007/BF01388980 so I guess you will have to get its value from here first, though a quick check in the paper did not allow me to conclude... $\endgroup$ Commented Nov 3 at 14:14
  • $\begingroup$ @NealYoung I've changed the condition. $\endgroup$ Commented Nov 4 at 15:13

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.