File: [local] / OpenXM_contrib2 / asir2000 / lib / dfff (download)
Revision 1.2, Thu Dec 14 03:19:51 2000 UTC (23 years, 9 months ago) by noro
Branch: MAIN
CVS Tags: R_1_3_1-2, RELEASE_1_3_1_13b, RELEASE_1_2_3_12, RELEASE_1_2_3, RELEASE_1_2_2_KNOPPIX_b, RELEASE_1_2_2_KNOPPIX, RELEASE_1_2_2, RELEASE_1_2_1, KNOPPIX_2006, HEAD, DEB_REL_1_2_3-9 Changes since 1.1: +20 -1
lines
Added df_demo() for demonstration of distributed Cantor-Zassenhaus factorization.
|
/* $OpenXM: OpenXM_contrib2/asir2000/lib/dfff,v 1.2 2000/12/14 03:19:51 noro Exp $ */
#define MAXLEVEL 50
extern Proc1$
Proc1 = -1$
/*
dfff : distributed factorizer
XXX : This file overwrites several functions in 'fff', so
do not use this file with 'fff'.
If you want to use fctr_ff() in this file,
add the following line to your $HOME/.asirrc:
load("dfff")$
*/
#include "defs.h"
extern TPMOD,TQMOD$
def df_demo()
{
purge_stdin();
print("Degree of input polynomial to be factored => ",0);
Str = get_line();
N = eval_str(Str);
P = lprime(0);
setmod_ff(P);
for ( I = 0, F = 1; I < N; I++ )
F *= randpoly_ff(2,x);
print("");
print("Factorization of ",0);
print(F,0);
print(" over GF(",0); print(P,0); print(")");
print("");
R = fctr_ff(F);
print(R);
}
/*
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);
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);
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 )
return c_z_lm(F,E,0);
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 )
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 */
def ox_c_z_lm(F,E,M,Level)
{
setmod_ff(M);
F = simp_ff(F);
L = c_z_lm(F,E,Level);
return map(lmptop,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_lm(F,E,Level)
{
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 ) {
if ( Level >= MAXLEVEL ) {
L1 = c_z_lm(G,E,Level+1);
L2 = c_z_lm(sdiv(F,G),E,Level+1);
} else {
if ( Proc1 < 0 ) {
Proc1 = ox_launch();
if ( Level < 7 ) {
ox_cmo_rpc(Proc1,"print","[3"+rtostr(Level)+"m");
ox_pop_cmo(Proc1);
} else if ( Level < 14 ) {
ox_cmo_rpc(Proc1,"print","[3"+rtostr(7)+"m");
ox_pop_cmo(Proc1);
ox_cmo_rpc(Proc1,"print","[4"+rtostr(Level-7)+"m");
ox_pop_cmo(Proc1);
}
}
ox_cmo_rpc(Proc1,"ox_c_z_lm",lmptop(G),E,setmod_ff(),Level+1);
L2 = c_z_lm(sdiv(F,G),E,Level+1);
L1 = ox_pop_cmo(Proc1);
L1 = map(simp_ff,L1);
}
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$