I’m writing in Maple V an algorithm that calculates a polynomial (error-locator polynomial).
I’m working in the finite field F_16, so a primitive element satisfy a^4+a+1. So I want to
have my output (that polynomial) in that field. I mean that he must simplify eg a^15 in 1.
To get that I make an alias: alias(al=RootOf(x^4+x+1)); and then I simplify my
polynomial.
But the problem is that he does not simplify it in the algorithm. The first time I run the algorithm with eg
sugiyama(al^9+al^12*x+x^2+al^14*x^3+al^13*x^4+x^5);
He gives me a polynomial that is not simplified (thus he gives me a very large polynomial
with al^130 in it)
If I run the program for the second time he does simplify it. Why is it that he won’t simplify the polynomial the first time. The problem is now that I can’t use this algorithm in another algorithm because the polynomial are to big (I want to have those polynomials (the primitive root alpha reduced).
The algorithm is as follows:
> sugiyama:=proc(E) > local a, b, r, A, t; > alias(al=RootOf(x^4+x+1)); # the alias! > t:=(degree(E,x)+1)/2: > a[0]:=x^(2*t): > b[0]:=E: > A[0]:=array(1..2,1..2,[[1,0],[0,1]]): > r:=1: > while degree(b[r-1],x) >= t do > b[r]:=simplify(a[r-1]-(Quo(a[r-1],b[r-1],x) mod 2)*b[r-1]) mod 2; > a[r]:=b[r-1]; > A[r]:=simplify(evalm(evalm((array(1..2,1..2,[[0,1], [1,-Quo(a[r-1],b[r-1],x)mod 2]])))&*evalm(A[r-1]))); > r:=r+1; > od; > collect(simplify(A[r-1][2,2]) mod 2, x); # and to simplify.... > end:
The reason your program needs two executions in order to get the desired result is as follows:
During the first execution of your program, Maple distinguishes between the formal parameter ’al’ that you use in your input and the alias ’al’ that you define inside of your procedure. In short, the alias definition does not affect the formal parameter ’al’ and that’s why your program returns long, unsimplified result.
If you go to the help page ?alias, you will find there this sentence:
"Parameters and local variables are not affected by aliases."
To see this more clearly, I have added one extra line to your program to show what happens. [Note: To see Maple output, please copy and paste the text below into maple V worksheet and execute.]
> sugiyama:=proc(E) local a,b,r,A,t; > alias(al=RootOf(x^4+x+1)); > print(evalb(al=RootOf(x^4+x+1))); #my extra line > t:=(degree(E,x)+1)/2: > a[0]:=x^(2*t): > b[0]:=E: > A[0]:=array(1..2,1..2,[[1,0],[0,1]]): > r:=1: > while degree(b[r-1],x) >= t do > b[r]:=simplify(a[r-1]-(Quo(a[r-1],b[r-1],x) mod 2)*b[r-1]) mod 2; > a[r]:=b[r-1]; > A[r]:=simplify(evalm(evalm((array(1..2,1..2,[[0,1], [1,-Quo(a[r-1],b[r-1],x)mod 2]])))&*evalm(A[r-1]))); > r:=r+1; > od; > collect(simplify(A[r-1][2,2]) mod 2, x); # and to simplify.... > end: > sugiyama(al^9+al^12*x+x^2+al^14*x^3+al^13*x^4+x^5); #first run
If you execute the above code, you will notice output ’false’ from the extra line
"print(evalb(al=RootOf(x^4+x+1)));" This means that Maple doesn’t recognize that
alias yet even though it is recognizable outside of the procedure now:
> print(evalb(al=RootOf(x^4+x+1)));
However, when you execute your program one more time, this time ’al’ in the input is recognized as one of the existing aliases and correct answer is returned:
> sugiyama(al^9+al^12*x+x^2+al^14*x^3+al^13*x^4+x^5); #second run
Notice ’false’ in the above even though separately issued command below yields the expected result, like before:
> print(evalb(al=RootOf(x^4+x+1)));
This is Maple’s peculiarity!
The only solution to your question of avoiding executing twice the same procedure so that alias ’al’ is recognized, the way I see it, is to define that alias before you execute your program like this:
> alias(al=RootOf(x^4+x+1)); #alias defined before the procedure > sugiyama2:=proc(E) local a,b,r,A,t; > #alias(al=RootOf(x^4+x+1)); #no alias definition in the procedure > print(evalb(al=RootOf(x^4+x+1))); #my extra line > t:=(degree(E,x)+1)/2: > a[0]:=x^(2*t): > b[0]:=E: > A[0]:=array(1..2,1..2,[[1,0],[0,1]]): > r:=1: > while degree(b[r-1],x) >= t do > b[r]:=simplify(a[r-1]-(Quo(a[r-1],b[r-1],x) mod 2)*b[r-1]) mod 2; > a[r]:=b[r-1]; > A[r]:=simplify(evalm(evalm((array(1..2,1..2,[[0,1], [1,-Quo(a[r-1],b[r-1],x)mod 2]])))&*evalm(A[r-1]))); > r:=r+1; > od; > collect(simplify(A[r-1][2,2]) mod 2, x); # and to simplify.... > end: > sugiyama2(al^9+al^12*x+x^2+al^14*x^3+al^13*x^4+x^5); #first run
The above gives the expected result in one run.
I have not found a way to fool Maple into replacing with the alias, that you want to define inside of your procedure, the formal parameter used by you.
My suggestion is just to define alias ’al’ in your worksheet before you ever use your new procedure ’sugiyama2’.
Your problem is that the alias command needs to be at the global level. I also simplified your algorithm. There is no need for all that indexing and those array commands. I think that this is much easier to understand:
> sugiyama:=proc(E) > local a, b, x, A, t, new_a, Q; > x:= indets(E)[]; > t:= (degree(E,x)+1)/2; > a:= x^(2*t); > b:= E; > A:= [[1,0],[0,1]]; > while degree(b,x) >= t do > Q:= Quo(a,b,x) mod 2; > new_a:= b; > b:= simplify(a-Q*b) mod 2; > a:= new_a; > A:= evalm([[0,1],[1,-Q]] &* A) > od; > collect(simplify(A[2,2]) mod 2, x) # and to simplify.... > end: > > alias(al=RootOf(x^4+x+1)); # the alias!
al
> sugiyama(al^9+al^12*x+x^2+al^14*x^3+al^13*x^4+x^5); 2 3 3 3 2 2 3 (1 + al + al + al ) x + (al + al ) x + (1 + al + al + al ) x 2 3 + 1 + al + al
Note that the way that I set it up, you do not need to use "x" as the variable in the polynomial.