{"entities":{"Q7361085":{"pageid":31518794,"ns":120,"title":"Item:Q7361085","lastrevid":105362618,"modified":"2026-10-07T13:34:22Z","type":"item","id":"Q7361085","labels":{"en":{"language":"en","value":"Polynomial Factorization"}},"descriptions":{"en":{"language":"en","value":"AFP entry Polynomial_Factorization"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d8d7535c96bac8d4c52d540fcea4f52936270396","datavalue":{"value":"https://isa-afp.org/entries/Polynomial_Factorization.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361085$77158CDD-2CC4-48E2-90C9-9092E3E49D69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1af2a193c5682448650b640f6abcfebb3d52b60","datavalue":{"value":{"time":"+2016-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361085$A4731DF4-4271-402C-B054-6C3D98530E82","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361085$4F8E1D3A-F48D-4E46-A7EA-855262D8D5F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"4e646f16cde9cfa1c19d0771a8f74ba7e8c772f6","datavalue":{"value":"Akihisa Yamada","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361085$ABD5D375-DD93-40F4-9269-60B14CB1F46E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"831595f0184e491085b4ce535ce283fc90a6ff5f","datavalue":{"value":{"text":"Polynomial Factorization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361085$A934A8B6-41BD-42E5-9586-4F63A3D33425","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dba027f20e592c6bf534cd274a527247388f400d","datavalue":{"value":"Based on existing libraries for polynomial interpolation and matrices, we formalized several factorization algorithms for polynomials, including Kronecker's algorithm for integer polynomials, Yun's square-free factorization algorithm for field polynomials, and Berlekamp's algorithm for polynomials over finite fields. By combining the last one with Hensel's lifting, we derive an efficient factorization algorithm for the integer polynomials, which is then lifted for rational polynomials by mechanizing Gauss' lemma. Finally, we assembled a combined factorization algorithm for rational polynomials, which combines all the mentioned algorithms and additionally uses the explicit formula for roots of quadratic polynomials and a rational root test. As side products, we developed division algorithms for polynomials over integral domains, as well as primality-testing and prime-factorization algorithms for integers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361085$0C97D36D-E019-4B3E-A87D-3DECC9C276F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"31385ef3ca1eb53ed08bbfa48b8b91d2510acbaf","datavalue":{"value":{"entity-type":"item","numeric-id":4282674,"id":"Q4282674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$8BE19DA2-F770-4A68-88D2-ECDC320BAA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8ae2d2158e3c465c93233b4442630df5c29733e","datavalue":{"value":{"entity-type":"item","numeric-id":3522019,"id":"Q3522019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$A499710B-CDB8-4C41-9CD8-F71CE809A3E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f259479a384f8ecfe337d79512b22e03f359c6b3","datavalue":{"value":{"entity-type":"item","numeric-id":5550483,"id":"Q5550483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$2FC1E87D-CD53-4763-AB36-D6CD98ACFEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0aef60bd392ccfb5e82daa98f095917b33d1745","datavalue":{"value":{"entity-type":"item","numeric-id":3183545,"id":"Q3183545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$C27C5FCA-24FB-4A86-B4D9-93BB7BD597E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8140e4105e9a133f88717f08d7a9ce19bb1f9cab","datavalue":{"value":{"entity-type":"item","numeric-id":5277869,"id":"Q5277869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$BA22D26C-80A7-407B-A469-FDE8BAF92658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"094a19452f4a2cac731a8f91e8d3d9444cc1deea","datavalue":{"value":{"entity-type":"item","numeric-id":1491721,"id":"Q1491721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$1913BED7-53BB-4A96-A372-F04D12D359A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0ff209a8c00e6853b2c43b2e31810805788f0","datavalue":{"value":{"entity-type":"item","numeric-id":3935355,"id":"Q3935355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$80944A12-16B1-4B5D-A9BF-813EB0108D72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d53d3fc5ef0eaf03448b2958c7b38baf170d7b9b","datavalue":{"value":{"entity-type":"item","numeric-id":928655,"id":"Q928655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$0459173C-815E-4000-9571-2175C6ACD0E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73402f4152dc1b0c6384814fa1868f011d7bebc5","datavalue":{"value":{"entity-type":"item","numeric-id":3421016,"id":"Q3421016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$E69EF021-484D-4D83-B9C3-30A0269DCE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97132178938a086d46887cf71f3c6653c803319d","datavalue":{"value":{"entity-type":"item","numeric-id":3582701,"id":"Q3582701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$2D2162E9-CE02-40FB-B2C5-337105A4B4E6","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$C748A2C9-4C9E-4702-9E9D-F87066F04CB7","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"bb0293970cb12cb0c0b06315232bb60667277b31","datavalue":{"value":{"entity-type":"item","numeric-id":7361362,"id":"Q7361362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$58962D8B-423E-4B69-8241-E0C4EE2BB958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"472350d0e5dd5ba9def2e15a38c587b54d3979fa","datavalue":{"value":{"entity-type":"item","numeric-id":7361428,"id":"Q7361428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$59BA4206-7D01-4C45-9A5E-DA31805ED59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"c74fb85b93aed6b0154f37279158b02ac3d7c1fa","datavalue":{"value":{"entity-type":"item","numeric-id":7361519,"id":"Q7361519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$9CE22DB9-0EB5-4A35-A598-AAF22FF850D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"911ce259dbcadd322bcb1b83dc5bfce4b6c36b1b","datavalue":{"value":{"entity-type":"item","numeric-id":7361212,"id":"Q7361212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$A0954AA8-248C-4DAB-BA07-D2EF8BF29711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"1201acfd0ade107234c23996279076e377633ac8","datavalue":{"value":{"entity-type":"item","numeric-id":7361247,"id":"Q7361247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$1870CAB5-E36A-412C-9374-5972563C67E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"fe8e4266ccdb5bc1f08b1d6665bd026f17fde0ac","datavalue":{"value":{"entity-type":"item","numeric-id":7361683,"id":"Q7361683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$4070D96A-8F39-4FD0-9E1E-53248F962E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"c8b055357156b513ebffa05abff4ab0fc053c1d6","datavalue":{"value":{"entity-type":"item","numeric-id":7361662,"id":"Q7361662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$0D6E2ADD-D5E4-4AD0-ADFF-29FDAABE78C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"1bd8a170e1a91182d9c95c33fb53b59631080f47","datavalue":{"value":{"entity-type":"item","numeric-id":7361185,"id":"Q7361185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$F352AFDE-2CEB-42C3-B34B-41AD24581FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0efca7872f6f2bc29e0aa800862a00f25b835a0","datavalue":{"value":{"entity-type":"item","numeric-id":7361019,"id":"Q7361019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$79EB47CF-FAE1-4395-8AC9-ADC678434B01","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"65292b3c42fa1bd5c21e4c91fe94fdc3f630f232","datavalue":{"value":{"entity-type":"item","numeric-id":7360821,"id":"Q7360821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$AD05C562-DA04-463D-A00D-2FD770E4D4D3","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361085$C3B5F083-4822-4A90-85F4-DF5149333AD4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial Factorization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial_Factorization"}}}}}