I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some operations with polynomials. E.g. if I need to do $g^{\frac{p-1}{q^e}}$. How can I do this with polynomial?


1 Answer 1


A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ such polynomials $$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$

Addition is by mod 2 addition of coefficients. When you multiply two polynomials, you take the remainder of the product modulo $f(x)$.

You can use square and multiply (see here) to compute the power $$a(x)^k=a(x)^{k_0+2 k_1+ 2^2 k_2+ \cdots+ 2^t k_t},$$ taking care to reduce modulo $f(x)$ from time to time, so the degrees of the squares don't get too large.


Your Answer

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

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