{"entities":{"Q5928878":{"pageid":8105680,"ns":120,"title":"Item:Q5928878","lastrevid":47594692,"modified":"2026-01-02T04:19:56Z","type":"item","id":"Q5928878","labels":{"en":{"language":"en","value":"On the deterministic complexity of factoring polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1584481"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$3CBD3E82-DDE7-481B-B18C-56B2BF88DFED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dbefc17bda7320549c0536d490ab58e3887c3ed7","datavalue":{"value":{"text":"On the deterministic complexity of factoring polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5928878$323CB50B-A874-4B48-847A-71649860DEBE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c14612396997c7a62c7594d06dbcf09b2adfaa1a","datavalue":{"value":"0972.11113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$8A38A5E9-5B19-4EB5-8F44-7F87630A204B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"473924dcd4778a798405a0152ecde3a07d239d95","datavalue":{"value":{"entity-type":"item","numeric-id":165900,"id":"Q165900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$665E5A44-42F1-4F65-8000-5EBE776F3073","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$7E049BB0-93CD-4352-9538-E92676EF53A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28cf98d9fb3bd2ae0db9f209d5d7198a0716e98a","datavalue":{"value":{"time":"+2001-11-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5928878$41F6BCD3-02B5-4D83-8AE3-40E90D85398E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1e31fc786c3dcfc4fd9c16ec41344b755f257b39","datavalue":{"value":"https://semanticscholar.org/paper/2873bbbac8f9ba31fa81b8d74cedf797692f437e","type":"string"},"datatype":"url"},"type":"statement","id":"Q5928878$8A66E7FD-E375-4C31-B1B8-79FFFFEAF354","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b0d10f80c56ae265dccb983133a7c808a75a7b07","datavalue":{"value":"The problem considered is factoring polynomials over finite fields. In 1970 Berlekamp published an algorithm solving this problem in probabilistic polynomial time. It is still an open question whether there exists a deterministic polynomial time algorithm, even under the extended Riemann hypothesis (ERH). Since 1992, several authors have given, under ERH, efficient algorithms for special classes of polynomials or for polynomials over special fields. This paper continues this line of research for deterministic polynomial time algorithms under GRH. The paper contains such a result which applies to polynomials which do not satisfy a very stringent condition. The other one conjectures that the class of polynomials satisfying this condition is empty.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928878$9FC62B6C-6D14-4CDE-844A-98394D9C3A1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7b37a6de3a76a2f46603d2a1e14f19e4a44922ce","datavalue":{"value":{"entity-type":"item","numeric-id":168882,"id":"Q168882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$03AF4BFB-5C10-49D8-B279-1BB47D2BAB4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$AA7C8782-DB62-4DC9-ACFE-5E645893F52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$E9BBCB77-590E-429D-A19B-AC5CBAB13CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$ADD56BB4-1C62-48BA-8958-0A93D95F3461","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c93870d476d512aee5a40da9029ebabb9cefbae","datavalue":{"value":"1584481","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$DBB07B86-42CB-41E1-B815-46A3F36F2570","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2da93c39af03caab375da15c75b6c27fee60f16","datavalue":{"value":"factorization of polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928878$A0E296F1-5499-4FE8-8269-D27D346C4DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928878$0E8FCFC6-4C68-450E-843F-5F405D5F9C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1137c0a4aa2706c40a25da9a00d973ee23bc7e5c","datavalue":{"value":"extended Riemann hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928878$A22F4E68-5854-445E-A8E5-0641ECE4B9AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc96701316860fa5048999d77020f19011092cd","datavalue":{"value":"deterministic polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5928878$735AD9A8-6322-4635-839E-E58984299BC7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$A69E1E68-5416-4BEE-AEAD-2CB67D7C42F9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0c7d6d5e801f155e351fd782b070bed52eec2c1","datavalue":{"value":"W2027160923","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$C083C36F-B3DA-4FCC-B050-CA294CFEFFD7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b776ac22a6133e5b0428c718bb6712a9b852aad","datavalue":{"value":{"entity-type":"item","numeric-id":4372647,"id":"Q4372647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$1CC6411D-879E-4795-B5A3-3EBB4BA32CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2644855b8a9e93ba498a3d6bd57ed1fe107ac4e8","datavalue":{"value":{"entity-type":"item","numeric-id":5927536,"id":"Q5927536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$AACC065F-B8D3-47B0-B431-13EE707BBC9D","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":"Q5928878$214E4596-A8B7-4967-BDA1-E024EFC4DA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ceef5307961d7894eb83c6ef5e3560792b4f1dd","datavalue":{"value":{"entity-type":"item","numeric-id":5659665,"id":"Q5659665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$62E51377-C83B-4050-B14C-E879888B76EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdb34ede96ba491c4d206935e342ed72dc70432a","datavalue":{"value":{"entity-type":"item","numeric-id":3672093,"id":"Q3672093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$4F4A1A1D-9C1C-4519-8ABE-E277B4AAFBCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36b8a9af0084b722fa34e3af91b53abf56d68ae1","datavalue":{"value":{"entity-type":"item","numeric-id":3481814,"id":"Q3481814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$53B597D6-1018-46CA-9E6B-17136A00957E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1de521fe8e141732c57eae676569db95f3a5648","datavalue":{"value":{"entity-type":"item","numeric-id":1339732,"id":"Q1339732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$F3E657C4-D720-44EF-99B9-2F05F61896BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7c59d5accaf5ec800fd0d40227e41c156420c19","datavalue":{"value":{"entity-type":"item","numeric-id":3356388,"id":"Q3356388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$8AB81F0B-FC94-45AE-BBDF-6C5F47CFCEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90510f4dee0b4cb63a1b6cecd2f7aa83f934cd29","datavalue":{"value":{"entity-type":"item","numeric-id":4396457,"id":"Q4396457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$36D5DF6F-BBD7-4075-954E-9290ECBBF57A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c1d53c21f29e35ff0acb8862d389f14894f939b","datavalue":{"value":{"entity-type":"item","numeric-id":3798759,"id":"Q3798759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$8044CBEB-8501-4B7A-8CF2-38B99A31DE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"086419c0a2151cf26d91db2a6d741fa6fd91058a","datavalue":{"value":{"entity-type":"item","numeric-id":4118736,"id":"Q4118736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$2C11ABAE-9152-4201-AD4A-E9485C6EE177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a62cdec956f493e0e23da573b7623b64aa5e4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4154061,"id":"Q4154061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$67AE2270-7E0F-423B-9ABA-3B43207CCA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce80bdcc0c449c37180a7d140ae7c7f8eabc6b9c","datavalue":{"value":{"entity-type":"item","numeric-id":3795755,"id":"Q3795755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$ED06BF8B-7374-452C-AC2C-31BA7180C863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e75f4e77460cab9b1685a643349b5b9d1adb8ab4","datavalue":{"value":{"entity-type":"item","numeric-id":909466,"id":"Q909466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$09723C9D-8949-42BD-BE4D-21B4EAE085DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76374bc9c5ac3c2e82893bb724a6920e4da782f8","datavalue":{"value":{"entity-type":"item","numeric-id":4018845,"id":"Q4018845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$E5E20F46-918A-4CF9-9BD5-FA8C73F449CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43d8915a2dc1427fb9a16b79103d5e30f2eef773","datavalue":{"value":{"entity-type":"item","numeric-id":1095971,"id":"Q1095971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$CDE3E3E4-5073-445C-91D0-6EC81A4BFAA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d535030ec08de6e93e11b397aea8164357a189d0","datavalue":{"value":{"entity-type":"item","numeric-id":2366168,"id":"Q2366168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$1C14FF4F-56B1-49E8-A417-50907C8A34FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"141c227ad9231b19e11bd8c4dfb758c0da98d961","datavalue":{"value":{"entity-type":"item","numeric-id":5525481,"id":"Q5525481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$D5D24F6A-69D7-4853-A9FE-91D9D51F3B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0341bb5c15b0333cfa2941de1db8dbf4a4eba2c4","datavalue":{"value":{"entity-type":"item","numeric-id":3286403,"id":"Q3286403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$FA026B51-8312-4473-A408-8570162DA3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d32d82223ca2b19279ffc7ed889f6e76935fee9","datavalue":{"value":{"entity-type":"item","numeric-id":2537316,"id":"Q2537316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5928878$E9A0F785-E28A-4661-91AE-6C069D1751F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"564fdc687b0867cee29919800f706ca091a69d53","datavalue":{"value":"10.1006/JSCO.1999.1001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5928878$4C03B131-A220-4BBF-9634-F026AAAA6ACD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6953514430162722363585ce72af545fb4734d9a","datavalue":{"value":{"entity-type":"item","numeric-id":1178194,"id":"Q1178194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d519a46e412c823ba21049babe6fb59a4ab65d65","datavalue":{"value":{"amount":"+0.8701040148735046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5928878$64989140-BF60-4814-BEF6-926A50D42FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2286df5522df5f3afadb82e86411855566b73e08","datavalue":{"value":{"entity-type":"item","numeric-id":4847930,"id":"Q4847930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02b41947e362e342c45065a322bda6780a76bf37","datavalue":{"value":{"amount":"+0.8665010333061218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5928878$667A474D-DB26-4FA5-9799-EA4FFA32AB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"683d8a1d165fc2d1216b9bfe732a7a22c4d2666e","datavalue":{"value":{"entity-type":"item","numeric-id":3795755,"id":"Q3795755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02b41947e362e342c45065a322bda6780a76bf37","datavalue":{"value":{"amount":"+0.8665010333061218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5928878$82135698-ACDF-4D99-BCFE-139754EE1F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"380b113faf962c888d73a8002a54a7a0ee424534","datavalue":{"value":{"entity-type":"item","numeric-id":3117221,"id":"Q3117221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6726864f58363cb5f0fbccc85fc4f8adb6114e05","datavalue":{"value":{"amount":"+0.8650872707366943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5928878$2C3E0ECD-B9F1-4C18-8D70-677CE8A9E1E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adee2d3e42bebe72e803cb88dc4ddedffe94a3e7","datavalue":{"value":{"entity-type":"item","numeric-id":911294,"id":"Q911294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bd0207838ab5c1237ef5c3b63f75d1f625a9142","datavalue":{"value":{"amount":"+0.8646765947341919","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5928878$29A82586-8FCB-44C5-9773-D417CDF54295","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5928878","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5928878"}}}}}