/*
 * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED 
 * All rights reserved.
 * 
 * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
 * non-exclusive and royalty-free license to use, copy, modify and
 * redistribute, solely for non-commercial and non-profit purposes, the
 * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
 * conditions of this Agreement. For the avoidance of doubt, you acquire
 * only a limited right to use the SOFTWARE hereunder, and FLL or any
 * third party developer retains all rights, including but not limited to
 * copyrights, in and to the SOFTWARE.
 * 
 * (1) FLL does not grant you a license in any way for commercial
 * purposes. You may use the SOFTWARE only for non-commercial and
 * non-profit purposes only, such as academic, research and internal
 * business use.
 * (2) The SOFTWARE is protected by the Copyright Law of Japan and
 * international copyright treaties. If you make copies of the SOFTWARE,
 * with or without modification, as permitted hereunder, you shall affix
 * to all such copies of the SOFTWARE the above copyright notice.
 * (3) An explicit reference to this SOFTWARE and its copyright owner
 * shall be made on your publication or presentation in any form of the
 * results obtained by use of the SOFTWARE.
 * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
 * e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
 * for such modification or the source code of the modified part of the
 * SOFTWARE.
 * 
 * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
 * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
 * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
 * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
 * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
 * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
 * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
 * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
 * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
 * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
 * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
 * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
 * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
 * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
 * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
 *
 * $OpenXM: OpenXM_contrib2/asir2018/lib/fff,v 1.1 2018/09/19 05:45:08 noro Exp $
*/
/*
	fff : Univariate factorizer over a finite field.

    Revision History:

    99/05/18    noro    the first official version
    99/06/11    noro    
    99/07/27    noro    
*/
module fff $
  /* Empty for now. It will be used in a future. */
endmodule $

#include "defs.h"

extern TPMOD,TQMOD$

/*
  Input : a univariate polynomial F
  Output: a list [[F1,M1],[F2,M2],...], where
          Fi is a monic irreducible factor, Mi is its multiplicity.
          The leading coefficient of F is abondoned.
*/

def fctr_ff(F)
{
	F = simp_ff(F);
	F = F/LCOEF(F);
	L = sqfr_ff(F);
	for ( R = [], T = L; T != []; T = cdr(T) ) {
		S = car(T); A = S[0]; E = S[1];
		B = ddd_ff(A);
		R = append(append_mult_ff(B,E),R);
	}
	return R;
}

/*
  Input : a list of polynomial L; an integer E
  Output: a list s.t. [[L0,E],[L1,E],...]
          where Li = L[i]/leading coef of L[i]
*/

def append_mult_ff(L,E)
{
	for ( T = L, R = []; T != []; T = cdr(T) )
		R = cons([car(T)/LCOEF(car(T)),E],R);
	return R;
}

/*
	Input : a polynomial F
	Output: a list [[F1,M1],[F2,M2],...]
	        where Fi is a square free factor,
	        Mi is its multiplicity.
*/

def sqfr_ff(F)
{
	V = var(F);
	F1 = diff(F,V);
	L = [];
	/* F=H*Fq^p => F'=H'*Fq^p => gcd(F,F')=gcd(H,H')*Fq^p */
	if ( F1 != 0 ) {
		F1 = F1/LCOEF(F1);
		F2 = ugcd(F,F1);
		/* FLAT = H/gcd(H,H') : square free part of H */
		FLAT = sdiv(F,F2);
		FLAT /= LCOEF(FLAT);
		I = 0;
		/* square free factorization of H */
		while ( deg(FLAT,V) ) {
			while ( 1 ) {
				QR = sqr(F,FLAT);
				if ( !QR[1] ) {
					F = QR[0]; I++;
				} else
					break;
			}
			if ( !deg(F,V) )
				FLAT1 = simp_ff(1);
			else
				FLAT1 = ugcd(F,FLAT);
			FLAT1 /= LCOEF(FLAT1);
			G = sdiv(FLAT,FLAT1);
			FLAT = FLAT1;
			L = cons([G,I],L);
		}
	}
	/* now F = Fq^p */
	if ( deg(F,V) ) {
		Char = characteristic_ff();
		T = sqfr_ff(pthroot_p_ff(F));
		for ( R = []; T != []; T = cdr(T) ) {
			H = car(T); R = cons([H[0],Char*H[1]],R);
		}
	} else
		R = [];
	return append(L,R);
}

/* 
	Input : a polynomial F
	Output: F^(1/char)
*/

def pthroot_p_ff(F)
{
	V = var(F);
	DVR = characteristic_ff();
	PWR = DVR^(extdeg_ff()-1);
	for ( T = F, R = 0; T; ) {
		D1 = deg(T,V); C = coef(T,D1,V); T -= C*V^D1;
		R += C^PWR*V^idiv(D1,DVR);
	}
	return R;
}

