1
$\begingroup$

In the paper describing AKS primality test : http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf

On page no. 8 Lemma 4.7 last paragraph, I cannot understand how number of distinct polynomials with degree less than $t$ is calculated.

I understood that number of distinct polynomials with degree equal to 1 is $l + 1$, but how is the formula for a general degree ($t$) is derived? Can anyone please help me with this.

Although this paper also describes an induction method to prove this on page no. 8, but I could not understand how the number of polynomials with degree $(t - 1)$ is calculated here.Link: http://www.andrew.cmu.edu/user/jpaulson/AKS.pdf

$\endgroup$
  • 1
    $\begingroup$ Please post the relevant mathematical details here, and leave the link as reference for extended information. $\endgroup$ – barak manos Jun 19 '16 at 14:59
  • $\begingroup$ I have written my doubt clearly. Can you please say what mathematical details are you asking for. $\endgroup$ – Mayank Jun 19 '16 at 15:01
  • 1
    $\begingroup$ Any detail which is available at the given link but not within this post, AND - which is required (IYO) for answering this question. $\endgroup$ – barak manos Jun 19 '16 at 15:09
  • $\begingroup$ this is better written: dms.umontreal.ca/~andrew/PDF/Bulletin04.pdf $\endgroup$ – Will Jagy Jun 19 '16 at 17:42
0
$\begingroup$

I have understood the solution. The solution can be produced by using integral equation : e0 + e1+ e2+ ....+ el = t.

$\endgroup$
  • 1
    $\begingroup$ This post has been flagged. I first converted it to a comment, but I'm having second thoughts. I'm glad that you figured out the answer to your question. But for the benefit of future readers you should give more details before you wrap up this question by accepting your own answer. $\endgroup$ – Jyrki Lahtonen Jun 20 '16 at 6:47

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.