{"entities":{"Q2792346":{"pageid":2803084,"ns":120,"title":"Item:Q2792346","lastrevid":52477079,"modified":"2026-01-22T18:25:44Z","type":"item","id":"Q2792346","labels":{"en":{"language":"en","value":"Better polynomials for GNFS"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6552499"}},"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":"Q2792346$6F2D49F2-2AD1-4C54-9403-30911F4770E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"16f6e06f196be3f04df13bd44fc06d55643e1968","datavalue":{"value":{"text":"Better polynomials for GNFS","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2792346$EF4EFCC2-DB13-423A-A34A-F73E68C9EB60","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fad3672e2b6e82ff454192d4b6e60fda41de7996","datavalue":{"value":"1377.11125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$25DB3FE8-A0D0-4E4A-9975-44711F9ECDE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c7e0a76714d21b8d334adcba65faa5b75bd5dec","datavalue":{"value":{"entity-type":"item","numeric-id":1078135,"id":"Q1078135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$F60EBF06-12D9-41B0-83EC-246ABD72D9E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94365f16a75e3d8d08c55228033a8d7e24867185","datavalue":{"value":{"entity-type":"item","numeric-id":2055703,"id":"Q2055703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$E2A1AEC5-59D0-4C91-B457-2BABCEAC594D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"581cc3aabb2d56de850d507f1ab86336127e5337","datavalue":{"value":{"entity-type":"item","numeric-id":2792345,"id":"Q2792345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$1F4763F3-B353-4D1A-BA6C-2BDBC666994B","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":"Q2792346$8B4D953C-2D91-41B1-AC9A-5D1E002A668C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"baa5e802769412f0844a94f995d30b9509cb3673","datavalue":{"value":{"entity-type":"item","numeric-id":65726,"id":"Q65726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$9A12468E-B9E8-4815-9584-B006129B43BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ddcefc10613dfba994bca5094600721a8bb07857","datavalue":{"value":{"time":"+2016-03-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2792346$B2FC56F7-200E-46B1-B66D-AB1BCB9CF904","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d29d7ee2168a96d35db3611c2978d9e8f21f1a4","datavalue":{"value":"https://hal.inria.fr/hal-01089507/file/sopt-20140905.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2792346$8C25EDB2-E164-47A5-8ADB-BA569ACE7773","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$9E02D12A-D4C6-470A-8676-A511246BA34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$BC4FE36C-83B2-44EA-9574-0D0CF8E160FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$588F8158-10D3-4D12-9C7B-F4B84671A68B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"142c00b8d548035f28173baf29e2c3c95b774095","datavalue":{"value":"6552499","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$BB7172DD-C939-4FC6-8E3A-C0750B7BC1EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"971d25706c332803bde4bc7afcefde2deb20bd9e","datavalue":{"value":"polynomial selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2792346$868FB83E-1516-460F-853E-2A6010F69A36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c8b1ceebf31be2bb57ae446acedaa9a07a19997","datavalue":{"value":"general number field sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q2792346$0CC26A8D-271F-49A8-B0E2-B53359912DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5aeb0b983bdb4b724393c6caa76cb17ace6f6415","datavalue":{"value":"size optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2792346$939C4918-1FC6-4F8B-B5F9-6A8809A7AB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a7495423acd742d23f5e6c277ddc702efc21d98","datavalue":{"value":"RSA cryptosystem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2792346$A1C4944E-991A-46B5-8451-CDB662E5283B","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c782801fdd3371f9fb588015af28cb26b4be906f","datavalue":{"value":{"entity-type":"item","numeric-id":19299,"id":"Q19299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$7A195AB8-22AF-42CC-AFE0-0BFB8CF1C28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e0c4a6ad3c27ba998e0e2d591cca239aaacb62b4","datavalue":{"value":{"entity-type":"item","numeric-id":54932,"id":"Q54932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$6BE9F6A0-6F8B-4250-9EA2-FE3F703926B5","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":"Q2792346$F864BBB1-6035-43C6-8A54-7EA177D895EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"75550887d7b9ef69b91c57aa60cf5d475734ffa7","datavalue":{"value":"W2007595765","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$5BD3958E-C87D-4EC9-80D4-C39208EFE8DF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49c5828eda9d8ef7dd9252ab58dc3dc87cde9d83","datavalue":{"value":{"entity-type":"item","numeric-id":5264135,"id":"Q5264135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$64607FA4-231C-441F-8CEF-FE5A33B5E2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfc5592294a90ccdc261af236caea25d4702ed1f","datavalue":{"value":{"entity-type":"item","numeric-id":2826687,"id":"Q2826687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$C49F745A-06F1-4DD6-B30D-AA5AED55C468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6cc0e794c3e822623a98e375e48032bb7e640ad","datavalue":{"value":{"entity-type":"item","numeric-id":4273681,"id":"Q4273681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$FD7DC460-2F8F-49A0-AA6E-4529F279B516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2e6850be8358b6c5e8ee5013eac646311867ea","datavalue":{"value":{"entity-type":"item","numeric-id":3615925,"id":"Q3615925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$B29C2398-83E1-4B81-9677-3F3644A123A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0db340cee27a6e90b89e9608c03cbc1dd643ffe8","datavalue":{"value":{"entity-type":"item","numeric-id":1320524,"id":"Q1320524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$808D1DF1-D141-407A-AED0-5D4EDC7A00D1","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":"Q2792346$1669E17D-3696-4E95-832B-B0FA5FEAA671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb2c469b81d6110dea3018c85fde542bb3eec30b","datavalue":{"value":{"entity-type":"item","numeric-id":689067,"id":"Q689067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$F788D697-E480-4E3A-BE84-E4BD983CF17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61d7a694079f32d2e8ef705fa1ca39732fe18534","datavalue":{"value":{"entity-type":"item","numeric-id":3840157,"id":"Q3840157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$26885AE4-3F31-4047-BA54-D29154CE7091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0976a9c037230064b408226242c4eaba8d09ae7a","datavalue":{"value":{"entity-type":"item","numeric-id":4953360,"id":"Q4953360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$BABC4BFC-97EA-4832-A1E5-5D165AA4A94B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"341ffe90a37096919c89edcf5568cb818b21453a","datavalue":{"value":{"entity-type":"item","numeric-id":4273680,"id":"Q4273680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$58215ACF-36A4-452F-8D9C-73E42BF3D65C","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":"Q2792346$9FDED204-9496-472D-8B3B-8AA8EBC5F3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81b88eb61b2d2bd3a6009beb22421c0131c2583f","datavalue":{"value":{"entity-type":"item","numeric-id":3748329,"id":"Q3748329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$18F5F565-9AC4-4F26-9B6B-2D31F103DB26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b0f884a4968987fec3a14ba604f66cf8de4a430","datavalue":{"value":{"entity-type":"item","numeric-id":5902374,"id":"Q5902374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2792346$91F5A4D3-3558-4E00-AA4B-1CE7FAE5DE53","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c388cc8877507ce8134ff34e7c1693f825a30d79","datavalue":{"value":"Q128145885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$C1B36ADA-063A-4BA8-85BE-A467DEAF7512","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8dadc9b9a914ef106a2ea687b0d9c9bc3b999b2","datavalue":{"value":"10.1090/MCOM3048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2792346$552BBE9F-8F07-4511-9633-FFB6B859E478","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c154ff9a28a93ca6c9bb111103f4c15b71e14f6c","datavalue":{"value":"The General Number Field Sieve (GNFS) (see [\\textit{A. K. Lenstra} (ed.) and \\textit{H. W. Lenstra jun.} (ed.), The development of the number field sieve. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] is the best known method to factor a large integer \\(n\\). The first step of the GNFS is \\textit{polynomial selection}: to find two irreducible and coprime polynomials \\(f(x), g(x)\\in Z[X]\\) sharing a common root modulo \\(n\\) or equivalently with resultant \\(Res(f, g)\\equiv 0 \\bmod n\\).NEWLINENEWLINEIn this paper, as usually, \\(g\\)\\, is a linear polynomial and \\(f\\) a polynomial of (small) degree \\(d>1\\). (P. L. Montgomery and other authors proposed a method producing polynomials \\(f,g\\) of the same degree \\(d\\)). The running time of the GNFS method depends on the size and root properties of \\(f\\) and \\(g\\).NEWLINENEWLINEBeginning with some convenient \\(f,g\\) their size and root properties can be optimized using translation (\\(f(x+k), g(x+k)\\)) and rotation of \\(f(x)\\) by a polynomial \\(\\lambda(x)\\) (\\(f_{\\lambda}(x)=f(x)+\\lambda(x)g(x))\\), see [\\textit{B. A. Murphy}, Polynomial selection for the number field sieve integer factorisation algorithm. PhD thesis, The Australian National University (1999)]. The present paper deals with the size optimization step to produce polynomials with smaller logarithmic \\(L^2\\)-norm.NEWLINENEWLINESection 3 first describes some methods that produce polynomials with \\(Res(f,g)=n\\) and then proposes a generalization such that \\(Res(f,g)=ln\\), with \\(l\\) a small number. The algorithm, described for \\(deg(f)=6\\), takes \\(f(x+k)\\) for several values of \\(k\\) (Section 3.4 describes two methods to choose such \\(k\\)) and applies the Lenstra-Lenstra-Lov\u00e1sz (LLL) algorithm to find a good rotation of \\(f(x+k)\\). Table 1 shows numerical results with \\(10^5\\) sextic polynomials (for RSA-768) and 5795 quintic polynomials (for RSA-512). Finally Section 4 gives examples of polynomials for some RSA challenge numbers (RSA-768, RSA-896 and RSA-1024).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2792346$E5A3DE89-9730-4771-B78C-EAD5357DC1F4","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":"Q2792346$2F5325EF-77F9-482C-AEEF-A7B48B798DBF","rank":"normal"}],"P1643":[{"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":"09d0fafc8ddd96db88e8dc2036d1ecf276268add","datavalue":{"value":{"amount":"+0.888594388961792","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":"Q2792346$36EE33E2-82CD-4725-A10D-29D1CC9EA408","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":"5bcade9d6138d1575aff1baf14ab2fa58a56ce53","datavalue":{"value":{"amount":"+0.887324869632721","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":"Q2792346$6DF17B9E-0237-424C-A7B7-7DBE649775F5","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":"5704d9d0130d934050bf6d10d93b3ba91f6dd55b","datavalue":{"value":{"amount":"+0.8854625225067139","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":"Q2792346$BDB16706-AF1A-4D52-8F17-0CCBEFD0CD9C","rank":"normal"},{"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":"37bbda0f708e3eae15a200940d4407455dbaf08b","datavalue":{"value":{"amount":"+0.8790715336799622","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":"Q2792346$B49C63C7-7C6C-4218-BF10-9783834CAF99","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":"c7eb803c5257d1b19c9d100e0ce89c6d015c92c2","datavalue":{"value":{"amount":"+0.8396756649017334","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":"Q2792346$1ED5C013-62F3-4EFE-9AEB-1D1FDEFE642E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2792346","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2792346"}}}}}