/* 
	Input : a polynomial F of degree N
	Output: a list [V^Ord mod F,Tab]
	        where V = var(F), Ord = field order
	        Tab[i] = V^(i*Ord) mod F (i=0,...,N-1)
*/

def tab_ff(F)
{
	V = var(F);
	N = deg(F,V);
	F = F/LCOEF(F);
	XP = pwrmod_ff(F);
	R = pwrtab_ff(F,XP);
	return R;
}

/*
	Input : a square free polynomial F
	Output: a list [F1,F2,...]
	        where Fi is an irreducible factor of F.
*/

def ddd_ff(F)
{
	V = var(F);
	if ( deg(F,V) == 1 )
		return [F];
	TAB = tab_ff(F);
	for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
		lazy_lm(1);
		for ( T = 0, K = 0; K <= deg(W,V); K++ )
			if ( C = coef(W,K,V) )
				T += TAB[K]*C;
		lazy_lm(0);
		W = simp_ff(T);
		GCD = ugcd(F,W-V);
		if ( deg(GCD,V) ) {
			L = append(berlekamp_ff(GCD,I,TAB),L);
			F = sdiv(F,GCD);
			W = urem(W,F);
		}
	}
	if ( deg(F,V) )
		return cons(F,L);
	else
		return L;
}

/*
	Input : a polynomial
	Output: 1 if F is irreducible
			0 otherwise
*/

def irredcheck_ff(F)
{
	V = var(F);
	if ( deg(F,V) <= 1 )
		return 1;
	F1 = diff(F,V);
	if ( !F1 )
		return 0;
	F1 = F1/LCOEF(F1);
	if ( deg(ugcd(F,F1),V) > 0 )
		return 0;
	TAB = tab_ff(F);
	for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
		for ( T = 0, K = 0; K <= deg(W,V); K++ )
			if ( C = coef(W,K,V) )
				T += TAB[K]*C;
		W = T;
		GCD = ugcd(F,W-V);
		if ( deg(GCD,V) )
			return 0;
	}
	return 1;
}

/*
	Input : a square free (canonical) modular polynomial F
	Output: a list of polynomials [LF,CF,XP] where
		LF=the product of all the linear factors
		CF=F/LF
		XP=x^field_order mod CF
*/

def meq_linear_part_ff(F)
{
	F = simp_ff(F);
	F = F/LCOEF(F);
	V = var(F);
	if ( deg(F,V) == 1 )
		return [F,1,0];
T0 = time()[0];
	XP = pwrmod_ff(F);
	GCD = ugcd(F,XP-V);
	if ( deg(GCD,V) ) {
		GCD = GCD/LCOEF(GCD);
		F = sdiv(F,GCD);
		XP = srem(XP,F);
		R = GCD;
	} else
		R = 1;
TPMOD += time()[0]-T0;
	return [R,F,XP];
}

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the same degree D.
	Output: D
*/

def meq_ed_ff(F,XP)
{
T0 = time()[0];
	F = simp_ff(F);
	F = F/LCOEF(F);
	V = var(F);

	TAB = pwrtab_ff(F,XP);

	D = deg(F,V);
	for ( I = 1, W = V, L = []; 2*I <= D; I++ ) {
		lazy_lm(1);
		for ( T = 0, K = 0; K <= deg(W,V); K++ )
			if ( C = coef(W,K,V) )
				T += TAB[K]*C;
		lazy_lm(0);
		W = simp_ff(T);
		if ( W == V ) {
			D = I; break;
		}
	}
TQMOD += time()[0]-T0;
	return D;
}

/*
	Input : a square free polynomial F
	        an integer E
            an array TAB
            where all the irreducible factors of F has degree E
            and TAB[i] = V^(i*Ord) mod F. (V=var(F), Ord=field order)
    Output: a list containing all the irreducible factors of F
*/

