{"entities":{"Q7361900":{"pageid":31521239,"ns":120,"title":"Item:Q7361900","lastrevid":105423971,"modified":"2026-10-08T13:45:55Z","type":"item","id":"Q7361900","labels":{"en":{"language":"en","value":"A verified factorization algorithm for integer polynomials with polynomial complexity"}},"descriptions":{"en":{"language":"en","value":"AFP entry LLL_Factorization"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0515825eb25a492b0aee38475de5604ea8a7cec5","datavalue":{"value":"https://isa-afp.org/entries/LLL_Factorization.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361900$33E50DE4-0712-4E65-9081-8D030FDF51C1","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3ac7196df7cfbb13ec1a00e4eadbe8c75213209e","datavalue":{"value":"Jose Divas\u00f3n","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361900$F63DEE6D-C07D-421C-BDB9-A7BB0050D997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"68caf737a72c94bcb2627452f3944631c5b3bfaa","datavalue":{"value":"Sebastiaan J. C. Joosten","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361900$DD1EC692-97E3-4916-9480-D6F62D7D7D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361900$D4CE3241-53DC-4EFE-A14B-5ECED93B7209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"4e646f16cde9cfa1c19d0771a8f74ba7e8c772f6","datavalue":{"value":"Akihisa Yamada","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361900$97CD5634-18C7-4EF9-9089-52C99680516A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43d8e2f0b64eea27a39671878bbb74e93d76efeb","datavalue":{"value":"Short vectors in lattices and factors of integer polynomials are related. Each factor of an integer polynomial belongs to a certain lattice. When factoring polynomials, the condition that we are looking for an irreducible polynomial means that we must look for a small element in a lattice, which can be done by a basis reduction algorithm. In this development we formalize this connection and thereby one main application of the LLL basis reduction algorithm: an algorithm to factor square-free integer polynomials which runs in polynomial time. The work is based on our previous Berlekamp\u2013Zassenhaus development, where the exponential reconstruction phase has been replaced by the polynomial-time basis reduction algorithm. Thanks to this formalization we found a serious flaw in a textbook.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361900$BACB7147-45F8-496B-B3D8-DB971E4E39DB","rank":"normal"}],"P223":[{"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":"Q7361900$B33632F8-F04F-4911-B7D5-84E69A696E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0543f1e8c81032cff0b481c190929fef1b006bd","datavalue":{"value":{"entity-type":"item","numeric-id":4406533,"id":"Q4406533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$C9F12559-1A1F-4285-8AA1-1C679D95528E","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"6b0c8751e5c0af23677c31da7dad8b06ad87cc15","datavalue":{"value":{"entity-type":"item","numeric-id":7361415,"id":"Q7361415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$3305BE0A-7B8B-4237-8C55-784BAF2AFEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0aa50f079ce55914d2017210f388754913ab11f","datavalue":{"value":{"entity-type":"item","numeric-id":7361200,"id":"Q7361200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$88B761E0-0761-4609-9FE6-8FC0DD72061E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a56c33c49680ed15bf9438494fe87a6286c086fc","datavalue":{"value":{"time":"+2018-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361900$1B0300E2-61B2-4EAF-A3C4-42977BB82236","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ddf8ee6eca8ea3c4c3fdb31f3a4bc6d397d91cd8","datavalue":{"value":{"text":"A verified factorization algorithm for integer polynomials with polynomial complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361900$5FC838D0-A632-4CFE-9154-2ED479D5DB7E","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":"Q7361900$57770026-9768-435F-97E2-EC7687E081ED","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":"Q7361900$0A798F08-2B50-4AF1-8348-2535C9905BD3","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":"Q7361900$E65C4689-051E-4B7C-B2DD-2AFDE0F5EC09","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"c1493983999acd74423988a4c1b27558efb37407","datavalue":{"value":"28660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361900$57294E77-CCA4-485A-8553-3EC4BD5451FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd3cd3c8cd085ac2048034c2279872658062342d","datavalue":{"value":"11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361900$D9E5BF01-D8F9-4411-8778-C6B1C62D43FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f5e0c6033338f59ef27e37d6877da0f26d9646","datavalue":{"value":"68.0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361900$866CB040-622A-4492-9C51-91ACEC94379D","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$530A925C-2A0C-4D38-B0B3-372695982F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$448FF7DF-3BDE-486A-9846-DADD5A75FB73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ed15eb8701a335444fde1bcc3327d1067ce64751","datavalue":{"value":{"entity-type":"item","numeric-id":24376,"id":"Q24376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$B748E53C-F96A-4628-9261-21BA4391657B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7d1a8519018039436924ad678b461ed447b5bd71","datavalue":{"value":{"entity-type":"item","numeric-id":40310,"id":"Q40310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$673191D1-CEB9-4185-B162-73DD0322B8C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"83a7c52533a2a0c00f328cde038f2bdb12749a41","datavalue":{"value":{"entity-type":"item","numeric-id":40375,"id":"Q40375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$6ECE6239-89C5-479D-A976-A2BCD49AF833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$1D5CF05D-234B-49AB-B537-512C1416421A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$063EBB18-BA10-4CE8-BEC6-F3D209A14529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"244ebbac6461f60bed6d50e50ce8194b0e233968","datavalue":{"value":{"entity-type":"item","numeric-id":40296,"id":"Q40296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$989642AB-F132-41CC-92FD-86B80EE54CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"1a02d239e8e5fb50db504a225f64b24632e538b0","datavalue":{"value":{"entity-type":"item","numeric-id":52554,"id":"Q52554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$E4DEFFF3-D0AB-4019-9414-547300BE31B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ea5413756061bf33eb1bd266ba2a93f8c7b394c6","datavalue":{"value":{"entity-type":"item","numeric-id":5973088,"id":"Q5973088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$806D5036-2A7F-495D-A139-2B189305AE2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"eba8b47e1a803cab7d21f0226e3c8085963466de","datavalue":{"value":{"entity-type":"item","numeric-id":5975135,"id":"Q5975135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$DD77AC26-B21C-465C-B8ED-2036CAB49942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a3f9d192df50f24767772f5b218635cb7747b820","datavalue":{"value":{"entity-type":"item","numeric-id":21717,"id":"Q21717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$B67E4DE4-8CFE-4FDB-8E1C-41EC407C06A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"331995fe532c23e24d72d01a1bd6245fafcd9671","datavalue":{"value":{"entity-type":"item","numeric-id":19106,"id":"Q19106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$5B4340D7-2C90-454E-B4BD-2A81D5069651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"868d665ea0607bf8bd28ea3e3872eb2ea87bd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":40371,"id":"Q40371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$B4F06FCB-446A-4A64-8EEE-913F4A5D0DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"61d0c0612cc30c9c51b93ddaf1f78ee1ae75f9fe","datavalue":{"value":{"entity-type":"item","numeric-id":18676,"id":"Q18676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$2EDC138F-9E71-4CE7-8754-DCBC1B6CE6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"9eb436930ab1f6d235b354c651322b547341064b","datavalue":{"value":{"entity-type":"item","numeric-id":13309,"id":"Q13309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$B5F86DC7-9224-4923-89C8-03E3F45A2BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$69190E59-8D9A-4D41-BB12-94F3E753237D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"c7cf914fa2ed02c8c123a4c265842a9ab4be0800","datavalue":{"value":{"entity-type":"item","numeric-id":25403,"id":"Q25403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361900$82983600-DB6F-45AB-B3BA-D16414ACFA87","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A verified factorization algorithm for integer polynomials with polynomial complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_verified_factorization_algorithm_for_integer_polynomials_with_polynomial_complexity"}}}}}