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