# $Source: /u/maple/research/lib/mod/src/RCS/Primfield,v $
# $Notify: mvanhoei@daisy.uwaterloo.ca
#
# Calling sequences: 1) Primfield(L) mod p
#                       where L = set or list
#
#                       This is the mod p equivalence of evala/Primfield
#                       Everything in L is reduced to elements of Fp(alpha)
#                       where Fp is the field with p elements and alpha is
#                       an irreducible RootOf over Fp. The procedure gives
#                       the substitution to Fp(alpha) and the inverse
#                       computation is also computed, if possible. Syntax
#                       is the same as evala/Primfield except for the fact
#                       that the optional second argument K of evala/Primfield
#                       is not allowed. The reason is that for the mod p case
#                       the field K must be Fp anyway because Maple does not
#                       support nested RootOf's mod p.
#
#                       Note that this procedure does allow nested RootOf's
#                       as input. It will transform these into non-nested
#                       RootOf's that are allowed as input in other mod p
#                       procedures in Maple.
#
#                       If L contains RootOfs that are reducible mod p then
#                       a factor will be chosen. If L contains variables then
#                       random values for those in Fp will be chosen, and no
#                       inverse will be computed. This can also be used to
#                       prevent computation of the inverse substitution when
#                       it is not needed.
#
#
#                    2) ReduceField(L,S) mod p
#                       where L=list, S=set of variables
#
#                       Now the substitutions (back and forth) are not returned,
#                       instead the forward substition is applied to all
#                       elements of L. So this is for a one-way, one-time use,
#                       substitution.
#                       The set S is a set of variables (can be empty) which are
#                       not replaced by random elements of Fp.
#                       Since the functionality of ReduceField is also available
#                       through Primfield, users do not need to use ReduceField
#                       and therefore it will not be documented by a help page.
#
# Author: Mark van Hoeij, May 2000.
#
`mod/Primfield`:=proc(L::{set,list},p::posint)
	local k,v,R,nk,ans,inv,P,nP,i,j,c,d;

	k:=[op(L)];
	v:=`mod/ReduceField`(k,{},p);
	
	R:=op(indets(v,RootOf));
	nk:=nops(k);
	ans:=[seq(k[i]=v[i],i=1..nk)];
	inv:=[];
if indets(L)={} and R<>NULL then
	# Compute inv
	P:=[1];
	for i from 1 to nk do
		P:=[seq(seq(v*c[i]^j,v=P),j=0..`algcurves/degree_ext`(
		  convert(k[i],RootOf),{})-1)]
	od;
	nP:=nops(P);
	P:=add(P[i]*d[i],i=1..nP);
	v:={coeffs(Expand(subs(seq(c[i]=v[i],i=1..nk), P) - d[0]*R) mod p,R)};
	v:=matrix(nops(v),nP+1,[seq( seq(coeff(i,d[j]),j=0..nP) ,i=v)]);
	v:=Nullspace(v) mod p;
	for i in v do if i[1]<>0 then
		inv:=subs(seq(d[j]=i[j+1]/i[1],j=1..nP),P) mod p;
		inv:=[R=subs(seq(c[i]=k[i],i=1..nk),inv)];
		break
	fi od
fi;
	[inv,ans]
end:

#savelib('`mod/Primfield`'):