Return to ntl.rr CVS log

Up to [local] / OpenXM / src / ox_ntl

added ox_ntl

install `NTL'
   % make install-ntl

install ox_ntl
   % make install

EX.
  [1028] load("ntl.rr")$
  [1040] F=ntl.ex_data(4);
  x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225
  [1041] F=F*subst(F,x,x+1)$
  [1042] ntl.factor(PID,F);
  [[1,1],[x^16+16*x^15-16*x^14-1344*x^13-4080*x^12+32576*x^11+157376*x^10-255232*x^9-2062624*x^8-249088*x^7+10702080*x^6+9126912*x^5-18643712*x^4-24167424*x^3+2712576*x^2+10653696*x+2324736,1],[x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225,1]]

/* $OpenXM: OpenXM/src/ox_ntl/ntl.rr,v 1.1 2003/11/03 03:11:21 iwane Exp $ */

module ntl;
localf factor$
localf ex_data$
localf ex_data_tmp$


/* static variables */

/* extern variables */

#if 1
localf test$

/*&usage begin: ntl.test(PID, POLY)
 compare on ox_NTL and on asir.

example: 
[1028] F=ntl.ex_data(4);
x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225
[1029] F = F * subst(F, x, x + 1)$
[1030] ntl.factor(PID, F);
[[1,1],[x^16+16*x^15-16*x^14-1344*x^13-4080*x^12+32576*x^11+157376*x^10-255232*x^9-2062624*x^8-249088*x^7+10702080*x^6+9126912*x^5-18643712*x^4-24167424*x^3+2712576*x^2+10653696*x+2324736,1],[x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225,1]]
[1031] ntl.test(PID, F);
[CPU,0.121539,0.001354,GC,0.0222,0]


end: */
def test(PID, F)
{
	T0 = time();
	fctr(F);
	T1 = time();
	ntl.factor(PID, F);
	T2 = time();

	return (["CPU", T1[0]-T0[0],T2[0]-T1[0],"GC",T1[1]-T0[1],T2[1]-T1[1]]);
}

#endif

/*&usage begin: ntl.factor(PID, POLY)

  Factorize polynomial {POLY} over the rationals.

{RETURN}
	list
{POLY}
	univariate polynomial with rational coefficients 

description: 
  Factorizes polynomial {POLY} over the rationals.
  The result is represented by a list, whose elements are a pair represented as

[[num,1],[factor1,multiplicity1],[factor2,multiplicity2],...].

Products of all factor^multiplicity and num is equal to {POLY}.

The number {num} is determined so that ({POLY}/{num}) is an integral polynomial
and its content (GCD of all coefficients) is 1.

author: H.Iwane <iwane@math.sci.kobe-u.ac.jp> 

example: 
[1282] F=(x^5-1)*(x^3+1)^2;
x^11+2*x^8-x^6+x^5-2*x^3-1
[1283] ntl.factor(PID, F);
[[1,1],[x^4+x^3+x^2+x+1,1],[x-1,1],[x+1,2],[x^2-x+1,2]]
[1284] fctr(F);
[[1,1],[x-1,1],[x^4+x^3+x^2+x+1,1],[x+1,2],[x^2-x+1,2]]

ref: fctr
end:
*/
def factor(PID, POLY)
{
	local F, C, LIST, STR, RET, RET_NTL, VAR, I;
	local TYPE;

	/* 入力チェック */
	TYPE = type(POLY);
	if (TYPE == 0 || TYPE == 1) {
		return ([[POLY,1]]);
	} else if (TYPE != 2) {
		error("ntl.factor: invalid argument");
	}


	LIST = vars(POLY);
	if (length(LIST) >= 2) { /* 一変数多項式のみ */
		error("ntl.factor: invalid argument");
	}


	/* NTL で 有理係数多項式は不可 */
	F = ptozp(POLY);

	C = sdiv(POLY, F);

	ox_cmo_rpc(PID, "fctr", F);

	RET_NTL = ox_pop_cmo(PID);	

	/* ERROR Check */
	if (type(RET_NTL) != 4 || length(RET_NTL) < 2) {
		error(RET_NTL);
	}

	RET = cons([RET_NTL[0] * C, 1], RET_NTL[1]);

	return (RET);
}

/*&usage begin: ex_data_tmp(F, N)
  Generate sample irreducible polynomial

example:
[1032] F=t^3-p;       
-p+t^3
[1033] ntl.ex_data_tmp(F,3);
x^27-90*x^24+1089*x^21-62130*x^18+105507*x^15-16537410*x^12-30081453*x^9-1886601330*x^6+73062900*x^3-6859000
[1034] ntl.ex_data_tmp(F,4);
-x^81+459*x^78-76896*x^75+7538094*x^72-347721147*x^69+3240161703*x^66+1032617170332*x^63-37499673798288*x^60+784360767442050*x^57+150576308695750650*x^54+771023617441694964*x^51+67248913649472410184*x^48+13913995714637027898294*x^45+270221527865987051874714*x^42-8828542741395296724347412*x^39-154971101776040822743879716*x^36+4343529580943017469231383983*x^33+4648027555241630173815780123*x^30-1072436585643253024332438894564*x^27+16237394255218510503554781142602*x^24-134104542851048701593527668875195*x^21+727430949790032393675174790142991*x^18-2727255031466780569416130788693624*x^15+7102683996190585423335589883738868*x^12-12524463688445776069953452180105904*x^9+14119870779369458313271232460210576*x^6-8591747198480108022372636571451136*x^3+2346749360904699138972190279765184

ref: ex_data

end: */
def ex_data_tmp(F, N)
{
	FP = subst(F, p, prime(0));
	GP = subst(FP, t, x);

	for (I = 1; I < N; I++) {
		FP = subst(F, p, prime(I));
		GP = res(t, subst(GP, x, x-t), FP);
	}

	return (GP);
}

/*&usage begin: ntl.ex_data(N)
  Generate sample irreducible polynomial

example: 
[1028] ntl.ex_data(3);
x^8-40*x^6+352*x^4-960*x^2+576
[1029] ntl.ex_data(4);
x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225

ref:
ex_data_tmp

end: */
def ex_data(N)
{
	if (type(N) != 1 && type(N) != 10) {
		print("invalid argument");
		return (0);
	}

	return (ex_data_tmp(t^2-p, N));
}


endmodule;


end$