{"entities":{"Q2719078":{"pageid":2729817,"ns":120,"title":"Item:Q2719078","lastrevid":82998890,"modified":"2026-05-06T22:37:55Z","type":"item","id":"Q2719078","labels":{"en":{"language":"en","value":"The index calculus method using non-smooth polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1597965"}},"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":"Q2719078$C6BE0A84-7333-4B81-A290-4A27BCD9707E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22647149e86b31bc7d95d5e58abcac44a6cea2c9","datavalue":{"value":"0982.11071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$5C519A88-592B-4332-82FA-F69F61F6D006","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"acbc2af843bd7c4c25ef2e108f9d1b2af64fe061","datavalue":{"value":"10.1090/S0025-5718-01-01298-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$3FFE8B03-CF28-4E0B-82EB-A368AECAA851","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"030e5d47e3499b011ce8f65cb76e83a6b54c84fd","datavalue":{"value":{"entity-type":"item","numeric-id":439092,"id":"Q439092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$D5DF01D6-DAEB-48DE-A807-6D83D05BA512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38491a7ac1e8ccbfecab277114086e0b35ff394f","datavalue":{"value":{"entity-type":"item","numeric-id":169310,"id":"Q169310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$A32D3068-F7EF-4720-A916-9A265FD82A3F","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":"Q2719078$905A52B8-D745-4138-BEAA-ADB1B5DBB9CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e0a8ef751728b2b17bbcf17280282a4718c22627","datavalue":{"value":{"time":"+2001-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2719078$5C1DEFF0-3AB3-412A-92FB-8632C2C0F73D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$F66F8981-611B-4371-9C44-5E966E524E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$60F6B437-1ED0-4965-AFF1-93C6C231A435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$310DC092-700E-427C-B8EB-B3B71865968E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$86C8303E-DA9C-4DF1-8B34-CC09071F587B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$E340066C-7066-423A-A936-6AE33FA2BD97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$A5ADEAB1-F116-4685-BDA3-D092CAA07880","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a03dd5933ebfc00ec4f5e04b48f357cd14af2e7c","datavalue":{"value":"1597965","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2719078$6AFAE8FB-3B23-47D0-BD50-72D9763A7192","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q2719078$6F33FD21-486A-44D0-834C-C7C0D2684435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63b6e7519439f3dae7ed038b09ceb974d18f527f","datavalue":{"value":"discrete logarithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2719078$C5558948-50F4-44FC-9FA6-A2B5BC80FD48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q2719078$EA737FB8-B7B5-41CC-A5A1-CE61F185E445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8c8bba3406f85e9131f398a983c32f9564a53d3","datavalue":{"value":"smooth polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q2719078$A4FEC4D9-C8E8-4902-88F7-8D1E395855E5","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":"Q2719078$226755E4-D2CA-4F46-B382-7BA9AD052CA2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f3fbc1309a974a811915b3068df7d148fb256f9","datavalue":{"value":{"entity-type":"item","numeric-id":3320493,"id":"Q3320493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$A608A686-EEA3-492A-A864-59156A97BC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a581f96e8cabd60b98280dbc93b840cb31eb7421","datavalue":{"value":{"entity-type":"item","numeric-id":3339289,"id":"Q3339289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$EC855223-1A4C-40DF-A6F7-7E4EA022F86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aadf2df93d48a781d328dff09757916d5e3d7d9","datavalue":{"value":{"entity-type":"item","numeric-id":1202149,"id":"Q1202149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$9E26D692-4F2B-409C-B8A9-94D3C64E231E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d971207323fc32c252b42f869ff1c8bcd7ecda2","datavalue":{"value":{"entity-type":"item","numeric-id":3216753,"id":"Q3216753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$85C8BEB3-C337-4BAB-B81F-F11D81D768E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e40651885e589ae16736b2ed26430168a8207418","datavalue":{"value":{"entity-type":"item","numeric-id":3875826,"id":"Q3875826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$3879A81C-EA1C-4BF8-8637-E3E5DEE889D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cda85911724dc7df1b5bc469cb04a8165137fbb8","datavalue":{"value":{"entity-type":"item","numeric-id":3705350,"id":"Q3705350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$10A1C86F-EA16-4024-B716-E6E8876F312A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9325ee32ab085cf1f8f87a10cc1d2d990b86a154","datavalue":{"value":{"entity-type":"item","numeric-id":4217866,"id":"Q4217866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$9A4312B8-2C90-4D33-B450-3EA607A2889E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddf8a6720a728f67231840e8f58c4ee6cf3369e1","datavalue":{"value":{"entity-type":"item","numeric-id":4372701,"id":"Q4372701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$7FD44093-0DF5-4A60-9F8B-329D79A6416F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f89dbd6017fea2e86a08e4f1b8f57827eed8cab","datavalue":{"value":{"entity-type":"item","numeric-id":4799524,"id":"Q4799524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$53051A5C-7379-46BE-88C2-DFD7E3D66FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d847066036254452782dd2fb074dc0d6d96c79d","datavalue":{"value":{"entity-type":"item","numeric-id":5928877,"id":"Q5928877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$F6A88A38-C1BE-49AE-82BF-032C744EF21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91c72470240cb65021f36a0e6ec12560df7c5675","datavalue":{"value":{"entity-type":"item","numeric-id":4893202,"id":"Q4893202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$E56D2D6C-EEB9-4A1D-B4E5-B7D13126AF71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e95077d020c5f6b661b441b54cadb9581d456da","datavalue":{"value":{"entity-type":"item","numeric-id":4213392,"id":"Q4213392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$8BBA4CE9-AC05-4F23-AAB1-9387DD17E31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b18db7a0da41b2f07c7fee3e133fd1755390a53","datavalue":{"value":{"entity-type":"item","numeric-id":3141896,"id":"Q3141896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$C418261B-FD45-4601-AB57-E3F742639029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd3fed77c9b02d6f60e6602f5f3aab32c777e01","datavalue":{"value":{"entity-type":"item","numeric-id":4235520,"id":"Q4235520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$B9A9363D-9CE9-4101-8E5A-D748A118FAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c551822e86c0407675a9f9f7fcb1ddd9dd22246b","datavalue":{"value":{"entity-type":"item","numeric-id":3726006,"id":"Q3726006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$4706A8EC-AA4F-4216-B24E-7DE9C0D1141A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa05153ceb8a5a9a53eefd730a8dfeffd2a8c98","datavalue":{"value":{"entity-type":"item","numeric-id":4314374,"id":"Q4314374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$077971CE-068A-4FC9-82E8-D0F9B42A6434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a0be0d87ecd75a5c57dde884eb78d56ae3fb6b","datavalue":{"value":{"entity-type":"item","numeric-id":3746790,"id":"Q3746790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$E162EEB0-DB7F-43E1-A088-82837B740EEB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e32bbb44ffff67219e307a8264ce0685082ab793","datavalue":{"value":{"text":"The index calculus method using non-smooth polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2719078$866F5E9E-6C8B-4E6F-8384-2B44057C359B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e10c1bb3a0e68b81ef21fd64b2dc2bc7f3be991","datavalue":{"value":"The discrete logarithm problem of interest uses the index calculus method for the finite field \\({\\mathbb F}_q\\), \\(q=p^n\\) for \\(p\\) a prime and \\(n>1\\). The elements of \\({\\mathbb F}_q\\) are represented as polynomials over \\({\\mathbb F}_p\\) of degree smaller than \\(n\\), and arithmetic in the field is modulo an irreducible polynomial \\(f(x)\\) of degree \\(n\\). The case of interest here is for \\(p\\) small and \\(n \\rightarrow \\infty\\). A set \\(S\\) of irreducible polynomials over \\({\\mathbb F}_p\\) is chosen, called the factor base. Given a generator \\(g\\) of the multiplicative group of \\({\\mathbb F}_q\\), it is desired to compute the discrete logarithm of the polynomial \\(h^*\\) to the base \\(g\\). NEWLINENEWLINENEWLINEThe algorithm proceeds in two stages. In the first stage an attempt is made to find the logarithms of the polynomials in the factor base \\(S\\) by forming random relations between powers of \\(g\\) and powers of polynomials in \\(S\\) by seeing if \\(g^s \\pmod{f}\\) factors over \\(S\\). The relations obtained are solved by matrix techniques. In the second stage one attempts to find the logarithm of \\(h \\equiv h^* g^s \\pmod{f}\\) for randomly chosen \\(s\\). NEWLINENEWLINENEWLINEOne usually chooses for the factor base \\(S\\) the set of irreducible polynomials of degree less than some bound. In this work, the effect of choosing \\(S\\) to be the set of irreducible polynomials of degrees between \\(m_1\\) and \\(m_2\\) is considered. It is shown that the algorithm that results with this choice has the same asymptotic running time as the original version and that the best upper limit for the interval coincides with the one for the original version. Experimental results are discussed and heuristic arguments are given for the Waterloo and Coppersmith variants of the algorithm with this new factor base.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2719078$A25C4281-7C51-40A3-83C4-B77597497F3A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2719078$64B6F9CC-2842-4179-B5F3-8ADDA1A15DF9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15dcd2c3fbc8f31b39da00e51ef18a99175b8be4","datavalue":{"value":{"entity-type":"item","numeric-id":3137444,"id":"Q3137444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79148eac3875c156e8aa010b53c1dd14fe05a341","datavalue":{"value":{"amount":"+0.8732606768608093","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":"Q2719078$AA2545B6-DF72-4DD3-87C0-C59E6ABBD892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a09ba2a8024a1b32309b5cd08d0fb3d2138d532","datavalue":{"value":{"entity-type":"item","numeric-id":3615928,"id":"Q3615928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2debe910ea092d4ee0100e1e33d4e7c2b3370bcd","datavalue":{"value":{"amount":"+0.8690574765205383","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":"Q2719078$3536CDD1-2FA0-493A-BE2C-350E94924514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f231209178dff52592425f9b58069467bc3c4f70","datavalue":{"value":{"entity-type":"item","numeric-id":4213392,"id":"Q4213392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2826c460fa950f5688a354acd24d07f3a7136f","datavalue":{"value":{"amount":"+0.8602476119995117","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":"Q2719078$23E7C34E-360E-49FC-80AF-38B59BA73EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f87c93b876ab644732a00232e7d878c09ac6352d","datavalue":{"value":{"entity-type":"item","numeric-id":1591638,"id":"Q1591638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2826c460fa950f5688a354acd24d07f3a7136f","datavalue":{"value":{"amount":"+0.8602476119995117","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":"Q2719078$B83E9CE6-DDAC-40BC-8401-0EE9AF0EFDFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20f6b502d0b8c0ff06edc8d3e91dcac17892eae3","datavalue":{"value":{"entity-type":"item","numeric-id":4856880,"id":"Q4856880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2f8bed1440cd91b0f03278432d4513eace8db0a","datavalue":{"value":{"amount":"+0.8533273935317993","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":"Q2719078$A292842D-80C5-466C-88A0-9B2D7C1F8BA2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The index calculus method using non-smooth polynomials","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_index_calculus_method_using_non-smooth_polynomials"}}}}}