{"entities":{"Q1611366":{"pageid":1622106,"ns":120,"title":"Item:Q1611366","lastrevid":68041047,"modified":"2026-04-12T21:02:33Z","type":"item","id":"Q1611366","labels":{"en":{"language":"en","value":"A rigorous proof of the Waterloo algorithm for the discrete logarithm problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1785711"}},"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":"Q1611366$BF080C9F-A452-4379-A97A-55D14D32A9CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"adc598ce4aa5e060261aa1090647cff8c5d37ad0","datavalue":{"value":{"text":"A rigorous proof of the Waterloo algorithm for the discrete logarithm problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1611366$87DB7E3F-AB63-43AA-B5EF-76423690A649","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"79c12b9d324df471e1e4308222e79465799ab92c","datavalue":{"value":"1006.11072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$BA6F6202-3C4F-4DFA-8B6E-15D0A5CF427D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1684745c14579b04456a7202ef5b94e13b56a77","datavalue":{"value":"10.1023/A:1016521712726","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$47AFE702-EE6A-451F-8CE3-102DDE76C2A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"302a8d1286d2de3de883395ca11232e5696964f7","datavalue":{"value":{"entity-type":"item","numeric-id":213077,"id":"Q213077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1611366$DC0EDFCC-52EE-443F-904A-D46CD64CF506","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":"Q1611366$2ED6BA30-7DEB-47AC-A986-69146AD25218","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fb34abbf39f11094509111953e4c62a22b1e3897","datavalue":{"value":{"entity-type":"item","numeric-id":115940,"id":"Q115940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1611366$EB2F0716-4019-444B-A019-574B855AB7FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c29b947d701d478aa12d107bbc6ea14baaef48c","datavalue":{"value":{"time":"+2002-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1611366$64484BFE-78F0-499F-8FBB-D608EB7A8CB6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff71fafcb399bfc1c1a06147e130ca83fda9268d","datavalue":{"value":"The index calculus attack is a sub-exponential algorithm to compute discrete logarithms in finite fields. For fields of small characteristic, especially \\(\\mathbb{F}_{2^n}\\), \\textit{D. Coppersmith}'s variant [IEEE Trans. Inf. Theory 30, 587-594 (1984; Zbl 0554.12013)] is (heuristically) most efficient. A further algorithm specially designed for this case is the Waterloo algorithm [Advances in cryptology, Proc. Workshop, Santa Barbara/Calif. 1984, Lect. Notes Comput. Sci. 196, 73-82 (1985; Zbl 0574.94012)] by \\textit{I. F. Blake, R. C. Mullin}, and \\textit{S. A. Vanstone}. The present article manages to give proofs for the heuristic arguments used to estimate the running time. The main step is to compute the probability that two polynomials of degree at most \\(n/2\\) factor into irreducible polynomials of degree at most \\(m\\), where \\(m\\) is a parameter of the algorithm. To reach this aim the authors estimate the number of \\(m\\)-smooth polynomials of bounded degree and coprime pairs of such polynomials. The main tool used to derive these results are generating functions for polynomials and the saddle point method as in \\textit{A. L. Odlyzko} [Advances in cryptology, Proc. EUROCRYPT 84, Workshop Paris 1984, Lect. Notes Comput. Sci. 209, 224-314 (1985; Zbl 0594.94016)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1611366$E5418B4A-BF4B-483A-ABDA-66886148BE17","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"05d313fafb9c8d843f17d1fd39b688f4cfaf3dbe","datavalue":{"value":{"entity-type":"item","numeric-id":701119,"id":"Q701119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1611366$18651CCA-32C4-449C-A84C-3753CC3FBFD1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$5A7BD34B-3560-4FC0-8896-2DA2D948978C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$218B943C-0FAE-4AF7-A5BB-70AFF8EC9CD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$5E91A210-67F2-4DC7-B4F4-EE3249774568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$AA51D068-C768-4717-9CB7-7977571D9333","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"563f7dbb92ca26339966f80d425dbd36cda93fb0","datavalue":{"value":"1785711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$53700F00-7278-4BCB-9086-11D0F0528FD6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76c3b676e35ac52749b3f6c477b01691c4b0dc96","datavalue":{"value":"discrete logarithm problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1611366$2314A00D-BCD3-4789-B290-4D3DD93F21DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1611366$EE38881D-78F4-4214-8134-58F0929E7AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8c8bba3406f85e9131f398a983c32f9564a53d3","datavalue":{"value":"smooth polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1611366$51F2DCB7-56FC-49F8-BC82-9D3C8947755A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"931fc00879af8b0f86011ef32c390fa4802ca84e","datavalue":{"value":"generating functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1611366$A6ADC6B7-6FB2-4F51-B9C4-EABEAFAF5C9D","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":"Q1611366$6F1CB462-39CE-4BEB-87BA-C5A131A4F729","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"def31bfe0ceef3a8b7cb58972745329edca2ebfc","datavalue":{"value":"https://doi.org/10.1023/a:1016521712726","type":"string"},"datatype":"url"},"type":"statement","id":"Q1611366$9A4D76F2-7AC4-46CE-8DF9-EB05A198C423","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1ee3762a18a0996ffe5a87c4dfcaaa1983b61cd4","datavalue":{"value":"W1596459745","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1611366$E9A1731C-A6BD-4A53-A84D-44ECB604D754","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b74c6ecb1010f426b84a4560c7a089374ba568b4","datavalue":{"value":{"entity-type":"item","numeric-id":2154468,"id":"Q2154468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ada9ef88c2f2733cc40cc9f85c33dca0d2a50a4a","datavalue":{"value":{"amount":"+0.87347895","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":"Q1611366$A2254E5E-BFFC-4A71-8AA4-5A6799FE153E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53552676735685923b4fa85cd2a2b6e7fcb21a4b","datavalue":{"value":{"entity-type":"item","numeric-id":5898934,"id":"Q5898934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97b7511258eadcf0c2ae7a61fb814bc6e716b2c0","datavalue":{"value":{"amount":"+0.8723","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":"Q1611366$30317B48-506D-4A12-BF67-961CE6544812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef733fd14c87b5cb22daf4f39d8e44ea068ee9b2","datavalue":{"value":{"entity-type":"item","numeric-id":5150750,"id":"Q5150750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec2b0cec4478199a06dddc4085b3b68c48f877c","datavalue":{"value":{"amount":"+0.8706964","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":"Q1611366$9A026E76-F5A1-4032-8AFA-8E6FD9DAE2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"903abaab87ec423d5dfec4824b02084488356b2c","datavalue":{"value":{"entity-type":"item","numeric-id":2414928,"id":"Q2414928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9da291c2fe5101e4c746c5a6f984de3549568bf","datavalue":{"value":{"amount":"+0.8701652","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":"Q1611366$6F202988-66E4-4E10-AA29-4AD59C67383D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"127a96016ac14957b1fdb345e2eb7bf5c1c95b6b","datavalue":{"value":{"entity-type":"item","numeric-id":5380102,"id":"Q5380102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"845d398ed2e4e82e0fd953385f927db6bfde16e1","datavalue":{"value":{"amount":"+0.8683305","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":"Q1611366$094E6FDA-BA5B-4778-8008-869C2362E38A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32ad349ba4a209c727c884569842d9d4cec1c0db","datavalue":{"value":{"entity-type":"item","numeric-id":3792628,"id":"Q3792628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18be78fcb21b79c5621f74fef1341b7794f619b9","datavalue":{"value":{"amount":"+0.867127","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":"Q1611366$E0D584DA-C0E1-489E-9447-AA877713B89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d2e8e16c56415349e6219ad96a49b9403749830","datavalue":{"value":{"entity-type":"item","numeric-id":1898267,"id":"Q1898267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52e07c75178fca322cedc4a385f1014f36fa3638","datavalue":{"value":{"amount":"+0.8668372","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":"Q1611366$0E9CA4E4-94C9-4FBC-B0F9-98C7A1F24C50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d9349bc6ec3f68b6be7707523d5b3a74215171e","datavalue":{"value":{"entity-type":"item","numeric-id":5750402,"id":"Q5750402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91eeb59028b1607b6842a7886fa26818d3b8b257","datavalue":{"value":{"amount":"+0.8641542","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":"Q1611366$22A4EFEB-1C2B-40A1-97F8-615876A7F3B8","rank":"normal"},{"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":"ef9e574ed0f070e58671f68f458c80afdd553f8b","datavalue":{"value":{"amount":"+0.86245275","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":"Q1611366$692DDDA0-96BB-4FB1-8698-3526B794052D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"764d7b8ede0c2615f7b18b8f72d745d88f64145b","datavalue":{"value":{"entity-type":"item","numeric-id":4341740,"id":"Q4341740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef9e574ed0f070e58671f68f458c80afdd553f8b","datavalue":{"value":{"amount":"+0.86245275","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":"Q1611366$9FC1BCED-6063-4A42-A709-E6E7B3B50066","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A rigorous proof of the Waterloo algorithm for the discrete logarithm problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_rigorous_proof_of_the_Waterloo_algorithm_for_the_discrete_logarithm_problem"}}}}}