|
⇤ ← Revision 1 as of 2010-12-02 19:34:27
Size: 235
Comment:
|
← Revision 2 as of 2010-12-03 00:10:19 ⇥
Size: 873
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| * ''Goal'' -- * ''Type'' -- * ''Priority'' -- * ''Difficulty'' -- * ''Prerequisites'' -- * ''Background'' -- |
* ''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 [[../PolynomialPrecision | p-adic polynomial precision]] * ''Background'' -- See [[http://homes.esat.kuleuven.be/~fvercaut/talks/pAdic.pdf | this talk]] |
| Line 8: | Line 8: |
| * ''Progress'' - | * ''Progress'' - not started |
| Line 14: | Line 14: |
1. 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. |
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.