def berlekamp_ff(F,E,TAB)
{
	V = var(F);
	N = deg(F,V);
	Q = newmat(N,N);
	for ( J = 0; J < N; J++ ) {
		T = urem(TAB[J],F);
		for ( I = 0; I < N; I++ ) {
			Q[I][J] = coef(T,I);
		}
	}
	for ( I = 0; I < N; I++ )
		Q[I][I] -= simp_ff(1);
	L = nullspace_ff(Q); MT = L[0]; IND = L[1];
	NF0 = N/E;
	PS = null_to_poly_ff(MT,IND,V);
	R = newvect(NF0); R[0] = F/LCOEF(F);
	for ( I = 1, NF = 1; NF < NF0 && I < NF0; I++ ) {
		PSI = PS[I];
		MP = minipoly_ff(PSI,F);
		ROOT = find_root_ff(MP); NR = length(ROOT);
		for ( J = 0; J < NF; J++ ) {
			if ( deg(R[J],V) == E )
				continue;
			for ( K = 0; K < NR; K++ ) {
				GCD = ugcd(R[J],PSI-ROOT[K]);
				if ( deg(GCD,V) > 0 && deg(GCD,V) < deg(R[J],V) ) {
					Q = sdiv(R[J],GCD);
					R[J] = Q; R[NF++] = GCD;
				}
			}
		}
	}
	return vtol(R);
}

/*
	Input : a matrix MT
	        an array IND
	        an indeterminate V
            MT is a matrix after Gaussian elimination
            IND[I] = 0 means that i-th column of MT represents a basis
            element of the null space.
	Output: an array R which contains all the basis element of
	         the null space of MT. Here, a basis element E is represented
	         as a polynomial P of V s.t. coef(P,i) = E[i].
*/

def null_to_poly_ff(MT,IND,V)
{
	N = size(MT)[0];
	for ( I = 0, J = 0; I < N; I++ )
		if ( IND[I] )
			J++;
	R = newvect(J);
	for ( I = 0, L = 0; I < N; I++ ) {
		if ( !IND[I] )
			continue;
		for ( J = K = 0, T = 0; J < N; J++ )
			if ( !IND[J] )
				T += MT[K++][I]*V^J;
			else if ( J == I )
				T -= V^I;
		R[L++] = simp_ff(T);
	}
	return R;
}

/*
	Input : a polynomial P, a polynomial F
	Output: a minimal polynomial MP(V) of P mod F.
*/

def minipoly_ff(P,F)
{
	V = var(P);
	P0 = P1 = simp_ff(1);
	L = [[P0,P0]];
	while ( 1 ) {
		/* P0 = V^K, P1 = P^K mod F */
		P0 *= V;
		P1 = urem(P*P1,F);
		/*
	        NP0 = P0-c1L1_0-c2L2_0-...,
            NP1 is a normal form w.r.t. [L1_1,L2_1,...]
		    NP1 = P1-c1L1_1-c2L2_1-...,
            NP0 represents the normal form computation.
	     */
		L1 = lnf_ff(P0,P1,L,V); NP0 = L1[0]; NP1 = L1[1];
		if ( !NP1 )
			return NP0;
		else
			L = lnf_insert([NP0,NP1],L,V);
	}
}

/*
	Input ; a list of polynomials [P0,P1] = [V^K,P^K mod F]
	        a sorted list L=[[L1_0,L1_1],[L2_0,L2_1],...]
	        of previously computed pairs of polynomials
	        an indeterminate V
	Output: a list of polynomials [NP0,NP1]
	        where NP1 = P1-c1L1_1-c2L2_1-...,
	              NP0 = P0-c1L1_0-c2L2_0-...,
            NP1 is a normal form w.r.t. [L1_1,L2_1,...]
            NP0 represents the normal form computation.
	        [L1_1,L_2_1,...] is sorted so that it is a triangular
	        linear basis s.t. deg(Li_1) > deg(Lj_1) for i<j.
*/

def lnf_ff(P0,P1,L,V)
{
	NP0 = P0; NP1 = P1;
	for ( T = L; T != []; T = cdr(T) ) {
		Q = car(T);
		D1 = deg(NP1,V);
		if ( D1 == deg(Q[1],V) ) {
			H = -coef(NP1,D1,V)/coef(Q[1],D1,V);
			NP0 += Q[0]*H;
			NP1 += Q[1]*H;
		}
	}
	return [NP0,NP1];
}

/*
	Input : a pair of polynomial P=[P0,P1],
	        a list L,
	        an indeterminate V
	Output: a list L1 s.t. L1 contains P and L
	        and L1 is sorted in the decreasing order
	        w.r.t. the degree of the second element
	        of elements in L1.
*/

def lnf_insert(P,L,V)
{
	if ( L == [] )
		return [P];
	else {
		P0 = car(L);
		if ( deg(P0[1],V) > deg(P[1],V) )
			return cons(P0,lnf_insert(P,cdr(L),V));
		else
			return cons(P,L);
	}
}

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: a list containing all the irreducible factors of F
*/

def c_z_ff(F,E)
{
	Type = field_type_ff();
	if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
		return c_z_lm(F,E);
	else
		return c_z_gf2n(F,E);
}		

/*
	Input : a square free polynomial P s.t. P splits into linear factors
	Output: a list containing all the root of P
*/

