## 15 Reputation

0 years, 313 days

## My own proc for pth root calculating ove...

I managed it by implementing the following code in Maple:

pthRoot := proc (f::polynom, x::name, p::prime, k::posint)
# returns the pth root for a polynomial f in F_q[x], q=p^k,
# f as in Theorem 20.3 in Victor Shoup- A computational Introduction to number theory and Algebra
# pth root calculated as in Theorem 20.3 mentioned
local ef, ge, ha, prim, geKoeff, haKoeff, i;
ef := f; prim := p;
ge := sort(collect(algsubs(x^prim = x, ef), x), x);
for i from 0 to degree(ge) do
geKoeff[i] := coeff(ge, x, i);
haKoeff[i] := evala(`mod`(Expand(`mod`(geKoeff[i]^(prim^(k-1)), prim)), prim))
end do;
ha := 0;
for i from 0 to degree(ge) do
ha := haKoeff[i]*x^i+ha
end do;
return ha ;
end proc;

Perhaps somebody will need it some time :)
(Probably my code is not well implemented but it works and outputs the thing I need so I am happy but I am still amenable for any improvements!!)

## thanks, but I need sth else...

@Ramakrishnan

Hello!
First of all I would like to thank you for your answer and your Maple Worksheet. The problem is that your calculating sth different to what I need. In my Algo I will need the pth (in my example p=3, as well as in your mw) root of a poly and the derivative of that pth root:
Like in (15) you have
root[3](6*x^5+(3*(2*lambda+1))*x^2, symbolic);

And in the next step I need
diff((6*x^5+6*lambda*x^2+3*x^2)^(1/3), x)

The thing you do are calculating the nth derivative of a polynomial, but I have to calculate the pth root and then derivate that pth root. I hope I made it more clear?

Can you help me with that problem?

## got it...

With Expand(...) mod 3; it calculates the right stuff.

I was wrong and Maple was right.. The remainder is x!

## ok if I change tau to anything, then it ...

ok if I change tau to anything, then it works correctly...

## Thanks...

yeah I forgot about the x, and thank you for telling me about the p prime being last!
I have found my error, I also had to pass (not only the x) but also my new alias rootf ..

