Annotation of OpenXM/src/ox_ntl/ntl.rr, Revision 1.1
1.1 ! iwane 1: /* $OpenXM$ */
! 2:
! 3: module ntl;
! 4: localf factor$
! 5: localf ex_data$
! 6: localf ex_data_tmp$
! 7:
! 8:
! 9: /* static variables */
! 10:
! 11: /* extern variables */
! 12:
! 13: #if 1
! 14: localf test$
! 15:
! 16: /*&usage begin: ntl.test(PID, POLY)
! 17: compare on ox_NTL and on asir.
! 18:
! 19: example:
! 20: [1028] F=ntl.ex_data(4);
! 21: x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225
! 22: [1029] F = F * subst(F, x, x + 1)$
! 23: [1030] ntl.factor(PID, F);
! 24: [[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]]
! 25: [1031] ntl.test(PID, F);
! 26: [CPU,0.121539,0.001354,GC,0.0222,0]
! 27:
! 28:
! 29: end: */
! 30: def test(PID, F)
! 31: {
! 32: T0 = time();
! 33: fctr(F);
! 34: T1 = time();
! 35: ntl.factor(PID, F);
! 36: T2 = time();
! 37:
! 38: return (["CPU", T1[0]-T0[0],T2[0]-T1[0],"GC",T1[1]-T0[1],T2[1]-T1[1]]);
! 39: }
! 40:
! 41: #endif
! 42:
! 43: /*&usage begin: ntl.factor(PID, POLY)
! 44:
! 45: Factorize polynomial {POLY} over the rationals.
! 46:
! 47: {RETURN}
! 48: list
! 49: {POLY}
! 50: univariate polynomial with rational coefficients
! 51:
! 52: description:
! 53: Factorizes polynomial {POLY} over the rationals.
! 54: The result is represented by a list, whose elements are a pair represented as
! 55:
! 56: [[num,1],[factor1,multiplicity1],[factor2,multiplicity2],...].
! 57:
! 58: Products of all factor^multiplicity and num is equal to {POLY}.
! 59:
! 60: The number {num} is determined so that ({POLY}/{num}) is an integral polynomial
! 61: and its content (GCD of all coefficients) is 1.
! 62:
! 63: author: H.Iwane <iwane@math.sci.kobe-u.ac.jp>
! 64:
! 65: example:
! 66: [1282] F=(x^5-1)*(x^3+1)^2;
! 67: x^11+2*x^8-x^6+x^5-2*x^3-1
! 68: [1283] ntl.factor(PID, F);
! 69: [[1,1],[x^4+x^3+x^2+x+1,1],[x-1,1],[x+1,2],[x^2-x+1,2]]
! 70: [1284] fctr(F);
! 71: [[1,1],[x-1,1],[x^4+x^3+x^2+x+1,1],[x+1,2],[x^2-x+1,2]]
! 72:
! 73: ref: fctr
! 74: end:
! 75: */
! 76: def factor(PID, POLY)
! 77: {
! 78: local F, C, LIST, STR, RET, RET_NTL, VAR, I;
! 79: local TYPE;
! 80:
! 81: /* 入力チェック */
! 82: TYPE = type(POLY);
! 83: if (TYPE == 0 || TYPE == 1) {
! 84: return ([[POLY,1]]);
! 85: } else if (TYPE != 2) {
! 86: error("ntl.factor: invalid argument");
! 87: }
! 88:
! 89:
! 90: LIST = vars(POLY);
! 91: if (length(LIST) >= 2) { /* 一変数多項式のみ */
! 92: error("ntl.factor: invalid argument");
! 93: }
! 94:
! 95:
! 96: /* NTL で 有理係数多項式は不可 */
! 97: F = ptozp(POLY);
! 98:
! 99: C = sdiv(POLY, F);
! 100:
! 101: ox_cmo_rpc(PID, "fctr", F);
! 102:
! 103: RET_NTL = ox_pop_cmo(PID);
! 104:
! 105: /* ERROR Check */
! 106: if (type(RET_NTL) != 4 || length(RET_NTL) < 2) {
! 107: error(RET_NTL);
! 108: }
! 109:
! 110: RET = cons([RET_NTL[0] * C, 1], RET_NTL[1]);
! 111:
! 112: return (RET);
! 113: }
! 114:
! 115: /*&usage begin: ex_data_tmp(F, N)
! 116: Generate sample irreducible polynomial
! 117:
! 118: example:
! 119: [1032] F=t^3-p;
! 120: -p+t^3
! 121: [1033] ntl.ex_data_tmp(F,3);
! 122: 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
! 123: [1034] ntl.ex_data_tmp(F,4);
! 124: -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
! 125:
! 126: ref: ex_data
! 127:
! 128: end: */
! 129: def ex_data_tmp(F, N)
! 130: {
! 131: FP = subst(F, p, prime(0));
! 132: GP = subst(FP, t, x);
! 133:
! 134: for (I = 1; I < N; I++) {
! 135: FP = subst(F, p, prime(I));
! 136: GP = res(t, subst(GP, x, x-t), FP);
! 137: }
! 138:
! 139: return (GP);
! 140: }
! 141:
! 142: /*&usage begin: ntl.ex_data(N)
! 143: Generate sample irreducible polynomial
! 144:
! 145: example:
! 146: [1028] ntl.ex_data(3);
! 147: x^8-40*x^6+352*x^4-960*x^2+576
! 148: [1029] ntl.ex_data(4);
! 149: x^16-136*x^14+6476*x^12-141912*x^10+1513334*x^8-7453176*x^6+13950764*x^4-5596840*x^2+46225
! 150:
! 151: ref:
! 152: ex_data_tmp
! 153:
! 154: end: */
! 155: def ex_data(N)
! 156: {
! 157: if (type(N) != 1 && type(N) != 10) {
! 158: print("invalid argument");
! 159: return (0);
! 160: }
! 161:
! 162: return (ex_data_tmp(t^2-p, N));
! 163: }
! 164:
! 165:
! 166: endmodule;
! 167:
! 168:
! 169: end$
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ntl.rr CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / ox_ntl