{"entities":{"Q2787639":{"pageid":2798377,"ns":120,"title":"Item:Q2787639","lastrevid":42015383,"modified":"2025-05-22T12:30:19Z","type":"item","id":"Q2787639","labels":{"en":{"language":"en","value":"On nonlinear polynomial selection and geometric progression (mod \\(N\\)) for number field sieve"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6550289"}},"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":"Q2787639$ACA8AEE5-00BF-4981-A0FF-56618656C0A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4adf21c848a9aeeb6cd71430e2cf73476f545e28","datavalue":{"value":"1371.11156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$956E8268-657A-4219-8C86-3FA8361E27D2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"17d8a04816e427e537e13e5f92f1f966a51824fe","datavalue":{"value":"10.4134/BKMS.2016.53.1.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$BF48733F-27C1-481C-95C5-0E389D9ACAC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe9ba1d3987737329512b296d74440f5b7a2902e","datavalue":{"value":{"entity-type":"item","numeric-id":1994922,"id":"Q1994922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2787639$7FA9A8B3-B720-4A77-988F-6C3CE0F670AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5de35f0ea10a9f7f2bbd353246f0d4257bac3c52","datavalue":{"value":{"entity-type":"item","numeric-id":1642468,"id":"Q1642468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2787639$70F289EE-3DC4-4DEC-8087-C142254B3FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f17c887fa7c17f603948924252951a446472597b","datavalue":{"value":{"entity-type":"item","numeric-id":676286,"id":"Q676286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2787639$8E79C663-9519-42CC-B447-3E73FC69DE6D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1330c4223145b61f69533c0e4a93f6a1dd88426d","datavalue":{"value":{"entity-type":"item","numeric-id":2732161,"id":"Q2732161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2787639$BC9AD999-E4B3-4B35-BEBF-9F71F97C315C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9baa329984daf997c3bf5a084a91839bc1428d33","datavalue":{"value":{"time":"+2016-03-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":"Q2787639$FDDD469B-3402-4E8C-8F06-73B1D984B5E2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"de1b04ae2f9184fdc02b6f14eba18151a876d01e","datavalue":{"value":"http://www.mathnet.or.kr/mathnet/kms_content.php?no=467642","type":"string"},"datatype":"url"},"type":"statement","id":"Q2787639$926936CB-C56E-4F25-9D0E-277C21EAA809","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$A318C179-471D-4139-AF54-5345CA0F3DF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$A7615182-DC6C-47DA-AE5E-CC3AF95F1143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8836e0c1033732ccd066d1e91f06d60cc8819832","datavalue":{"value":"11B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$5EC76002-9DF2-4FEB-AB29-5C83755CCD59","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fbf473cc3bf4cd7608a2f2305cc2ef236e2bab12","datavalue":{"value":"6550289","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2787639$15CE3B8B-D688-472E-881A-2D6A4C0E4269","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971d25706c332803bde4bc7afcefde2deb20bd9e","datavalue":{"value":"polynomial selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2787639$5BF2CC1F-D6AA-46E0-A748-01A806BC90AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d92933569277d10edac01435fc2574cbf9ecacc","datavalue":{"value":"number field sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q2787639$2B405395-CA92-42B8-978E-50EDA3FD46BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1659a48a72b8a980164f54aa054aa3d386cf120b","datavalue":{"value":"geometric progression","type":"string"},"datatype":"string"},"type":"statement","id":"Q2787639$753E1770-230F-423C-9B2E-96E59640C8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"015ffb40feb4fd81f8432ff4a5b23631a305315c","datavalue":{"value":"LLL algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2787639$94C1C2C2-6E4E-41AF-96EC-6994FADA5673","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":"Q2787639$C8C9326E-4B57-4F6F-87DC-FA28655B46DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91d253872ce3213b145ed21aa05a6986949b9a27","datavalue":{"value":{"entity-type":"item","numeric-id":412202,"id":"Q412202"},"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":"Q2787639$14FA3B64-3282-469E-B1F4-3DC71E12B641","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":"ed783655530ea783ce4d4639de743f29da80987d","datavalue":{"value":{"amount":"+0.8423703","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":"Q2787639$086F5CC4-DCE4-4601-A478-CC8D40A76774","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":"380d45f92183006269b3116bf873404c6d5629a5","datavalue":{"value":{"amount":"+0.7861084","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":"Q2787639$9A38F665-7024-4618-8BCA-B03471810614","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":"11aa0913be7a4fb502372b9e73e60bf759dba4b5","datavalue":{"value":{"amount":"+0.7788876","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":"Q2787639$B9EEC6D1-0438-4902-A538-99035D4BF6C1","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":"3a096da029433fff40b82ec96e13014f1d185ff5","datavalue":{"value":{"amount":"+0.77303755","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":"Q2787639$64224532-F6D5-4C10-9953-9E69A7EB9A8E","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":"5023b603cf482a707de0a30fdac1c3edbb0f2885","datavalue":{"value":{"amount":"+0.76687914","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":"Q2787639$345B5174-8AF2-4949-AAB8-0DFA1A951F06","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":"f6506860a286e081c7877c04fb086e80ef66a60c","datavalue":{"value":{"amount":"+0.75598264","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":"Q2787639$B1DA821E-091A-4405-A0EA-B7C70EF3979C","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":"a2a851f070b7c58086af6f54b74341e9cfcdcf27","datavalue":{"value":{"amount":"+0.74906874","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":"Q2787639$65C748A4-9DC5-4144-AF4B-6B58D0116B76","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":"d2011dc06f04c7ca99bdab66bcf17333169f051e","datavalue":{"value":{"amount":"+0.74571055","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":"Q2787639$A4D08072-979D-44BC-8B30-F352E05E989E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227c1f98d4138262374ee665456b2aa9af2613c2","datavalue":{"value":{"entity-type":"item","numeric-id":5391189,"id":"Q5391189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05b8e5cf7e4ffce1cf747e2cbd3902bf564b6f93","datavalue":{"value":{"amount":"+0.7296917","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":"Q2787639$041AD04C-BC6F-4219-97E4-C9519A450DB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e85f74960781fe4782b22812224fc18e00556136","datavalue":{"value":{"text":"On nonlinear polynomial selection and geometric progression (mod \\(N\\)) for number field sieve","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2787639$710CA0DE-01FA-4A43-B34E-BA3961AD1D08","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81ef4b290d829f2cfb1dc2f9e73f2a5e3873c039","datavalue":{"value":"A first step of the Number Field Sieve method to factor an integer \\(N\\) is to find two polynomials \\(f,g\\in \\mathbb{Z}[X]\\) sharing a common root modulo \\(N\\), see \\textit{A. K. Lenstra} and \\textit{H. W. Lenstra} (eds.) [Lect. Notes Math. 1554. Berlin: Springer Verlag (1993; Zbl 0777.00017)]. Usually one takes as \\(f\\) a nonlinear polynomial of small degree \\(d>1\\) and as \\(g\\) a linear one (linear polynomial selection) but 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 \\(d\\geq 2\\) (nonlinear polynomial selection).NEWLINENEWLINENEWLINEMontgomery's method finds \\(f,g\\) given a geometric progression modulo \\(N\\) \\([c_0,\\dots, c_{2d-2}]\\) of length \\(2d-1\\) and \\(c_i=O(N^{1-1/d})\\). Montgomery shows how to construct such \\(\\text{GP} \\pmod N\\) when \\(d=2\\). The present paper proposes some generalizations of the Montgomery's method.NEWLINENEWLINENEWLINESection 3 uses \\(\\text{GP}\\pmod N\\) of length \\(d+k\\), \\(1\\leq k\\leq d-1\\), allowing to find polynomials \\(f,g\\) with degree \\(d\\) sharing a common root modulo \\(N\\) for \\(l/2<d<l\\) for a GP of length \\(l\\). Theorems 1 and 2 show the relations between \\(\\text{GP}\\pmod N\\) and pairs of polynomials \\(f,g\\), the number of such pairs and the size of their coefficients. Section 3 studies the classes of GP of length \\(d+1\\) and \\(d+2\\) and provides examples of both types.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2787639$9F4568B4-B99E-4FFE-AA03-FB1B4EEC23D9","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":"Q2787639$D3D5DE23-AE16-4967-AD5C-AA6A2E035A9B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2787639","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2787639"}}}}}