I am neither used to programming nor to using maple. I dont know where to change Maple 2D ( I didnt even know I was using that) to 1D? I just open Maple, klick on "new Worksheet" or open one of my recent files and try to implement what is needed, so that my procs give me the output I want them to have. I suppose I am what is called a noob :(
nevertheless I am grateful for your input and help!
Thank you.

## not working...

@Carl Love
When I enter your code in Maple it says for

`<seq(a^(` q `^k), k= 0..n)>^+,`

that

`Error, invalid power`

So I dont know how to get rid of the error call?

I tried to build it on my own. But now I have some list problems, I attach my code:

```ElemRing := proc (f::polynom, p::posint, k::posint, tauh)
local func, prim, g, ring, i;
func := f; prim := p; g[0] := 0; ring := [];
for i to (prim^k)^degree(func) do
ring := ListTools:-Flatten([ring, [[g[i-1]]]]);
g[i] := `mod`(Nextpoly(g[i-1], x, tauh), prim)
end do;
return ring
end proc;

ElemRing2 := proc (f::polynom, p::posint, k::posint, tauh)
local func, prim, g, ring, i, gRepr;
func := f; prim := p; gRepr[0] := 0; ring := []; g[0] := 0;
for i to (prim^k)^degree(func) do
ring := ListTools:-FlattenOnce([ring, [[g[i-1]]]]);
gRepr[i] := `mod`(Nextpoly(gRepr[i-1], x, tauh), prim);
g[i] := collect(eval(gRepr[i], x = rootf), rootf)
end do;
return ring
end proc;

firred := `mod`(Randprime(2, T), 3);
alias(tau = RootOf(firred));
f := sort(tau*x+x^2);
alias(rootf = RootOf(f));
2
T  + 2 T + 2
tau
2
x  + tau x
tau, rootf
p := 3; k := 2; gamm[2] := rootf;
3
2
rootf
for i to nops(ElemRing2(f, 3, 2, tau)) do
if ElemRing2(f, 3, 2, tau)[i] = [gamm[2]] then
print(ElemRing(f, 3, 2, tau)[i])
end if
end do;
# nothing happens
ElemRing(f, 3, 2, tau);

ElemRing2(f, 3, 2, tau);
[[0], [1], [2], [tau], [tau + 1], [tau + 2], [2 tau],

[2 tau + 1], [2 tau + 2], [rootf], ...
]

for i to nops(ElemRing2(f, 3, 2, tau)) do
if ElemRing2(f, 3, 2, tau)[i] = [gamm[2]] then
print(ElemRing(f, 3, 2, tau)[i])
end if
end do;
# nothing happens
ElemRing2(f, p, k, tau)[10];
[rootf]
[gamm[2]];
[rootf]
evalb(ElemRing2(f, p, k, tau)[10] = [gamm[2]]);
false
```

And that is absolutely nonsense! Because the 10th element od my list is [rootf] and because gamm[2]= rootf, it should be true and not false?!!
Sometimes I get the right output 'x' but more often I dont and I dont see where I went wrong?

## still dont know how to get to the residu...

@Carl Love
Hello again,

Let's suppose we have f, F_q and the remainder x for an polynomial h in F_q[x]/(f). Then x represents the residue class containing all polynomials that leave the remainder x when divided by f. how can i tell Maple now, that it has to see this x not as the polynomial (the representative) but as the residue class.
I will have to enter those residue classes in my Algo FastEval as points where i want a Polynomial (now one of the representatives of degree>0) evaluated.
To be more specific: I am trying to implement the iterated Frobenius Algo from J. von zur Gathen/J. Gerhard in Modern Computer Algebra Edition 3.

What I want to get in Mapleis to see the residue classes as something like the alpha for my finite field.
F_4 ist F_2[T]/(T^2+T+1)={[0], [1], [T], [T+1]} the set of residue classes modulo f_irred=T^2+T+2.
Because I am looking now at the ring R=F_q[x]/(f), with q=4 in my example and f squarefree , f the polynomial that I want to factor at the end.
So lets suppose f=x^2+[T]x. Then R ist the residue class ring {[0], [1], [T], [T+1], [x], [Tx], [(T+1)x], [x+1], [x+T], [x+T+1], [Tx+1], [Tx+T], [Tx+T+1], [(T+1)x +1], [(T+1)x+T], [(T+1)x+T+1]} the set of the same elements as in F_4^2=F_16, but with a different modulo operation because f is not irreducible. And with iterated Frobenius I want to calculate a, a^q, ..., a^q^m, for any residue class in R, m <= n=degree(f).

So let be xi=[x], q=4, m=1, f=x^2+[T]x, a =residue class in R.
I set gamma[0]:=xi;
gamma[1]:=xi^q;  and be gamma~[1] the polynomial representative of the residue class gamma[1].
ell:=ceil(log[2](m));    # is there something like ilog2 but for ceil??
now I want to calculate     FastEval(gamma~[1], 2 (=the number of points to be evaluated), 2(=p=prime), gamma[0], gamma[1]).
Do you see what I am trying to get at? gamma ist a residue class, but gamma~ a polynomial which I want tu evaluate at several residue classes. On paper it works perfectly fine, but I dont see how maple can do what I want it to do?
Do I have to change FastEval? For Fast Eval please look at: https://mapleprimes.com/questions/226375-Return-Vs-Print-How-Do-I-Reach-The

Please, can you help me with this problem as well??
Or anybody else??

## Thank you :)...

Thank you again for your help.

So that means I wont get any residue classe in Maple only the canonical representative (= the polynomial representing the residue class of degree less than ( <) degree(f))?
I think I will take your advise and define new operations to avoid the repeated typing of Rem(..,f,x) mod p. But I am not sure what you mean with "remember tables"? Do you mean the remember command? Where do I put this command? How do I get hold of the procs/values that have been remembered?

And just a side question: How do I put my Maple code here in this "Answer box", so that it looks so nice as in your answer?
I really cannot thank you enough, you helped me really great, I appreciate your help very much!

## Thank you!...

@Carl Love
Thank you very much! Wow your code looks quite different!
I was never sure if I could write p::prime, and until now I never knew about the satisfies command!! How do you know this? Do you know any website which tells me how to make my procs as clean as yours? Your coding is in my opinion really, really beautiful :)
So I thank you not only for solving my problem but also for showing me so many improvements on my coding!

I am going to need the FastEval Algo on any finite field, and my example was only to check if I get at least the right values for f. The polynomial f will be any f in F_q[x]. I only checked for f wihtout any alpha coefficients if it is working correctly.
Do you know how I can avoid to declare my Galoisfield always anew? I can enter the prime in FastEval but do you know any way to get the alpha aswell? with alpha I mean: alias(tau = RootOf(aOut)), here with tau instead of alpha

Thank you so much!!!

 Page 1 of 1
﻿