{"entities":{"Q1165896":{"pageid":1176645,"ns":120,"title":"Item:Q1165896","lastrevid":48668203,"modified":"2026-01-05T13:43:01Z","type":"item","id":"Q1165896","labels":{"en":{"language":"en","value":"Factoring polynomials with rational coefficients"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3767793"}},"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":"Q1165896$DB67DEDA-3819-47CE-ADC3-539FAB36AE1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a9146f311499d8b7a11fad260d68f6497024f0b","datavalue":{"value":{"text":"Factoring polynomials with rational coefficients","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1165896$E56F9370-B3B1-44E5-AA43-BAF8450DC1C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a147b72b98d476978f86c0949026af617acc29a","datavalue":{"value":"0488.12001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$64FB7990-3551-441F-92F2-87B31F1137E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a24623e88e7371a25fd0f954ed47d0be52b9157f","datavalue":{"value":"10.1007/BF01457454","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$6D78AF34-4CD7-4E3D-AA91-E4AC49291DFB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"25be37ea5efbda6463bca40df3ad865f3565481f","datavalue":{"value":{"entity-type":"item","numeric-id":218818,"id":"Q218818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$C0A3651B-C60D-4D62-8900-5577D31C32BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e59e3014c42347e04009f2d7e82f52c134765490","datavalue":{"value":{"entity-type":"item","numeric-id":165880,"id":"Q165880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$F0B723B4-1926-4F56-9DEC-DBC28BC1C14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"201364cbbc61e0d0a85431778d2e1c2e76306b69","datavalue":{"value":{"entity-type":"item","numeric-id":6480584,"id":"Q6480584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$27630235-2A4F-40F2-B8C4-5BBD1A37CEBD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7016073dc3661ad2b8fcf740b72e135f31d59f23","datavalue":{"value":{"entity-type":"item","numeric-id":166142,"id":"Q166142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$F3157EFE-C308-4170-A9B3-77706A43CA38","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47f57cd36df9e30d446df3867dc3917e4ea74654","datavalue":{"value":{"time":"+1982-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":"Q1165896$5C28B1F7-CDE0-46D5-99EA-8A45F2D38C8F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6021cb5e83ee7789d0d2f6b40e32d1c4e8b65e2","datavalue":{"value":"https://eudml.org/doc/182903","type":"string"},"datatype":"url"},"type":"statement","id":"Q1165896$505CE1F2-3DDD-46AC-9DD7-562B0F3440AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"53f337d077093aef37d0c91aee10216f56c0623e","datavalue":{"value":"This paper describes a polynomial-time algorithm for the factorization of primitive polynomials \\(f\\in \\mathbb Z[X]\\) into irreducible factors. The number of bit operations used by the algorithm is \\(O(n^{12} + n^9(\\log \\vert f\\vert)^3)\\), where \\(n\\) is the degree of \\(f\\) and \\(\\vert \\sum_i a_iX^i \\vert = (\\sum_i a_i^2)^{1/2})\\). The result can be generalized to algebraic number fields and to polynomials in several variables.   One of the main ingredients of the algorithm is a new basis reduction algorithm for lattices in \\(n\\)-dimensional space. This basis reduction algorithm can be used to find short vectors in an \\(n\\)-dimensional lattice. The paper briefly mentions two applications of this algorithm in diophantine approximation. It is also of importance for problems from operations research and cryptography.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$3192981C-FA7C-400B-B36F-B5A6A7FEFF60","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$FFBDAC96-C745-491B-BB73-5A040497235E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c87799adec94bf8b9b9eb5f19b936a1d5c6fca89","datavalue":{"value":"11C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$D4118BE6-38E7-4965-8E51-EFA4D9F03585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"75b5ae7d63c4b2ff3513743a5ea9e7be306e24ac","datavalue":{"value":"11R09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$7C0511E3-A735-4A8A-AEF7-9F377137CC70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$F82EA4EA-B0C9-4061-93D4-A8FB7FAF448C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83570ee3416602dc57635cc1b54323496cc5f450","datavalue":{"value":"3767793","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$9C76F1F0-D802-4999-92E5-4B77B688DE5F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$4082B33F-C29C-4FAE-BF2B-86F3EF7FA35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d3b69a5f4079b1c9e9cfdbe3ef2fa188d4aab73","datavalue":{"value":"factorization of primitive polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$4DCD7731-599E-471B-8236-795EC9B5832B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b683b480998b044680674a0f726898987efc4240","datavalue":{"value":"lattice basis reduction algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$57C1E1D4-05FE-4E5B-A142-E91EBD8AD578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90894f185013e534f70e51d039e89d83fea5b590","datavalue":{"value":"diophantine approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$E5E1B5FD-8429-471A-B144-018CDEB77966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ddc2790f83291413186a9651d6c4959058d194f","datavalue":{"value":"operations research","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$32C63F6A-9394-4949-AB04-FE4DE6E3DE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q1165896$A5D4C253-8951-4AD6-8D93-BCE13ABB2E44","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b643d8440202cd29c69cc03495866173d9a2aa32","datavalue":{"value":"Q56210589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1165896$FB69887C-4F9A-41C7-9E96-DC22C494E091","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":"Q1165896$4456C697-BAC7-4F97-999D-6BC26C8F78D4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90bfb6c6164c5120cdd0eec16c35b1f786043c43","datavalue":{"value":{"entity-type":"item","numeric-id":3924277,"id":"Q3924277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$E2BB7C34-BCE3-46C7-8EE0-05370B47E350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1507a4cbf5a5392202184c17995350ae1a2012d1","datavalue":{"value":{"entity-type":"item","numeric-id":3951538,"id":"Q3951538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$DD7F71D4-C050-4134-8A85-F1B3AB6B622A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f7e2e97c20d2abc0f9a209eb0226efbd5e45b6d","datavalue":{"value":{"entity-type":"item","numeric-id":5611106,"id":"Q5611106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$C767B40C-2518-42B6-B29A-1BB81EC5D809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93080d2e540eef438e3a51aef1c5dd914667ecd8","datavalue":{"value":{"entity-type":"item","numeric-id":3858342,"id":"Q3858342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$C60011D0-46F5-4B8A-A057-3C04D1CD5C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e28d865b6a527d6aef184a58e15bb15ad21dc2c","datavalue":{"value":{"entity-type":"item","numeric-id":3856819,"id":"Q3856819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$E614626E-964F-44BD-9936-4A3277026B38","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":"Q1165896$9F976E03-F7D9-4375-9664-0D1157293899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf96303896341f3f8dc9b3d4f453001ba32bbee2","datavalue":{"value":{"entity-type":"item","numeric-id":3932892,"id":"Q3932892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$0946F9CD-991E-42B6-8394-ED56F8F2F509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b7afcb9a0497959937cf113b16fb13499994cb9","datavalue":{"value":{"entity-type":"item","numeric-id":4053736,"id":"Q4053736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$2746E75E-5050-44A1-B713-7C4735FFF701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46ccba14837ab6c5bc350f0628d92fafda2a68c8","datavalue":{"value":{"entity-type":"item","numeric-id":3902523,"id":"Q3902523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$699045F4-C14F-4F4C-AADE-238C2E0C05B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a88e7c87651eeb3ff2433bf71733b763895cdc","datavalue":{"value":{"entity-type":"item","numeric-id":2626710,"id":"Q2626710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$17C89558-227F-4824-A795-F44E948519B9","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":"Q1165896$DBE5CA39-BC27-48EF-86A4-84047F919497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1d85f16e1af97ef9a7d410ae26787313d3c2190","datavalue":{"value":{"entity-type":"item","numeric-id":4163606,"id":"Q4163606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1165896$18E2FC3B-64C0-428A-8931-E6A6DFFD1D0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aff64447deac0e0f022ca58ad381f03e1c435711","datavalue":{"value":{"entity-type":"item","numeric-id":3327715,"id":"Q3327715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3270d709d2c88d6673714852ba0be60033c46a1","datavalue":{"value":{"amount":"+0.9058107137680054","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":"Q1165896$CD689E2A-B71C-44A0-B19A-D507268C7B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48a6fb804286ec3e599776e12f8662b3926e3311","datavalue":{"value":{"entity-type":"item","numeric-id":3326837,"id":"Q3326837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f80ad7be6f0430aa8e8bbd7720d12cb912eb14de","datavalue":{"value":{"amount":"+0.8986465334892273","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":"Q1165896$12D4E07E-3C30-4480-9590-EE67E66CBFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db9e5fac2ebc578f37dc4f073bc765f928b3ab8e","datavalue":{"value":{"entity-type":"item","numeric-id":3686034,"id":"Q3686034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2981af39a03084f61f94fcf8c405038bb16bec68","datavalue":{"value":{"amount":"+0.8967457413673401","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":"Q1165896$5D021C1D-1554-470D-8CE1-015B11787CAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58abd8e6dadd9a04f2a0f35a00cb2f793a0124db","datavalue":{"value":{"entity-type":"item","numeric-id":3684200,"id":"Q3684200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11d65b685b521237c1304b946d7dc559465e331d","datavalue":{"value":{"amount":"+0.8915921449661255","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":"Q1165896$350BA1B5-2FC8-4DD7-98F8-23BD18CAF2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd0fb95cf327e61b87623d87cdea12c86c8db3c","datavalue":{"value":{"entity-type":"item","numeric-id":1065867,"id":"Q1065867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abafa2be717b6f8082fe2b947ab4e719d02dd0bf","datavalue":{"value":{"amount":"+0.8772946000099182","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":"Q1165896$3FD135F5-B487-47AB-A582-626644140B1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1165896","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1165896"}}}}}