factor.rlg 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479
  1. Tue Feb 10 12:26:19 2004 run on Linux
  2. comment factorizer test file;
  3. array a(20);
  4. factorize(x**2-1);
  5. {{x + 1,1},{x - 1,1}}
  6. % To make sure factorizer is loaded.
  7. algebraic procedure test(prob,nfac);
  8. begin integer m; scalar p,q,r;
  9. scalar basetime;
  10. p := for i:=1:nfac product a(i);
  11. Write "Problem number ",prob;
  12. symbolic (basetime := time());
  13. r := factorize p;
  14. symbolic (basetime := time() - basetime);
  15. q := for each j in r product first j^second j;
  16. m := for each j in r sum second j;
  17. if m=nfac and p=q then return ok;
  18. write "This example failed:";
  19. write r
  20. end;
  21. test
  22. % Wang test case 1;
  23. a(1) := x*y+z+10$
  24. a(2) := x*z+y+30$
  25. a(3) := x+y*z+20$
  26. test(1,3);
  27. Problem number 1
  28. ok
  29. % Wang test case 2;
  30. a(1) := x**3*z+x**3*y+z-11$
  31. a(2) := x**2*z**2+x**2*y**2+y+90$
  32. test(2,2);
  33. Problem number 2
  34. ok
  35. % Wang test case 3;
  36. a(1) := x**3*y**2+x*z**4+x+z$
  37. a(2) := x**3+x*y*z+y**2+y*z**3$
  38. test(3,2);
  39. Problem number 3
  40. ok
  41. % Wang test case 4;
  42. a(1) := x**2*z+y**4*z**2+5$
  43. a(2) := x*y**3+z**2$
  44. a(3) := -x**3*y+z**2+3$
  45. a(4) := x**3*y**4+z**2$
  46. test(4,4);
  47. Problem number 4
  48. ok
  49. % Wang test case 5;
  50. a(1) := 3*u**2*x**3*y**4*z+x*z**2+y**2*z**2+19*y**2$
  51. a(2) := u**2*y**4*z**2+x**2*z+5$
  52. a(3) := u**2+x**3*y**4+z**2$
  53. test(5,3);
  54. Problem number 5
  55. ok
  56. % Wang test case 6;
  57. a(1) := w**4*x**5*y**6-w**4*z**3+w**2*x**3*y+x*y**2*z**2$
  58. a(2) := w**4*z**6-w**3*x**3*y-w**2*x**2*y**2*z**2+x**5*z
  59. -x**4*y**2+y**2*z**3$
  60. a(3) := -x**5*z**3+x**2*y**3+y*z$
  61. test(6,3);
  62. Problem number 6
  63. ok
  64. % Wang test case 7;
  65. a(1) := x+y+z-2$
  66. a(2) := x+y+z-2$
  67. a(3) := x+y+z-3$
  68. a(4) := x+y+z-3$
  69. a(5) := x+y+z-3$
  70. test(7,5);
  71. Problem number 7
  72. ok
  73. % Wang test case 8;
  74. a(1) := -z**31-w**12*z**20+y**18-y**14+x**2*y**2+x**21+w**2$
  75. a(2) := -15*y**2*z**16+29*w**4*x**12*z**3+21*x**3*z**2+3*w**15*y**20$
  76. % Commented out, since it can take a long time.
  77. % TEST(8,2);
  78. % Wang test case 9;
  79. a(1) := 18*u**2*w**3*x*z**2+10*u**2*w*x*y**3+15*u*z**2+6*w**2*y**3*z**2$
  80. a(2) := x$
  81. a(3) := 25*u**2*w**3*y*z**4+32*u**2*w**4*y**4*z**3-
  82. 48*u**2*x**2*y**3*z**3-2*u**2*w*x**2*y**2+44*u*w*x*y**4*z**4-
  83. 8*u*w*x**3*z**4+4*w**2*x+11*w**2*x**3*y+12*y**3*z**2$
  84. a(4) := z$
  85. a(5) := z$
  86. a(6) := u$
  87. a(7) := u$
  88. a(8) := u$
  89. a(9) := u$
  90. test(9,9);
  91. Problem number 9
  92. ok
  93. % Wang test case 10;
  94. a(1) := 31*u**2*x*z+35*w**2*y**2+40*w*x**2+6*x*y$
  95. a(2) := 42*u**2*w**2*y**2+47*u**2*w**2*z+22*u**2*w**2+9*u**2*w*x**2+21
  96. *u**2*w*x*y*z+37*u**2*y**2*z+u**2*w**2*x*y**2*z**2+8*u**2*w**2
  97. *z**2+24*u**2*w*x*y**2*z**2+24*u**2*x**2*y*z**2+12*u**2*x*y**2
  98. *z**2+13*u*w**2*x**2*y**2+27*u*w**2*x**2*y+39*u*w*x*z+43*u*
  99. x**2*y+44*u*w**2* z**2+37*w**2*x*y+29*w**2*y**2+31*w**2*y*z**2
  100. +12*w*x**2*y*z+43*w*x*y*z**2+22*x*y**2+23*x*y*z+24*x*y+41*y**2
  101. *z$
  102. test(10,2);
  103. Problem number 10
  104. ok
  105. % Wang test case 11;
  106. a(1) := -36*u**2*w**3*x*y*z**3-31*u**2*w**3*y**2+20*u**2*w**2*x**2*y**2
  107. *z**2-36*u**2*w*x*y**3*z+46*u**2*w*x+9*u**2*y**2-36*u*w**2*y**3
  108. +9*u*w*y**3-5*u*w*x**2*y**3+48*u*w*x**3*y**2*z+23*u*w*x**3*y**2
  109. -43*u*x**3*y**3*z**3-46*u*x**3*y**2+29*w**3*x*y**3*z**2-
  110. 14*w**3*x**3*y**3*z**2-45*x**3-8*x*y**2$
  111. a(2) := 13*u**3*w**2*x*y*z**3-4*u*x*y**2-w**3*z**3-47*x*y$
  112. a(3) := x$
  113. a(4) := y$
  114. test(11,4);
  115. Problem number 11
  116. ok
  117. % Wang test case 12;
  118. a(1) := x+y+z-3$
  119. a(2) := x+y+z-3$
  120. a(3) := x+y+z-3$
  121. test(12,3);
  122. Problem number 12
  123. ok
  124. % Wang test case 13;
  125. a(1) := 2*w*z+45*x**3-9*y**3-y**2+3*z**3$
  126. a(2) := w**2*z**3-w**2+47*x*y$
  127. test(13,2);
  128. Problem number 13
  129. ok
  130. % Wang test case 14;
  131. a(1) := 18*x**4*y**5+41*x**4*y**2-37*x**4+26*x**3*y**4+38*x**2*y**4-29*
  132. x**2*y**3-22*y**5$
  133. a(2) := 33*x**5*y**6-22*x**4+35*x**3*y+11*y**2$
  134. test(14,2);
  135. Problem number 14
  136. ok
  137. % Wang test case 15;
  138. a(1) := 12*w**2*x*y*z**3-w**2*z**3+w**2-29*x-3*x*y**2$
  139. a(2) := 14*w**2*y**2+2*w*z+18*x**3*y-8*x*y**2-y**2+3*z**3$
  140. a(3) := z$
  141. a(4) := z$
  142. a(5) := y$
  143. a(6) := y$
  144. a(7) := y$
  145. a(8) := x$
  146. a(9) := x$
  147. a(10) := x$
  148. a(11) := x$
  149. a(12) := x$
  150. a(13) := x$
  151. test(15,13);
  152. Problem number 15
  153. ok
  154. % Test 16 - the 40th degree polynomial that comes from
  155. % SIGSAM problem number 7;
  156. a(1) := 8192*y**10+20480*y**9+58368*y**8-161792*y**7+198656*y**6+
  157. 199680*y**5-414848*y**4-4160*y**3+171816*y**2-48556*y+469$
  158. a(2) := 8192*y**10+12288*y**9+66560*y**8-22528*y**7-138240*y**6+
  159. 572928*y**5-90496*y**4-356032*y**3+113032*y**2+23420*y-8179$
  160. a(3) := 4096*y**10+8192*y**9+1600*y**8-20608*y**7+20032*y**6+87360*y**5-
  161. 105904*y**4+18544*y**3+11888*y**2-3416*y+1$
  162. a(4) := 4096*y**10+8192*y**9-3008*y**8-30848*y**7+21056*y**6+146496*
  163. y**5-221360*y**4+1232*y**3+144464*y**2-78488*y+11993$
  164. test(16,4);
  165. Problem number 16
  166. ok
  167. % Test 17 - taken from Erich Kaltofen's thesis. This polynomial
  168. % splits mod all possible primes p;
  169. a(1) := x**25-25*x**20-3500*x**15-57500*x**10+21875*x**5-3125$
  170. test(17,1);
  171. Problem number 17
  172. ok
  173. % Test 18 - another 'hard-to-factorize' univariate;
  174. a(1) := x**18+9*x**17+45*x**16+126*x**15+189*x**14+27*x**13-
  175. 540*x**12-1215*x**11+1377*x**10+15444*x**9+46899*x**8+
  176. 90153*x**7+133893*x**6+125388*x**5+29160*x**4-
  177. 32076*x**3+26244*x**2-8748*x+2916$
  178. test(18,1);
  179. Problem number 18
  180. ok
  181. % Test 19 - another example chosen to lead to false splits mod p;
  182. a(1) := x**16+4*x**12-16*x**11+80*x**9+2*x**8+160*x**7+
  183. 128*x**6-160*x**5+28*x**4-48*x**3+128*x**2-16*x+1$
  184. a(2) := x**16+4*x**12+16*x**11-80*x**9+2*x**8-160*x**7+
  185. 128*x**6+160*x**5+28*x**4+48*x**3+128*x**2+16*x+1$
  186. test(19,2);
  187. Problem number 19
  188. ok
  189. % End of all tests;
  190. end;
  191. Time for test: 270 ms, plus GC time: 10 ms