Aurimas Fišeras on Thu, 07 May 2009 12:49:04 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
q-polynomials (linearized polynomials, or p-polynomials) in PARI/GP? |
Hello, I'm writing some algorithms that deal with q-polynomials ([Ore33], [LN84]). If I store them in PARI as regular polynomials they take a lot of space (e.g. q-degree=10 2-polynomial is stored internally as degree 1024 pol[mod]). However, if I store them as vectors, (where vector's component number represent q-degree, and vector holds only coefficients (variable x is presumed), i=pos-1, x^(q^i) + x^(q^i) + ...) all operations with them are quite difficult to perform. For example: simple substitution with regular polynomial: Px=x^4+2*x^2+3*x; a=2; subst(Px, x, a); %1 = 30 same 2-polynomial efficiently coded as vector: qPx=[3,2,1]; res=0;for(i=1,length(qPx),res+= qPx[i] * a^(2^(i-1))); res %2 = 30 1. Is there a more elegant way to work with q-polinomials in PARI? 2. Is there any other computer algebra system that can work natively with q-polynomials (I couldn't find any)? 3. Would PARI be a "right" CAS to implement q-polynomials natively? ---- [Ore33] O. Ore. On a special class of polynomials. Transactions of the American Mathematical Society, 35:559-584, 1933. (http://www.jstor.org/stable/1989849) [LN84] R. Lidl, H. Niederreiter, Finite Fields. Cambridge, UK: Cambridge Univ. Press, 1984.