https://www.shoup.net/ntb/ntb-v2.pdf, page 523, algortithm IPT

I don't get the for loop, since "k" isn't used anywhere inside the loop. What am i missing?

• Just iterate $\lfloor \ell/2 \rfloor$-times? – kelalaka Nov 27 '19 at 15:47
• Yes, but what changes from one iteration to another? – Fiono Nov 27 '19 at 15:54
• Do you anything about coding? – kelalaka Nov 27 '19 at 16:09
• We prefer reproducing content on this website over simply leaving links. That way a question or answer isn't made useless to other users after the link goes dead. – Future Security Nov 27 '19 at 16:30

If $$f$$ is irreducible, then $$\gcd(X^{q^k}−X, f) = 1$$ for all positive integers $$k$$ up to $$\ell /2$$
What the loop does is just testing all the $$\gcd(X^{q^k}-X,f)$$ up to $$\ell/2$$.
To avoid computing $$X^{q^k}$$ at each $$k$$, you just compute $$X^{q^k}=(X^{q^{k-1}})^q=h^q$$.
At the $$k$$-th round you will have $$h=X^{q^k}$$.