{"entities":{"Q1080657":{"pageid":1091409,"ns":120,"title":"Item:Q1080657","lastrevid":48971410,"modified":"2026-01-06T09:00:10Z","type":"item","id":"Q1080657","labels":{"en":{"language":"en","value":"Fast parallel absolute irreducibility testing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3967913"}},"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":"Q1080657$D100DE3A-BCF6-4688-A00A-91035222F6DD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"284e20b910fcfdd020ed28a93e1d96e72b99497a","datavalue":{"value":{"text":"Fast parallel absolute irreducibility testing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080657$814706EC-AC55-45E7-A94F-D15FE85AF68C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d9af999023f569d7c75478d5c503bccfb03713ec","datavalue":{"value":"0599.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$9F2C162B-E761-4DAA-AABF-DD17EDE8086E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4caf23bd782299b4561c21447789239e03c14244","datavalue":{"value":"10.1016/S0747-7171(85)80029-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$4A862965-EE02-4CCC-B7DB-414C85C6B0B0","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":"Q1080657$6A3E00EC-E453-41CB-92F3-3D1E59254228","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1080657$6446E6CA-A233-462A-92C5-50433476DC94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"038d2c92270b832ff5c2755882b08e9a9f65e47f","datavalue":{"value":"We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coefficients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial's irreducibility closure of the finite field of order p is not preserved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$1FD3D11F-28F0-49BD-BC26-E01F8BC88B72","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$CA9C6EDD-19F2-4786-9E84-B73ED0A613CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$0DBB9E52-A099-496D-A749-61544BA27225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$212A5E2E-B846-4D72-850D-BA9C2E7DCDEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"352295d1160dbd33b62ff206ba20a986dbd58c1b","datavalue":{"value":"12D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$9631194F-90B7-4FDC-8961-215039AE0385","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4eb421ee60761602f065b23080bf93a64c5126df","datavalue":{"value":"3967913","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080657$B32F02FD-C359-4C02-AEA2-9C608717BB5D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2394caa1af48a722a94d755ad4ba95a18105042","datavalue":{"value":"fast parallel deterministic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$100DF2AC-8B95-4EBE-987C-0C97052B7060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6205934d4379923caa5bc41ea462fae81d40b22c","datavalue":{"value":"testing multivariate integral polynomials for absolute irreducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$9BC94C8C-004A-469B-B2BC-A9EEBDBC2A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25ad97a641d30b87cb9828f3f321c3756192b7b3","datavalue":{"value":"complexity class NC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$00E76C3A-D18A-4044-866A-EF8EC37D49B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"793980207209e125a0c57c6e5d442d9fefc3e091","datavalue":{"value":"sequentially polynomial-time problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$4D701E69-2E1A-489B-800B-26B8D6408B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080657$E8B283AF-6037-44BC-B574-F069689B33D3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b8fab2835aa67de048549fe321076187d6937ac4","datavalue":{"value":{"entity-type":"item","numeric-id":412212,"id":"Q412212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$F2E35578-E102-4923-BF36-C94E222FBA5C","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":"Q1080657$0FC0C96A-6F1F-4A7C-9478-6F80F61A8BFC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$2DC0F133-6DF4-4F2B-86F6-60E2D76C9345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb5037acc3949cbca8f8e77ab83b58c3f57e4b13","datavalue":{"value":{"entity-type":"item","numeric-id":3732965,"id":"Q3732965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$CAEC1BA5-5B0C-4E52-847C-0E2EEBD6EE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a006907d50546bdc051c28c96b89ad928a5269a5","datavalue":{"value":{"entity-type":"item","numeric-id":1158753,"id":"Q1158753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$642FD569-DB2B-416F-9248-80F382D41F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33276d0641cdf33da6148533199de09db3b8a390","datavalue":{"value":{"entity-type":"item","numeric-id":3939229,"id":"Q3939229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$F2E1873B-AE65-471E-8551-2B19C41B8306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78b1248cd93ca1ae4c05b1a736044eefb5495f42","datavalue":{"value":{"entity-type":"item","numeric-id":3346430,"id":"Q3346430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$8B8F9508-C107-4E11-AC37-6BF37CB783DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d26a6f91cad09aedfac2542737473fd6604555b7","datavalue":{"value":{"entity-type":"item","numeric-id":3041304,"id":"Q3041304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$82BB2F6A-34B8-4FDF-9F22-0B46868C2ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2446a7a37330f31d0fe1f5a3d2929d51c5096db","datavalue":{"value":{"entity-type":"item","numeric-id":3912021,"id":"Q3912021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$06DC6919-E81C-49F8-8CFD-2F5FF61F0FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2359bbf72928d5a5d4373ebacb8db66a5e2a235","datavalue":{"value":{"entity-type":"item","numeric-id":3743372,"id":"Q3743372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$4FF61F92-E4DF-4BCE-902C-03795BFABA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e7fb03ceb8a0fcf13a76525214a9274d728818b","datavalue":{"value":{"entity-type":"item","numeric-id":3708879,"id":"Q3708879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$C0F38958-FEE2-42CD-8370-FFD80AB52189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$D3B02CDD-4F84-4376-ABCD-C8D4E2A06F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95345f69dfeae4be53e3f6612576bcc12e7cba27","datavalue":{"value":{"entity-type":"item","numeric-id":3919787,"id":"Q3919787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$654DB8A4-F951-414E-8201-7FF84BEC88F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c433cbc0bb084950ec8a2870c1d6dfbdbf28c5","datavalue":{"value":{"entity-type":"item","numeric-id":3697106,"id":"Q3697106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$74FBC06D-F485-481A-B1A2-3E3F6CE1C397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a744c9c17719923d1a192e9214086e46257ed20d","datavalue":{"value":{"entity-type":"item","numeric-id":1227023,"id":"Q1227023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080657$13145E75-765B-4146-8028-2D37B05AC37A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b26a26ed5f827cd3921b32e15b1107a009b07f00","datavalue":{"value":{"entity-type":"item","numeric-id":1009361,"id":"Q1009361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb0e3cd2a299f74e14ee120bb10074f4565b0766","datavalue":{"value":{"amount":"+0.8899460434913635","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":"Q1080657$188383B5-9B20-4CB8-A0EB-FA8DAE6C4D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfbcf366ada11978f3447a214530bea98191ddb2","datavalue":{"value":{"entity-type":"item","numeric-id":1612137,"id":"Q1612137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0518ad32cf7cb22526fede5de5463e1f29f9cf9","datavalue":{"value":{"amount":"+0.8801195025444031","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":"Q1080657$1A270C01-FA61-4F75-B99D-50144BB2D25A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"532a24cc5830530e02bc7af5c36144c1eb45980a","datavalue":{"value":{"entity-type":"item","numeric-id":1083191,"id":"Q1083191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd66c808d51c5d03eac6e562572d3fe41c002f27","datavalue":{"value":{"amount":"+0.8493640422821045","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":"Q1080657$C0FD332F-BBD0-4F02-807F-F0C231A99C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e77fbee1b8f4a4be7b8e8d3e49f7dba6cb371a1a","datavalue":{"value":{"entity-type":"item","numeric-id":1892221,"id":"Q1892221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f4ebef213a1f1ac8c452e48d3350830c0acea1b","datavalue":{"value":{"amount":"+0.8367610573768616","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":"Q1080657$803CBAE3-F3C4-41F6-9669-736BBDD97C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35f9162b86e088830ba788c10c6466ee3a5772f5","datavalue":{"value":{"entity-type":"item","numeric-id":607052,"id":"Q607052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fd388130062481ce4340c2d30286b46e3ab53c8","datavalue":{"value":{"amount":"+0.8366352915763855","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":"Q1080657$F851245E-613C-40DB-929E-C9AE10C6BD36","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1080657","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1080657"}}}}}