{"entities":{"Q412202":{"pageid":413969,"ns":120,"title":"Item:Q412202","lastrevid":61658478,"modified":"2026-04-11T00:46:47Z","type":"item","id":"Q412202","labels":{"en":{"language":"en","value":"Non-linear polynomial selection for the number field sieve"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6030304"}},"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":"Q412202$9BB24EE7-44EE-4152-A5EA-806A6B3DC4CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1f417bc1bdaf32adf252623bc3d2239309df092c","datavalue":{"value":{"text":"Non-linear polynomial selection for the number field sieve","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q412202$E05FC400-3F58-4F9F-9CE4-35F410FBD300","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5053a19af2cf60c1f7181ebcfb476d26646b0b9d","datavalue":{"value":"1278.11107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$AE8D454F-B6F9-453B-AD52-D02FB0C0246A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e332602c62f3511a5261e0ca1092e3fb59b38bb3","datavalue":{"value":{"entity-type":"item","numeric-id":412200,"id":"Q412200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$117434F3-A69B-431B-826A-AC398B65CC09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"582ff81aaf243b59ee8142b6af1822c87468b245","datavalue":{"value":{"entity-type":"item","numeric-id":412201,"id":"Q412201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$98856061-BC80-4734-B89D-8E5BA5E58F98","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":"Q412202$18FD09C6-486D-45D7-956E-73587E170301","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8d0f2e18c1df897dbb15de5492927d1ae63c4ec2","datavalue":{"value":{"time":"+2012-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q412202$F162314D-16FA-4FFC-BF9A-64DF8A589FC1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$6A02B555-1802-4B66-90DA-B750227A0922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$72C38040-47CE-4674-BDA8-55F53B4E9D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$8CB7DAC8-40EF-4BEE-ACF6-E459DA469109","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e98ba042dce20291b348d4456ebf3e113da4f112","datavalue":{"value":"6030304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$3E21D5CA-A9AF-428E-BD82-183A9871E8D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fee303a20941ce1bcb80f32aa2b5199af39f9600","datavalue":{"value":"integer factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q412202$7EEC877F-CF94-4362-928F-DAF9D54BE928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d92933569277d10edac01435fc2574cbf9ecacc","datavalue":{"value":"number field sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q412202$D411E557-C112-494B-9BFF-ECF5D27F0180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971d25706c332803bde4bc7afcefde2deb20bd9e","datavalue":{"value":"polynomial selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q412202$E307BA1C-5F36-449D-9FA0-5BF73E86A827","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$30CAF725-1617-48D1-89DC-BC382AC6DC1A","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":"Q412202$F7ED2D87-60B0-4DF4-B527-7E629ADA9F4E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"760db6183907a24fe5c166864a4c1e87e31502e8","datavalue":{"value":"https://doi.org/10.1016/j.jsc.2011.09.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q412202$54DDC557-4CAE-403C-BAE5-EBDFBD74EC36","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2db4f6672f54e59e5adddd301cf1953b86e29c30","datavalue":{"value":"W2022432349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$A9B97BE8-FCD9-445C-B827-3B13C970E9C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf7864d52795e3024212f33d34ce2fd77a413d9","datavalue":{"value":{"entity-type":"item","numeric-id":2785383,"id":"Q2785383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$A730B3E6-63B0-4368-AC6E-528B683597F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd6c18a657aa24b4c1725768bf2c4c4a527cd03e","datavalue":{"value":{"entity-type":"item","numeric-id":5188542,"id":"Q5188542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$2A0DC155-7BE6-4F95-86B4-6F9135C86495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ccbb922165f2699cfdc941c91af219b767c01f","datavalue":{"value":{"entity-type":"item","numeric-id":3420245,"id":"Q3420245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$6CE6D565-C8BD-47C3-8196-0C8BA0CC3DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41a3dade4b3dedf68f423bc55d01d535a93c6f99","datavalue":{"value":{"entity-type":"item","numeric-id":3582763,"id":"Q3582763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$1AA98741-14F2-4729-BC30-B76F26773F84","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":"Q412202$B76B408E-AABC-4D3B-93F2-DE10A1FD55D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dbfba5386a9300fa0e4804ce40960e92cd42409","datavalue":{"value":{"entity-type":"item","numeric-id":1041163,"id":"Q1041163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412202$A69505A4-2066-48D8-BF5F-14A0E768452D","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":"Q412202$B6ECFC24-4D89-4F91-8D8E-FF4B572C6900","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6eca8cb0df89b7849325567b2086340ae03867d0","datavalue":{"value":"10.1016/J.JSC.2011.09.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412202$2C047852-6381-4E96-8DC6-8A66D6FB737B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab5d0e9090530cb98c38a23f902842a78ad36e36","datavalue":{"value":{"entity-type":"item","numeric-id":2787639,"id":"Q2787639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb87676f3f292f96111fe4cfae7fab08015f391d","datavalue":{"value":{"amount":"+0.8770485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$D0A9D4F9-8DAC-43F5-B253-5CA700863B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cbfe3bdb5e256321db9b3af74fd957d4e0aa6d9","datavalue":{"value":{"entity-type":"item","numeric-id":745185,"id":"Q745185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b540d7e5b1ff06106bd81f49b5a74511bf90ed6","datavalue":{"value":{"amount":"+0.8328135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$E3FFCFEB-AA0F-48DA-BBD4-ACEE0464451E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"625cb8cdb09b5ae383b16de18977cf381c6c5c16","datavalue":{"value":{"entity-type":"item","numeric-id":2792346,"id":"Q2792346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1242aa077d978f147fc372d38fcfb471ae9aa23","datavalue":{"value":{"amount":"+0.8303085","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$9FFD9F98-6245-4012-AB5D-588A661EDB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d5be3063ac4b09b717f073f8eae8c340aa5ca57","datavalue":{"value":{"entity-type":"item","numeric-id":5888180,"id":"Q5888180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cc418ccf3337baaf321a5fe8baec62c9fbb1570","datavalue":{"value":{"amount":"+0.8170927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$28304335-C1BD-4044-AEDF-F2CA7DDDB4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b10667e03fe2c3cc7370442ab67fe4f891a0a3","datavalue":{"value":{"entity-type":"item","numeric-id":3420245,"id":"Q3420245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47e6d17846149b0ac1851838649f7480f772634a","datavalue":{"value":{"amount":"+0.80264777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$E9A76722-8F4F-4B20-95DF-1E55D75FD0A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a03881068bedd0c1ad8cb6a0e303bdcb7e67d0ad","datavalue":{"value":{"entity-type":"item","numeric-id":3166983,"id":"Q3166983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8dceb7e814bf1bdd215294b1f31c7f37df23647","datavalue":{"value":{"amount":"+0.792401","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$6CF38CD2-23A1-431C-8FC7-6914297FD87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbb08ad3e0e504f48df7a4c8a29aa3f71c7854a8","datavalue":{"value":{"entity-type":"item","numeric-id":5264135,"id":"Q5264135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcb91a69a0585be65e332e48b4f005124e4a9fd2","datavalue":{"value":{"amount":"+0.78900486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$D5F7091B-0F9F-4FFC-A836-7FC4F4DF8EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"136ad8be448e491e1315c1a5a19137029b8be05f","datavalue":{"value":{"entity-type":"item","numeric-id":3840157,"id":"Q3840157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21ac8691c5999e8f01c23303d041ce7500e27ad5","datavalue":{"value":{"amount":"+0.7772893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$3ABD914D-A36E-4C63-9D2C-A9B6202447DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79b32a38813052901162e1f68e433e48fa4fdb90","datavalue":{"value":{"entity-type":"item","numeric-id":4375601,"id":"Q4375601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c7735f3ac72aa26f9a35b2984def07b9cb9dab0","datavalue":{"value":{"amount":"+0.7756715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$8A63BF21-BB72-4699-A555-BE5E96BE7AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9316cdecc5a0b7aa562b0d099df537dc56485f33","datavalue":{"value":{"entity-type":"item","numeric-id":3838139,"id":"Q3838139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f99710295567c3f0483ac002411151cfc3ca71a0","datavalue":{"value":{"amount":"+0.76979524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q412202$5DCA47D3-E2C9-4CAF-BC56-665C9DEB7C25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd6a63f3e18c1886a8e411782c34dd3a45decef2","datavalue":{"value":"The Number Field Sieve (see [\\textit{A. K. Lenstra} and \\textit{H. W. Lenstra jun.} (eds.), The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)]) is the best method today to factor a large integer \\(N\\). A first step is to find two polynomials \\(f,g\\in \\mathbb{Z}[X]\\) sharing a common root modulo \\(N\\)\\, or equivalently with resultant \\(\\text{Res}(f,g)\\) a (small) multiple of \\(N\\) (polynomial selection).NEWLINENEWLINEUsually one takes \\(g\\) to be a linear polynomial and as \\(f\\) a polynomial of (small) degree \\(d>1\\). P. L. Montgomery (see \\textit{M. Elkenbracht-Huizing} [Exp. Math. 5, No. 3, 231--253 (1996; Zbl 0869.11101)]) proposed a method producing polynomials \\(f,g\\) of degree two and recently \\textit{R. S. Williams} [M. Sc. Thesis, Texas Tech. Univ. (1910)] gave an algorithm to select \\(f,g\\) with degree \\(d=3\\). The present paper generalizes Montgomery's method allowing to find polynomials of (the same) degree \\(d\\) for any \\(d\\).NEWLINENEWLINENEWLINESection 1 reminds notations and basic facts about lattices and resultants and Section 2 summarizes the state of the art in polynomial selection, describing the Montgomery and Williams algorithms. Section 3 describes the proposed method giving details of the algorithm in the case \\(d=3\\). In this last case the authors conclude that their method improves Williams' algorithm because ``it finds two polynomials with resultant \\(O(N^{5/4})\\) instead of \\(O(N^{4/3})\\)''. Finally Section 4 discusses the open question of how to produce polynomials \\(f,g\\) of different degrees, in particular \\(d\\) and \\(d-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q412202$20C70942-58EC-48AA-9D33-B0B467185890","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Non-linear polynomial selection for the number field sieve","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Non-linear_polynomial_selection_for_the_number_field_sieve"}}}}}