def find_root_ff(P)
{
	V = var(P);
	L = c_z_ff(P,1);
	for ( T = L, U = []; T != []; T = cdr(T) ) {
		S = car(T)/LCOEF(car(T)); U = cons(-coef(S,0,V),U);
	}
	return U;
}

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: an irreducible factor of F
*/

def c_z_one_ff(F,E)
{
	Type = field_type_ff();
	if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
		return c_z_one_lm(F,E);
	else
		return c_z_one_gf2n(F,E);
}		

/*
	Input : a square free polynomial P s.t. P splits into linear factors
	Output: a list containing a root of P
*/

def find_one_root_ff(P)
{
	V = var(P);
	LF = c_z_one_ff(P,1);
	U = -coef(LF/LCOEF(LF),0,V);
	return [U];
}

/*
	Input : an integer N; an indeterminate V
	Output: a polynomial F s.t. var(F) = V, deg(F) < N
	        and its coefs are random numbers in
	        the ground field.
*/

def randpoly_ff(N,V)
{
	for ( I = 0, S = 0; I < N; I++ )
		S += random_ff()*V^I;
	return S;	
}

/*
	Input : an integer N; an indeterminate V
	Output: a monic polynomial F s.t. var(F) = V, deg(F) = N-1
	        and its coefs are random numbers in
	        the ground field except for the leading term.
*/

def monic_randpoly_ff(N,V)
{
	for ( I = 0, N1 = N-1, S = 0; I < N1; I++ )
		S += random_ff()*V^I;
	return V^N1+S;	
}

/* GF(p) specific functions */

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: a list containing all the irreducible factors of F
*/

def c_z_lm(F,E)
{
	V = var(F);
	N = deg(F,V);
	if ( N == E )
		return [F];
	M = field_order_ff();
	K = idiv(N,E);
	L = [F];
	while ( 1 ) {
		W = monic_randpoly_ff(2*E,V);
		T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
		W = T-1;
		if ( !W )
			continue;
		G = ugcd(F,W);
		if ( deg(G,V) && deg(G,V) < N ) {
			L1 = c_z_lm(G,E);
			L2 = c_z_lm(sdiv(F,G),E);
			return append(L1,L2);
		}
	}
}

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: an irreducible factor of F
*/

def c_z_one_lm(F,E)
{
	V = var(F);
	N = deg(F,V);
	if ( N == E )
		return F;
	M = field_order_ff();
	K = idiv(N,E);
	while ( 1 ) {
		W = monic_randpoly_ff(2*E,V);
		T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
		W = T-1;
		if ( W ) {
			G = ugcd(F,W);
			D = deg(G,V);
			if ( D && D < N ) {
				if ( 2*D <= N ) {
					F1 = G; F2 = sdiv(F,G);
				} else {
					F2 = G; F1 = sdiv(F,G);
				}
				return c_z_one_lm(F1,E);
			}
		}
	}
}

/* GF(2^n) specific functions */

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: a list containing all the irreducible factors of F
*/

def c_z_gf2n(F,E)
{
	V = var(F);
	N = deg(F,V);
	if ( N == E )
		return [F];
	K = idiv(N,E);
	L = [F];
	while ( 1 ) {
		W = randpoly_ff(2*E,V);
		T = tracemod_gf2n(W,F,E);
		W = T-1;
		if ( !W )
			continue;
		G = ugcd(F,W);
		if ( deg(G,V) && deg(G,V) < N ) {
			L1 = c_z_gf2n(G,E);
			L2 = c_z_gf2n(sdiv(F,G),E);
			return append(L1,L2);
		}
	}
}

/*
	Input : a square free polynomial F s.t. 
	        all the irreducible factors of F
	        has the degree E.
	Output: an irreducible factor of F
*/

def c_z_one_gf2n(F,E)
{
	V = var(F);
	N = deg(F,V);
	if ( N == E )
		return F;
	K = idiv(N,E);
	while ( 1 ) {
		W = randpoly_ff(2*E,V);
		T = tracemod_gf2n(W,F,E);
		W = T-1;
		if ( W ) {
			G = ugcd(F,W);
			D = deg(G,V);
			if ( D && D < N ) {
				if ( 2*D <= N ) {
					F1 = G; F2 = sdiv(F,G);
				} else {
					F2 = G; F1 = sdiv(F,G);
				}
				return c_z_one_gf2n(F1,E);
			}
		}
	}
}

/*
	Input : an integer D
	Output: an irreducible polynomial F over GF(2)
	        of degree D.
*/

def defpoly_mod2(D)
{
	return gf2ntop(irredpoly_up2(D,0));
}

def dummy_time() {
	return [0,0,0,0];
}
end$