Goal -- Create an option for Zq and Qq to generate their defining polynomial by lifting from GF(p)[x] to a factor of x^q-1 (as opposed to lifting naively)
Type -- Convenience feature (computing Frobenius in such a representation is very fast)
Priority -- Medium-Low
Difficulty -- Medium
Prerequisites -- might rely on some polynomial code from p-adic polynomial precision
Background -- See this talk
Contributors --
Progress - not started
Related Tickets --
Discussion
Tasks
Given an irreducible polynomial f of degree n over GF(p), compute a lift of f that divides x^(p^n)-1. Plug this into Zq and Qq, and change the code for Frobenius to take advantage of this representation.