Knowledge

Polynomial decomposition

Source 📝

2164: 1733: 2159:{\displaystyle 2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 2}.} 1190: 1408: 659: 955: 1672: 777: 1510: 1220: 433: 458: 1530: 1225: 960: 463: 939: 268: 1185:{\displaystyle {\begin{aligned}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{aligned}}} 1525: 1714: 193: 817: 672: 57: 2442: 869: 837: 839:. The restriction in the definition to polynomials of degree greater than one excludes the infinitely many decompositions possible with linear polynomials. 1403:{\displaystyle {\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&\left(x^{3}-2\right)\circ \left(x^{2}-2x+1\right),\end{aligned}}} 1419: 279: 1519:, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form. For example, the decomposition 2250:
Jean-Charles Faugère, Ludovic Perret, "An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography",
654:{\displaystyle {\begin{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}} 125:
The rest of this article discusses only univariate polynomials; algorithms also exist for multivariate polynomials of arbitrary degree.
2174:
The first algorithm for polynomial decomposition was published in 1985, though it had been discovered in 1976, and implemented in the
2470: 2252: 2179: 2426: 871:, and the degrees of the components are the same up to linear transformations, but possibly in different order; this is 115: 878: 204: 2494: 1667:{\displaystyle {\begin{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}} 2199:
A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.
2186: 1211: 80: 2365: 2182: 1683: 2397: 1207: 111: 76: 31: 88: 143: 2489: 1724: 782: 446: 439: 2402: 772:{\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}} 2352: 2235: 1516: 1196: 2466: 2300: 949:
A polynomial decomposition may enable more efficient evaluation of a polynomial. For example,
36: 2407: 2334: 2284: 2261: 2228: 1720: 119: 2446: 2190: 92: 848: 1195:
can be calculated with 3 multiplications and 3 additions using the decomposition, while
822: 2427:"A polynomial time algorithm for computing all minimal decompositions of a polynomial" 2411: 2338: 2276:
Capi Corrales-Rodrigáñez, "A note on Ritt's theorem on decomposition of polynomials",
2196:
A 1989 algorithm runs in polynomial time but with restrictions on the characteristic.
2185:. That algorithm takes exponential time in worst case, but works independently of the 2483: 2288: 669:
A polynomial may have distinct decompositions into indecomposable polynomials where
2385: 2381: 2217: 1505:{\displaystyle 1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}.} 842: 2325:
David R. Barton, Richard Zippel (1985). "Polynomial Decomposition Algorithms".
2265: 84: 24: 428:{\displaystyle f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,} 1203: 134: 2239: 2175: 1202:
A polynomial decomposition enables calculation of symbolic roots using
2232: 2463:
Computer Algebra and Symbolic Computation: Mathematical Methods
1413:
the roots of this irreducible polynomial can be calculated as
2461:
Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition".
1723:
gives equivalent results but in a form that is difficult to
122:, the product of the degrees of the composed polynomials. 1727:
and difficult to understand; one of the four roots is:
1736: 1686: 1528: 1422: 1223: 958: 881: 851: 825: 785: 675: 461: 282: 207: 146: 39: 118:). The degree of a composite polynomial is always a 98:Polynomials which are decomposable in this way are 2158: 1708: 1666: 1504: 1402: 1184: 933: 863: 831: 811: 771: 653: 427: 262: 187: 133:In the simplest case, one of the polynomials is a 51: 2222:Transactions of the American Mathematical Society 1199:would require 7 multiplications and 8 additions. 934:{\displaystyle x^{2}\circ x^{3}=x^{3}\circ x^{2}} 263:{\displaystyle g=x^{2}-3x+1{\text{ and }}h=x^{3}} 2388:(1989). "Polynomial Decomposition Algorithms". 8: 2401: 2299:The examples below were calculated using 2127: 2123: 2100: 2096: 2081: 2075: 2065: 2060: 2058: 2045: 2041: 2018: 2014: 1999: 1993: 1982: 1980: 1959: 1955: 1932: 1928: 1913: 1907: 1900: 1883: 1879: 1856: 1852: 1837: 1831: 1809: 1805: 1782: 1778: 1763: 1757: 1747: 1743: 1735: 1693: 1685: 1636: 1611: 1598: 1570: 1554: 1538: 1529: 1527: 1487: 1483: 1468: 1456: 1437: 1433: 1421: 1367: 1338: 1325: 1297: 1281: 1265: 1249: 1233: 1224: 1222: 1155: 1133: 1105: 1092: 1064: 1048: 1032: 1016: 1000: 984: 968: 959: 957: 925: 912: 899: 886: 880: 850: 824: 803: 790: 784: 763: 744: 731: 718: 699: 686: 674: 626: 592: 576: 563: 535: 519: 503: 487: 471: 462: 460: 407: 388: 378: 359: 281: 254: 239: 218: 206: 173: 157: 145: 38: 16:Factorization under function composition 2311: 2309: 2207: 1719:but straightforward application of the 1214:. For example, using the decomposition 873:Ritt's polynomial decomposition theorem 2434:ACM Communications in Computer Algebra 2213: 2211: 2220:, "Prime and Composite Polynomials", 1709:{\displaystyle 2\pm {\sqrt {3\pm i}}} 116:factored into products of polynomials 7: 2315:Where each ± is taken independently. 2278:Journal of Pure and Applied Algebra 79:greater than 1; it is an algebraic 14: 1210:. This technique is used in many 188:{\displaystyle f=x^{6}-3x^{3}+1} 2390:Journal of Symbolic Computation 2327:Journal of Symbolic Computation 2253:Journal of Symbolic Computation 812:{\displaystyle g_{i}\neq h_{i}} 1657: 1629: 1623: 1604: 641: 619: 613: 569: 413: 400: 385: 371: 365: 352: 343: 340: 334: 328: 319: 313: 310: 298: 292: 286: 1: 2412:10.1016/S0747-7171(89)80027-6 2339:10.1016/S0747-7171(85)80012-2 2283::3:293–296 (6 December 1990) 2289:10.1016/0022-4049(90)90086-W 2511: 104:indecomposable polynomials 102:; those which are not are 87:are known for decomposing 2266:10.1016/j.jsc.2008.02.005 2227::1:51–66 (January, 1922) 110:(not to be confused with 2425:Raoul Blankertz (2014). 2353:Functional Decomposition 1212:computer algebra systems 81:functional decomposition 52:{\displaystyle g\circ h} 21:polynomial decomposition 2183:computer algebra system 1208:irreducible polynomials 112:irreducible polynomials 2160: 1710: 1668: 1506: 1404: 1186: 935: 865: 833: 813: 773: 655: 429: 264: 189: 89:univariate polynomials 53: 32:functional composition 2161: 1711: 1669: 1507: 1405: 1187: 936: 866: 834: 814: 774: 656: 440:ring operator symbol 430: 265: 190: 100:composite polynomials 54: 1734: 1684: 1526: 1515:Even in the case of 1420: 1221: 956: 879: 849: 823: 783: 673: 459: 447:function composition 280: 205: 144: 37: 2260::1676-1689 (2009), 1517:quartic polynomials 864:{\displaystyle m=n} 2445:2015-09-24 at the 2189:of the underlying 2156: 1706: 1664: 1662: 1502: 1400: 1398: 1182: 1180: 931: 861: 829: 809: 769: 651: 649: 425: 260: 185: 114:, which cannot be 49: 19:In mathematics, a 2151: 2146: 2138: 2110: 2086: 2028: 2004: 1975: 1971: 1970: 1942: 1918: 1866: 1842: 1792: 1768: 1704: 1497: 1478: 1473: 832:{\displaystyle i} 242: 108:prime polynomials 2502: 2495:Computer algebra 2476: 2449: 2441: 2431: 2422: 2416: 2415: 2405: 2378: 2372: 2362: 2356: 2351:Richard Zippel, 2349: 2343: 2342: 2322: 2316: 2313: 2304: 2297: 2291: 2274: 2268: 2248: 2242: 2215: 2165: 2163: 2162: 2157: 2152: 2147: 2139: 2137: 2136: 2135: 2131: 2122: 2118: 2111: 2109: 2108: 2104: 2091: 2087: 2082: 2076: 2064: 2059: 2054: 2053: 2049: 2040: 2036: 2029: 2027: 2026: 2022: 2009: 2005: 2000: 1994: 1983: 1981: 1976: 1969: 1968: 1967: 1963: 1954: 1950: 1943: 1941: 1940: 1936: 1923: 1919: 1914: 1908: 1899: 1892: 1891: 1887: 1878: 1874: 1867: 1865: 1864: 1860: 1847: 1843: 1838: 1832: 1818: 1817: 1813: 1804: 1800: 1793: 1791: 1790: 1786: 1773: 1769: 1764: 1758: 1746: 1745: 1744: 1715: 1713: 1712: 1707: 1705: 1694: 1677:gives the roots 1673: 1671: 1670: 1665: 1663: 1641: 1640: 1616: 1615: 1599: 1575: 1574: 1559: 1558: 1543: 1542: 1532: 1511: 1509: 1508: 1503: 1498: 1496: 1495: 1491: 1474: 1469: 1458: 1457: 1446: 1445: 1441: 1409: 1407: 1406: 1401: 1399: 1392: 1388: 1372: 1371: 1354: 1350: 1343: 1342: 1326: 1302: 1301: 1286: 1285: 1270: 1269: 1254: 1253: 1238: 1237: 1227: 1206:, even for some 1191: 1189: 1188: 1183: 1181: 1177: 1173: 1160: 1159: 1142: 1138: 1137: 1121: 1117: 1110: 1109: 1093: 1069: 1068: 1053: 1052: 1037: 1036: 1021: 1020: 1005: 1004: 989: 988: 973: 972: 962: 940: 938: 937: 932: 930: 929: 917: 916: 904: 903: 891: 890: 870: 868: 867: 862: 838: 836: 835: 830: 818: 816: 815: 810: 808: 807: 795: 794: 778: 776: 775: 770: 768: 767: 749: 748: 736: 735: 723: 722: 704: 703: 691: 690: 660: 658: 657: 652: 650: 631: 630: 597: 596: 581: 580: 564: 540: 539: 524: 523: 508: 507: 492: 491: 476: 475: 465: 452:Less trivially, 434: 432: 431: 426: 412: 411: 393: 392: 383: 382: 364: 363: 269: 267: 266: 261: 259: 258: 243: 240: 223: 222: 198:decomposes into 194: 192: 191: 186: 178: 177: 162: 161: 120:composite number 58: 56: 55: 50: 2510: 2509: 2505: 2504: 2503: 2501: 2500: 2499: 2480: 2479: 2473: 2460: 2457: 2452: 2447:Wayback Machine 2429: 2424: 2423: 2419: 2403:10.1.1.416.6491 2380: 2379: 2375: 2363: 2359: 2350: 2346: 2324: 2323: 2319: 2314: 2307: 2298: 2294: 2275: 2271: 2249: 2245: 2233:10.2307/1988911 2216: 2209: 2205: 2172: 2092: 2077: 2074: 2070: 2069: 2010: 1995: 1992: 1988: 1987: 1924: 1909: 1906: 1902: 1901: 1848: 1833: 1830: 1826: 1825: 1774: 1759: 1756: 1752: 1751: 1732: 1731: 1721:quartic formula 1682: 1681: 1661: 1660: 1632: 1607: 1600: 1592: 1591: 1566: 1550: 1534: 1524: 1523: 1479: 1429: 1418: 1417: 1397: 1396: 1363: 1362: 1358: 1334: 1333: 1329: 1327: 1319: 1318: 1293: 1277: 1261: 1245: 1229: 1219: 1218: 1197:Horner's method 1179: 1178: 1151: 1150: 1146: 1129: 1125: 1101: 1100: 1096: 1094: 1086: 1085: 1060: 1044: 1028: 1012: 996: 980: 964: 954: 953: 947: 921: 908: 895: 882: 877: 876: 875:. For example, 847: 846: 821: 820: 799: 786: 781: 780: 759: 740: 727: 714: 695: 682: 671: 670: 667: 648: 647: 622: 588: 572: 565: 557: 556: 531: 515: 499: 483: 467: 457: 456: 403: 384: 374: 355: 278: 277: 250: 241: and  214: 203: 202: 169: 153: 142: 141: 137:. For example, 131: 93:polynomial time 59:of polynomials 35: 34: 17: 12: 11: 5: 2508: 2506: 2498: 2497: 2492: 2482: 2481: 2478: 2477: 2471: 2456: 2453: 2451: 2450: 2417: 2396:(5): 445–456. 2373: 2357: 2344: 2333:(2): 159–168. 2317: 2305: 2292: 2269: 2243: 2206: 2204: 2201: 2187:characteristic 2171: 2168: 2167: 2166: 2155: 2150: 2145: 2142: 2134: 2130: 2126: 2121: 2117: 2114: 2107: 2103: 2099: 2095: 2090: 2085: 2080: 2073: 2068: 2063: 2057: 2052: 2048: 2044: 2039: 2035: 2032: 2025: 2021: 2017: 2013: 2008: 2003: 1998: 1991: 1986: 1979: 1974: 1966: 1962: 1958: 1953: 1949: 1946: 1939: 1935: 1931: 1927: 1922: 1917: 1912: 1905: 1898: 1895: 1890: 1886: 1882: 1877: 1873: 1870: 1863: 1859: 1855: 1851: 1846: 1841: 1836: 1829: 1824: 1821: 1816: 1812: 1808: 1803: 1799: 1796: 1789: 1785: 1781: 1777: 1772: 1767: 1762: 1755: 1750: 1742: 1739: 1717: 1716: 1703: 1700: 1697: 1692: 1689: 1675: 1674: 1659: 1656: 1653: 1650: 1647: 1644: 1639: 1635: 1631: 1628: 1625: 1622: 1619: 1614: 1610: 1606: 1603: 1601: 1597: 1594: 1593: 1590: 1587: 1584: 1581: 1578: 1573: 1569: 1565: 1562: 1557: 1553: 1549: 1546: 1541: 1537: 1533: 1531: 1513: 1512: 1501: 1494: 1490: 1486: 1482: 1477: 1472: 1467: 1464: 1461: 1455: 1452: 1449: 1444: 1440: 1436: 1432: 1428: 1425: 1411: 1410: 1395: 1391: 1387: 1384: 1381: 1378: 1375: 1370: 1366: 1361: 1357: 1353: 1349: 1346: 1341: 1337: 1332: 1328: 1324: 1321: 1320: 1317: 1314: 1311: 1308: 1305: 1300: 1296: 1292: 1289: 1284: 1280: 1276: 1273: 1268: 1264: 1260: 1257: 1252: 1248: 1244: 1241: 1236: 1232: 1228: 1226: 1193: 1192: 1176: 1172: 1169: 1166: 1163: 1158: 1154: 1149: 1145: 1141: 1136: 1132: 1128: 1124: 1120: 1116: 1113: 1108: 1104: 1099: 1095: 1091: 1088: 1087: 1084: 1081: 1078: 1075: 1072: 1067: 1063: 1059: 1056: 1051: 1047: 1043: 1040: 1035: 1031: 1027: 1024: 1019: 1015: 1011: 1008: 1003: 999: 995: 992: 987: 983: 979: 976: 971: 967: 963: 961: 946: 943: 928: 924: 920: 915: 911: 907: 902: 898: 894: 889: 885: 860: 857: 854: 828: 806: 802: 798: 793: 789: 766: 762: 758: 755: 752: 747: 743: 739: 734: 730: 726: 721: 717: 713: 710: 707: 702: 698: 694: 689: 685: 681: 678: 666: 663: 662: 661: 646: 643: 640: 637: 634: 629: 625: 621: 618: 615: 612: 609: 606: 603: 600: 595: 591: 587: 584: 579: 575: 571: 568: 566: 562: 559: 558: 555: 552: 549: 546: 543: 538: 534: 530: 527: 522: 518: 514: 511: 506: 502: 498: 495: 490: 486: 482: 479: 474: 470: 466: 464: 436: 435: 424: 421: 418: 415: 410: 406: 402: 399: 396: 391: 387: 381: 377: 373: 370: 367: 362: 358: 354: 351: 348: 345: 342: 339: 336: 333: 330: 327: 324: 321: 318: 315: 312: 309: 306: 303: 300: 297: 294: 291: 288: 285: 271: 270: 257: 253: 249: 246: 238: 235: 232: 229: 226: 221: 217: 213: 210: 196: 195: 184: 181: 176: 172: 168: 165: 160: 156: 152: 149: 130: 127: 48: 45: 42: 15: 13: 10: 9: 6: 4: 3: 2: 2507: 2496: 2493: 2491: 2488: 2487: 2485: 2474: 2472:1-56881-159-4 2468: 2464: 2459: 2458: 2454: 2448: 2444: 2439: 2435: 2428: 2421: 2418: 2413: 2409: 2404: 2399: 2395: 2391: 2387: 2386:Landau, Susan 2383: 2382:Kozen, Dexter 2377: 2374: 2370: 2368: 2361: 2358: 2354: 2348: 2345: 2340: 2336: 2332: 2328: 2321: 2318: 2312: 2310: 2306: 2302: 2296: 2293: 2290: 2286: 2282: 2279: 2273: 2270: 2267: 2263: 2259: 2255: 2254: 2247: 2244: 2241: 2237: 2234: 2230: 2226: 2223: 2219: 2214: 2212: 2208: 2202: 2200: 2197: 2194: 2192: 2188: 2184: 2181: 2177: 2169: 2153: 2148: 2143: 2140: 2132: 2128: 2124: 2119: 2115: 2112: 2105: 2101: 2097: 2093: 2088: 2083: 2078: 2071: 2066: 2061: 2055: 2050: 2046: 2042: 2037: 2033: 2030: 2023: 2019: 2015: 2011: 2006: 2001: 1996: 1989: 1984: 1977: 1972: 1964: 1960: 1956: 1951: 1947: 1944: 1937: 1933: 1929: 1925: 1920: 1915: 1910: 1903: 1896: 1893: 1888: 1884: 1880: 1875: 1871: 1868: 1861: 1857: 1853: 1849: 1844: 1839: 1834: 1827: 1822: 1819: 1814: 1810: 1806: 1801: 1797: 1794: 1787: 1783: 1779: 1775: 1770: 1765: 1760: 1753: 1748: 1740: 1737: 1730: 1729: 1728: 1726: 1722: 1701: 1698: 1695: 1690: 1687: 1680: 1679: 1678: 1654: 1651: 1648: 1645: 1642: 1637: 1633: 1626: 1620: 1617: 1612: 1608: 1602: 1595: 1588: 1585: 1582: 1579: 1576: 1571: 1567: 1563: 1560: 1555: 1551: 1547: 1544: 1539: 1535: 1522: 1521: 1520: 1518: 1499: 1492: 1488: 1484: 1480: 1475: 1470: 1465: 1462: 1459: 1453: 1450: 1447: 1442: 1438: 1434: 1430: 1426: 1423: 1416: 1415: 1414: 1393: 1389: 1385: 1382: 1379: 1376: 1373: 1368: 1364: 1359: 1355: 1351: 1347: 1344: 1339: 1335: 1330: 1322: 1315: 1312: 1309: 1306: 1303: 1298: 1294: 1290: 1287: 1282: 1278: 1274: 1271: 1266: 1262: 1258: 1255: 1250: 1246: 1242: 1239: 1234: 1230: 1217: 1216: 1215: 1213: 1209: 1205: 1200: 1198: 1174: 1170: 1167: 1164: 1161: 1156: 1152: 1147: 1143: 1139: 1134: 1130: 1126: 1122: 1118: 1114: 1111: 1106: 1102: 1097: 1089: 1082: 1079: 1076: 1073: 1070: 1065: 1061: 1057: 1054: 1049: 1045: 1041: 1038: 1033: 1029: 1025: 1022: 1017: 1013: 1009: 1006: 1001: 997: 993: 990: 985: 981: 977: 974: 969: 965: 952: 951: 950: 944: 942: 926: 922: 918: 913: 909: 905: 900: 896: 892: 887: 883: 874: 858: 855: 852: 844: 840: 826: 804: 800: 796: 791: 787: 764: 760: 756: 753: 750: 745: 741: 737: 732: 728: 724: 719: 715: 711: 708: 705: 700: 696: 692: 687: 683: 679: 676: 664: 644: 638: 635: 632: 627: 623: 616: 610: 607: 604: 601: 598: 593: 589: 585: 582: 577: 573: 567: 560: 553: 550: 547: 544: 541: 536: 532: 528: 525: 520: 516: 512: 509: 504: 500: 496: 493: 488: 484: 480: 477: 472: 468: 455: 454: 453: 450: 448: 444: 443: 422: 419: 416: 408: 404: 397: 394: 389: 379: 375: 368: 360: 356: 349: 346: 337: 331: 325: 322: 316: 307: 304: 301: 295: 289: 283: 276: 275: 274: 255: 251: 247: 244: 236: 233: 230: 227: 224: 219: 215: 211: 208: 201: 200: 199: 182: 179: 174: 170: 166: 163: 158: 154: 150: 147: 140: 139: 138: 136: 128: 126: 123: 121: 117: 113: 109: 106:or sometimes 105: 101: 96: 94: 90: 86: 82: 78: 74: 70: 66: 62: 46: 43: 40: 33: 29: 26: 22: 2462: 2437: 2433: 2420: 2393: 2389: 2376: 2366: 2360: 2347: 2330: 2326: 2320: 2295: 2280: 2277: 2272: 2257: 2251: 2246: 2224: 2221: 2198: 2195: 2173: 1718: 1676: 1514: 1412: 1201: 1194: 948: 945:Applications 872: 845:proved that 841: 668: 451: 441: 437: 272: 197: 132: 124: 107: 103: 99: 97: 72: 68: 64: 60: 27: 23:expresses a 20: 18: 2490:Polynomials 843:Joseph Ritt 2484:Categories 2455:References 2367:polydecomp 2170:Algorithms 665:Uniqueness 445:to denote 438:using the 85:Algorithms 25:polynomial 2440:(187): 1. 2398:CiteSeerX 2218:J.F. Ritt 2056:− 1985:− 1978:− 1741:− 1699:± 1691:± 1643:− 1627:∘ 1577:− 1545:− 1466:± 1460:− 1454:± 1427:± 1374:− 1356:∘ 1345:− 1313:− 1304:− 1272:− 1240:− 1144:∘ 1123:∘ 1112:− 1080:− 919:∘ 893:∘ 819:for some 797:≠ 757:∘ 754:⋯ 751:∘ 738:∘ 712:∘ 709:⋯ 706:∘ 693:∘ 633:− 617:∘ 542:− 510:− 478:− 395:− 305:∘ 225:− 164:− 44:∘ 2443:Archived 2369:function 2364:See the 1725:simplify 1204:radicals 135:monomial 129:Examples 67:, where 2355:, 1996. 2240:1988911 2176:Macsyma 30:as the 2469:  2400:  2301:Maxima 2238:  2180:Maxima 779:where 273:since 77:degree 2430:(PDF) 2236:JSTOR 2203:Notes 2191:field 75:have 2467:ISBN 71:and 63:and 2408:doi 2335:doi 2285:doi 2262:doi 2229:doi 1897:156 91:in 2486:: 2465:. 2438:48 2436:. 2432:. 2406:. 2392:. 2384:; 2329:. 2308:^ 2281:68 2258:44 2256:, 2225:23 2210:^ 2193:. 2116:72 2084:10 2062:52 2034:72 2002:10 1948:72 1916:10 1872:72 1840:10 1823:36 1798:72 1766:10 1564:18 1291:15 1275:20 1259:15 1058:10 1042:16 1026:19 1010:16 994:10 941:. 611:41 602:32 554:41 545:64 529:68 513:44 497:21 449:. 95:. 83:. 2475:. 2414:. 2410:: 2394:7 2371:. 2341:. 2337:: 2331:1 2303:. 2287:: 2264:: 2231:: 2178:/ 2154:. 2149:2 2144:8 2141:+ 2133:3 2129:/ 2125:1 2120:) 2113:+ 2106:2 2102:/ 2098:3 2094:3 2089:i 2079:8 2072:( 2067:3 2051:3 2047:/ 2043:1 2038:) 2031:+ 2024:2 2020:/ 2016:3 2012:3 2007:i 1997:8 1990:( 1973:6 1965:3 1961:/ 1957:1 1952:) 1945:+ 1938:2 1934:/ 1930:3 1926:3 1921:i 1911:8 1904:( 1894:+ 1889:3 1885:/ 1881:1 1876:) 1869:+ 1862:2 1858:/ 1854:3 1850:3 1845:i 1835:8 1828:( 1820:+ 1815:3 1811:/ 1807:2 1802:) 1795:+ 1788:2 1784:/ 1780:3 1776:3 1771:i 1761:8 1754:( 1749:9 1738:2 1702:i 1696:3 1688:2 1658:) 1655:1 1652:+ 1649:x 1646:4 1638:2 1634:x 1630:( 1624:) 1621:1 1618:+ 1613:2 1609:x 1605:( 1596:= 1589:2 1586:+ 1583:x 1580:8 1572:2 1568:x 1561:+ 1556:3 1552:x 1548:8 1540:4 1536:x 1500:. 1493:3 1489:/ 1485:1 1481:2 1476:i 1471:3 1463:1 1451:1 1448:, 1443:6 1439:/ 1435:1 1431:2 1424:1 1394:, 1390:) 1386:1 1383:+ 1380:x 1377:2 1369:2 1365:x 1360:( 1352:) 1348:2 1340:3 1336:x 1331:( 1323:= 1316:1 1310:x 1307:6 1299:2 1295:x 1288:+ 1283:3 1279:x 1267:4 1263:x 1256:+ 1251:5 1247:x 1243:6 1235:6 1231:x 1175:) 1171:1 1168:+ 1165:x 1162:+ 1157:2 1153:x 1148:( 1140:) 1135:2 1131:x 1127:( 1119:) 1115:2 1107:2 1103:x 1098:( 1090:= 1083:1 1077:x 1074:4 1071:+ 1066:2 1062:x 1055:+ 1050:3 1046:x 1039:+ 1034:4 1030:x 1023:+ 1018:5 1014:x 1007:+ 1002:6 998:x 991:+ 986:7 982:x 978:4 975:+ 970:8 966:x 927:2 923:x 914:3 910:x 906:= 901:3 897:x 888:2 884:x 859:n 856:= 853:m 827:i 805:i 801:h 792:i 788:g 765:n 761:h 746:2 742:h 733:1 729:h 725:= 720:m 716:g 701:2 697:g 688:1 684:g 680:= 677:f 645:. 642:) 639:x 636:2 628:2 624:x 620:( 614:) 608:+ 605:x 599:+ 594:2 590:x 586:9 583:+ 578:3 574:x 570:( 561:= 551:+ 548:x 537:2 533:x 526:+ 521:3 517:x 505:4 501:x 494:+ 489:5 485:x 481:6 473:6 469:x 442:∘ 423:, 420:1 417:+ 414:) 409:3 405:x 401:( 398:3 390:2 386:) 380:3 376:x 372:( 369:= 366:) 361:3 357:x 353:( 350:g 347:= 344:) 341:) 338:x 335:( 332:h 329:( 326:g 323:= 320:) 317:x 314:( 311:) 308:h 302:g 299:( 296:= 293:) 290:x 287:( 284:f 256:3 252:x 248:= 245:h 237:1 234:+ 231:x 228:3 220:2 216:x 212:= 209:g 183:1 180:+ 175:3 171:x 167:3 159:6 155:x 151:= 148:f 73:h 69:g 65:h 61:g 47:h 41:g 28:f

Index

polynomial
functional composition
degree
functional decomposition
Algorithms
univariate polynomials
polynomial time
irreducible polynomials
factored into products of polynomials
composite number
monomial
ring operator symbol
function composition
Joseph Ritt
Horner's method
radicals
irreducible polynomials
computer algebra systems
quartic polynomials
quartic formula
simplify
Macsyma
Maxima
computer algebra system
characteristic
field


J.F. Ritt
doi

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.