1
$\begingroup$

I looked at the article of AKS in wikipedia (https://en.wikipedia.org/wiki/AKS_primality_test) and I don't understand how can I do the last level in a polynomial time (relatively to the number of digits of $n$). I need to check if there are polynomials $f(x),g(x)$ so that $(x+a)^n-(x^n+a)=nf(x)+(x^r-1)g(x)$.

How can I do that in a polynomial time? Calculating the coefficients of $(x+a)^n-(x^n+a)$ using the binomial theorem takes an exponential time and even if I can check if $(x+a)^n-(x^n+a)=nf(x)+(x^r-1)g(x)$ in a polynomial time, I still need to check this for every $f(x),g(x)$, which is at least exponential time.

Is there a trick or something that lets me do it in a shorter time?

Thanks for answering

$\endgroup$
1
  • $\begingroup$ Both the polynomial exponent and degree are constrained by a modulo. You also only test for $s$ different $a$ values (the loop end in step 5 on the wiki page), and the paper shows $s$ and $r$ grow slow enough so the whole algorithm is polynomial time. Running some implementations over various sizes does show the result is polynomial time with an exponent of 6+epsilon, just as expected. That still makes it very slow compared to APR-CL or ECPP in practice. $\endgroup$
    – DanaJ
    Jul 19, 2020 at 12:09

1 Answer 1

1
$\begingroup$

If $u(x)$ is a polynomial over $\Bbb Z$ there is a unique polynomial $v(x)$ such that $$u(x)\equiv v(x)\mod{\left<n,x^r-1\right>}$$ and where $\deg v<r$ and the coefficients of $v$ lie in $\{0,1,\ldots,n-1\}$. Call finding $v(x)$ given $u(x)$ reducing $u(x)$ modulo $\left<n,x^r-1\right>$.

So we have to reduce $(x+a)^n-x^n-a$ modulo $\left<n,x^r-1\right>$ and determine if that is zero. The hard part is reducing $(x+a)^n$ modulo $\left<n,x^r-1\right>$. One can do that in polynomial time by adapting the exponentiation by squaring method. This requires $O(\log n)$ iterations, and each stage required reducing a polynomial of degree $<2n$ and with coefficients of size $O(nr)$ modulo $\left<n,x^r-1\right>$.

$\endgroup$
1
  • $\begingroup$ I didn't understand how can I use the exponentation by squaring method in order to reduce the polynomial $\endgroup$
    – uri gluck
    Jun 15, 2020 at 18:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.