{"entities":{"Q1323866":{"pageid":1334616,"ns":120,"title":"Item:Q1323866","lastrevid":70139253,"modified":"2026-04-13T12:42:34Z","type":"item","id":"Q1323866","labels":{"en":{"language":"en","value":"Deterministic analysis of aleatoric methods of polynomial factorization over finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 584043"}},"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":"Q1323866$720ADFBC-FF23-4D0D-BCA3-095B2205794D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bee70607d0a640784009a7134d334b5888ba619f","datavalue":{"value":{"text":"Deterministic analysis of aleatoric methods of polynomial factorization over finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323866$76A543EE-C156-4C7D-9A22-1B9D555AF12A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e410447bd2d26e281cc79342198be8990b8ee96","datavalue":{"value":"0802.11055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$DCD33C28-F2A1-4550-83FD-DFF73BFF662D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1176f05d697e9112b9b5a26588c6b8438a45e417","datavalue":{"value":{"entity-type":"item","numeric-id":1323865,"id":"Q1323865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323866$75FE775F-6DF3-407C-A744-EA7C6DDD1041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de0319dec6c25a1b772817937787b56aaa7c3d22","datavalue":{"value":{"entity-type":"item","numeric-id":1234348,"id":"Q1234348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323866$62A85E9A-3256-4FED-BB47-426834B70416","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e6cac328d206d9ef9b7afb3fb4ca5d1d204199af","datavalue":{"value":{"entity-type":"item","numeric-id":167107,"id":"Q167107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323866$B79724BD-427C-4058-BD5D-07546CCBFD3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"198e1cf6b5241864422b78fe5a16d94ea3d08eab","datavalue":{"value":{"time":"+1994-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323866$7290A165-D075-4ECD-8ED8-0E37EC807053","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85ff4b5591459460cb94f14e28d5918880e8aa50","datavalue":{"value":"This paper deals with the problem of factoring a monic polynomial \\(f\\) over a finite field \\(GF(q)\\) into a product of irreducible monic polynomials over \\(GF(q)\\). By either the method of \\textit{E. R. Berlekamp} [Factoring polynomials over large finite fields, Math. Comput. 24 (1970), 713-735 (1971; Zbl 0247.12014)] or the method of \\textit{D. G. Cantor} and \\textit{H. Zassenhaus} [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)] this problem is reduced to the problem of finding the roots of a polynomial for which it is known that the polynomial is a product of distinct linear factors over \\(GF(q)\\). Thus without loss of generality it may be assumed that \\(f= \\prod_{i=1}^ n (t-\\xi_ i)\\), where \\(\\xi_ 1, \\xi_ 2, \\dots, \\xi_ n\\) are distinct nonzero elements of \\(GF(q)\\).   The methods of Berlekamp and Cantor-Zassenhaus are both probabilistic methods. In the paper under review the authors propose a deterministic version of the Cantor-Zassenhaus algorithm. It is conjectured that this algorithm has complexity \\(O(n^ 4 \\log p)\\), where \\(n= \\text{degree} (f)\\) and \\(p\\) is the characteristic of \\(GF(q)\\). A combinatorial problem is formulated whose solution would imply the truth of this conjecture. The authors also present a new deterministic factorization algorithm that requires knowledge of a primitive root of \\(GF(q)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$8B359F13-D6AB-45E0-846A-57912D9774D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$CE05480E-73A8-4457-A8E3-D7488926A49C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$9557B441-78FE-40A3-B11D-F7D679361B33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1a055a505ad704f957ada3e75c4008753677289","datavalue":{"value":"584043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$1544D5F6-5B76-4568-BACB-97FA064161B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$F7DADD9A-675E-4D9A-AF9C-CB1348D877CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bea6f9167a8923f2618e0a44c353d919e1654e76","datavalue":{"value":"monic polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$A30903E6-0645-481B-979A-2241616DA26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5840ad880caf904702db8914e21510ceb27ba20","datavalue":{"value":"Cantor-Zassenhaus algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$896B2BD3-D138-4172-80B4-8693885D6B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$C762D86F-28AB-4F3A-AC19-9BE70A4F38EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87503bbc1a65ae1e32c070fa1401d7d9d4c61bab","datavalue":{"value":"deterministic factorization algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323866$87F4A735-8BCF-4F97-9E66-2E8A9D32C91C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1f7e1a277c07b3a6d4f148b99c27222344cbe448","datavalue":{"value":{"entity-type":"item","numeric-id":222524,"id":"Q222524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323866$6B0940DA-FB19-40A6-96ED-D22715B6A6D1","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":"Q1323866$67B07F18-37F9-4B76-8723-76C9E33C47B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd22f54e88dab9706cb8f76868315fa34a27b0c8","datavalue":{"value":"https://doi.org/10.1006/jnth.1994.1024","type":"string"},"datatype":"url"},"type":"statement","id":"Q1323866$E60CE0AB-4CEE-4A35-BC5F-341B2E4A2DC7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f9eeced5dd314adbba16c1cba163aa88ed14a10","datavalue":{"value":"W1983297160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$0A1A41F4-69C9-48AA-B09A-3FBE317B8F8B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15b6f5e3655d5fd1736f1becfc3c01338d603cc5","datavalue":{"value":"10.1006/JNTH.1994.1024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323866$52C7722C-0382-4420-A32B-D4DF39AD2704","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53625d0eebb5e8236376485cd22d90d39849a3ba","datavalue":{"value":{"entity-type":"item","numeric-id":4325734,"id":"Q4325734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12c9a960909210fcc0c122a3f84e8dc9bd5dcb99","datavalue":{"value":{"amount":"+0.8569883704185486","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":"Q1323866$E9B25931-5A8B-479C-81C3-4B63FAAD0FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b22422e3c22972c4ba0963db5868465079487633","datavalue":{"value":{"entity-type":"item","numeric-id":5928878,"id":"Q5928878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b43ac52cd1cea0f21292ec837373004bfbbbbefe","datavalue":{"value":{"amount":"+0.8558462262153625","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":"Q1323866$49153B5B-C56E-4C98-B81E-661356A4A79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc83329493a5b7c7c0529c64d8a051f16be44695","datavalue":{"value":{"entity-type":"item","numeric-id":1575686,"id":"Q1575686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2462832d7d8e111121d495bb9df1c5c8845fa8d7","datavalue":{"value":{"amount":"+0.842457115650177","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":"Q1323866$205F232C-DF26-42B7-8953-F67D61A511F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a9a7132f96f3049818fadafb17d6b2bed0e4bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3345783,"id":"Q3345783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2462832d7d8e111121d495bb9df1c5c8845fa8d7","datavalue":{"value":{"amount":"+0.842457115650177","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":"Q1323866$0045B75D-2FA3-4C4C-946D-C27261A2A563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"678888d34d8d4411bb3a8a9edbbafd342260f375","datavalue":{"value":{"entity-type":"item","numeric-id":2366168,"id":"Q2366168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"860fd7840401233e132a0c549747b256d7b63ec7","datavalue":{"value":{"amount":"+0.8340945243835449","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":"Q1323866$F4DE3A6B-2055-470E-8C84-CF21382E8C4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deterministic analysis of aleatoric methods of polynomial factorization over finite fields","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deterministic_analysis_of_aleatoric_methods_of_polynomial_factorization_over_finite_fields"}}}}}