1@article{koblitz1987elliptic,2 author = {Koblitz, Neal},3 title = {Elliptic Curve Cryptosystems},4 journal = {Mathematics of Computation},5 year = {1987},6 volume = {48},7 number = {177},8 pages = {203--209},9 doi = {10.1090/S0025-5718-1987-0866109-5}10}1112@incollection{miller1985use,13 author = {Miller, Victor S.},14 title = {Use of Elliptic Curves in Cryptography},15 booktitle = {Advances in Cryptology --- CRYPTO '85},16 series = {Lecture Notes in Computer Science},17 volume = {218},18 publisher = {Springer},19 year = {1986},20 pages = {417--426},21 doi = {10.1007/3-540-39799-X_31}22}2324@book{silverman2009arithmetic,25 author = {Silverman, Joseph H.},26 title = {The Arithmetic of Elliptic Curves},27 edition = {2nd},28 series = {Graduate Texts in Mathematics},29 volume = {106},30 publisher = {Springer},31 address = {New York},32 year = {2009},33 doi = {10.1007/978-0-387-09494-6}34}3536@book{washington2008elliptic,37 author = {Washington, Lawrence C.},38 title = {Elliptic Curves: Number Theory and Cryptography},39 edition = {2nd},40 publisher = {Chapman and Hall/CRC},41 address = {Boca Raton},42 year = {2008},43 doi = {10.1201/9781420071474}44}4546@book{galbraith2012mathematics,47 author = {Galbraith, Steven D.},48 title = {Mathematics of Public Key Cryptography},49 publisher = {Cambridge University Press},50 address = {Cambridge},51 year = {2012},52 doi = {10.1017/CBO9781139012843}53}5455@book{hankerson2004guide,56 author = {Hankerson, Darrel and Menezes, Alfred and Vanstone, Scott},57 title = {Guide to Elliptic Curve Cryptography},58 publisher = {Springer},59 address = {New York},60 year = {2004},61 doi = {10.1007/b97644}62}6364@book{menezes1996handbook,65 author = {Menezes, Alfred J. and van Oorschot, Paul C. and Vanstone, Scott A.},66 title = {Handbook of Applied Cryptography},67 publisher = {CRC Press},68 address = {Boca Raton},69 year = {1996},70 doi = {10.1201/9781439821916}71}7273@article{schoof1985elliptic,74 author = {Schoof, Ren{\'e}},75 title = {Elliptic Curves over Finite Fields and the Computation of Square Roots mod $p$},76 journal = {Mathematics of Computation},77 year = {1985},78 volume = {44},79 number = {170},80 pages = {483--494},81 doi = {10.1090/S0025-5718-1985-0777280-6}82}8384@article{schoof1995counting,85 author = {Schoof, Ren{\'e}},86 title = {Counting Points on Elliptic Curves over Finite Fields},87 journal = {Journal de Th{\'e}orie des Nombres de Bordeaux},88 year = {1995},89 volume = {7},90 number = {1},91 pages = {219--254},92 doi = {10.5802/jtnb.142}93}9495@incollection{cohen1998efficient,96 author = {Cohen, Henri and Miyaji, Atsuko and Ono, Takatoshi},97 title = {Efficient Elliptic Curve Exponentiation Using Mixed Coordinates},98 booktitle = {Advances in Cryptology --- ASIACRYPT '98},99 series = {Lecture Notes in Computer Science},100 volume = {1514},101 publisher = {Springer},102 year = {1998},103 pages = {51--65},104 doi = {10.1007/3-540-49649-1_6}105}106107@techreport{solinas1999generalized,108 author = {Solinas, Jerome A.},109 title = {Generalized {M}ersenne Numbers},110 institution = {Centre for Applied Cryptographic Research, University of Waterloo},111 number = {CORR 99-39},112 year = {1999},113 url = {https://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf}114}115116@article{montgomery1987speeding,117 author = {Montgomery, Peter L.},118 title = {Speeding the {P}ollard and Elliptic Curve Methods of Factorization},119 journal = {Mathematics of Computation},120 year = {1987},121 volume = {48},122 number = {177},123 pages = {243--264},124 doi = {10.1090/S0025-5718-1987-0866113-7}125}126127@incollection{brier2002weierstrass,128 author = {Brier, {\'E}ric and Joye, Marc},129 title = {Weierstra{\ss} Elliptic Curves and Side-Channel Attacks},130 booktitle = {Public Key Cryptography --- PKC 2002},131 series = {Lecture Notes in Computer Science},132 volume = {2274},133 publisher = {Springer},134 year = {2002},135 pages = {335--345},136 doi = {10.1007/3-540-45664-3_24}137}138139@incollection{gallant2001faster,140 author = {Gallant, Robert P. and Lambert, Robert J. and Vanstone, Scott A.},141 title = {Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms},142 booktitle = {Advances in Cryptology --- CRYPTO 2001},143 series = {Lecture Notes in Computer Science},144 volume = {2139},145 publisher = {Springer},146 year = {2001},147 pages = {190--200},148 doi = {10.1007/3-540-44647-8_11}149}150151@article{straus1964addition,152 author = {Straus, Ernst G.},153 title = {Addition Chains of Vectors (Problem 5125)},154 journal = {The American Mathematical Monthly},155 year = {1964},156 volume = {71},157 number = {7},158 pages = {806--808},159 doi = {10.2307/2310929},160 note = {Solution to problem 5125 proposed by R. Bellman}161}162163@article{pippenger1980evaluation,164 author = {Pippenger, Nicholas},165 title = {On the Evaluation of Powers and Monomials},166 journal = {SIAM Journal on Computing},167 year = {1980},168 volume = {9},169 number = {2},170 pages = {230--250},171 doi = {10.1137/0209022}172}173174@incollection{moller2001algorithms,175 author = {M{\"o}ller, Bodo},176 title = {Algorithms for Multi-exponentiation},177 booktitle = {Selected Areas in Cryptography --- SAC 2001},178 series = {Lecture Notes in Computer Science},179 volume = {2259},180 publisher = {Springer},181 year = {2001},182 pages = {165--180},183 doi = {10.1007/3-540-45537-X_13}184}185186@article{bernstein2012high,187 author = {Bernstein, Daniel J. and Duif, Niels and Lange, Tanja and Schwabe, Peter and Yang, Bo-Yin},188 title = {High-Speed High-Security Signatures},189 journal = {Journal of Cryptographic Engineering},190 year = {2012},191 volume = {2},192 number = {2},193 pages = {77--89},194 doi = {10.1007/s13389-012-0027-1}195}196197@incollection{naccache1994can,198 author = {Naccache, David and M'Ra{\"i}hi, David and Vaudenay, Serge and Raphaeli, Dan},199 title = {Can {D.S.A.} Be Improved? Complexity Trade-Offs with the Digital Signature Standard},200 booktitle = {Advances in Cryptology --- EUROCRYPT '94},201 series = {Lecture Notes in Computer Science},202 volume = {950},203 publisher = {Springer},204 year = {1995},205 pages = {77--85},206 doi = {10.1007/BFb0053426}207}208209@incollection{bellare1998fast,210 author = {Bellare, Mihir and Garay, Juan A. and Rabin, Tal},211 title = {Fast Batch Verification for Modular Exponentiation and Digital Signatures},212 booktitle = {Advances in Cryptology --- EUROCRYPT '98},213 series = {Lecture Notes in Computer Science},214 volume = {1403},215 publisher = {Springer},216 year = {1998},217 pages = {236--250},218 doi = {10.1007/BFb0054130}219}220221@incollection{shanks1971class,222 author = {Shanks, Daniel},223 title = {Class Number, a Theory of Factorization, and Genera},224 booktitle = {1969 Number Theory Institute},225 series = {Proceedings of Symposia in Pure Mathematics},226 volume = {20},227 publisher = {American Mathematical Society},228 year = {1971},229 pages = {415--440},230 doi = {10.1090/pspum/020/0316385}231}232233@article{pollard1978monte,234 author = {Pollard, John M.},235 title = {Monte {C}arlo Methods for Index Computation (mod $p$)},236 journal = {Mathematics of Computation},237 year = {1978},238 volume = {32},239 number = {143},240 pages = {918--924},241 doi = {10.1090/S0025-5718-1978-0491431-9}242}243244@article{pollard2000kangaroos,245 author = {Pollard, John M.},246 title = {Kangaroos, {M}onopoly and Discrete Logarithms},247 journal = {Journal of Cryptology},248 year = {2000},249 volume = {13},250 number = {4},251 pages = {437--447},252 doi = {10.1007/s001450010010}253}254255@article{vanoorschot1999parallel,256 author = {van Oorschot, Paul C. and Wiener, Michael J.},257 title = {Parallel Collision Search with Cryptanalytic Applications},258 journal = {Journal of Cryptology},259 year = {1999},260 volume = {12},261 number = {1},262 pages = {1--28},263 doi = {10.1007/PL00003816}264}265266@incollection{teske1998speeding,267 author = {Teske, Edlyn},268 title = {Speeding up {P}ollard's Rho Method for Computing Discrete Logarithms},269 booktitle = {Algorithmic Number Theory --- ANTS-III},270 series = {Lecture Notes in Computer Science},271 volume = {1423},272 publisher = {Springer},273 year = {1998},274 pages = {541--554},275 doi = {10.1007/BFb0054891}276}277278@article{teske2001random,279 author = {Teske, Edlyn},280 title = {On Random Walks for {P}ollard's Rho Method},281 journal = {Mathematics of Computation},282 year = {2001},283 volume = {70},284 number = {234},285 pages = {809--825},286 doi = {10.1090/S0025-5718-00-01213-8}287}288289@article{brent1980improved,290 author = {Brent, Richard P.},291 title = {An Improved {M}onte {C}arlo Factorization Algorithm},292 journal = {BIT Numerical Mathematics},293 year = {1980},294 volume = {20},295 number = {2},296 pages = {176--184},297 doi = {10.1007/BF01933190}298}299300@incollection{flajolet1990random,301 author = {Flajolet, Philippe and Odlyzko, Andrew M.},302 title = {Random Mapping Statistics},303 booktitle = {Advances in Cryptology --- EUROCRYPT '89},304 series = {Lecture Notes in Computer Science},305 volume = {434},306 publisher = {Springer},307 year = {1990},308 pages = {329--354},309 doi = {10.1007/3-540-46885-4_34}310}311312@incollection{shoup1997lower,313 author = {Shoup, Victor},314 title = {Lower Bounds for Discrete Logarithms and Related Problems},315 booktitle = {Advances in Cryptology --- EUROCRYPT '97},316 series = {Lecture Notes in Computer Science},317 volume = {1233},318 publisher = {Springer},319 year = {1997},320 pages = {256--266},321 doi = {10.1007/3-540-69053-0_18}322}323324@article{nechaev1994complexity,325 author = {Nechaev, Vassiliy I.},326 title = {Complexity of a Determinate Algorithm for the Discrete Logarithm},327 journal = {Mathematical Notes},328 year = {1994},329 volume = {55},330 number = {2},331 pages = {165--172},332 doi = {10.1007/BF02113297}333}334335@article{gallant2000improving,336 author = {Gallant, Robert and Lambert, Robert and Vanstone, Scott},337 title = {Improving the Parallelized {P}ollard Lambda Search on Anomalous Binary Curves},338 journal = {Mathematics of Computation},339 year = {2000},340 volume = {69},341 number = {232},342 pages = {1699--1705},343 doi = {10.1090/S0025-5718-99-01119-9}344}345346@incollection{wiener1999faster,347 author = {Wiener, Michael J. and Zuccherato, Robert J.},348 title = {Faster Attacks on Elliptic Curve Cryptosystems},349 booktitle = {Selected Areas in Cryptography --- SAC '98},350 series = {Lecture Notes in Computer Science},351 volume = {1556},352 publisher = {Springer},353 year = {1999},354 pages = {190--200},355 doi = {10.1007/3-540-48892-8_15}356}357358@incollection{duursma1999speeding,359 author = {Duursma, Iwan and Gaudry, Pierrick and Morain, Fran{\c{c}}ois},360 title = {Speeding up the Discrete Log Computation on Curves with Automorphisms},361 booktitle = {Advances in Cryptology --- ASIACRYPT '99},362 series = {Lecture Notes in Computer Science},363 volume = {1716},364 publisher = {Springer},365 year = {1999},366 pages = {103--121},367 doi = {10.1007/978-3-540-48000-6_10}368}369370@incollection{bos2010negation,371 author = {Bos, Joppe W. and Kleinjung, Thorsten and Lenstra, Arjen K.},372 title = {On the Use of the Negation Map in the {P}ollard Rho Method},373 booktitle = {Algorithmic Number Theory --- ANTS-IX},374 series = {Lecture Notes in Computer Science},375 volume = {6197},376 publisher = {Springer},377 year = {2010},378 pages = {66--82},379 doi = {10.1007/978-3-642-14518-6_9}380}381382@incollection{bernstein2011correct,383 author = {Bernstein, Daniel J. and Lange, Tanja and Schwabe, Peter},384 title = {On the Correct Use of the Negation Map in the {P}ollard Rho Method},385 booktitle = {Public Key Cryptography --- PKC 2011},386 series = {Lecture Notes in Computer Science},387 volume = {6571},388 publisher = {Springer},389 year = {2011},390 pages = {128--146},391 doi = {10.1007/978-3-642-19379-8_8}392}393394@incollection{bernstein2013nonuniform,395 author = {Bernstein, Daniel J. and Lange, Tanja},396 title = {Non-uniform Cracks in the Concrete: The Power of Free Precomputation},397 booktitle = {Advances in Cryptology --- ASIACRYPT 2013},398 series = {Lecture Notes in Computer Science},399 volume = {8270},400 publisher = {Springer},401 year = {2013},402 pages = {321--340},403 doi = {10.1007/978-3-642-42045-0_17},404 note = {Full version: IACR Cryptology ePrint Archive, Report 2012/318}405}406407@incollection{corrigangibbs2018discrete,408 author = {Corrigan-Gibbs, Henry and Kogan, Dmitry},409 title = {The Discrete-Logarithm Problem with Preprocessing},410 booktitle = {Advances in Cryptology --- EUROCRYPT 2018},411 series = {Lecture Notes in Computer Science},412 volume = {10821},413 publisher = {Springer},414 year = {2018},415 pages = {415--447},416 doi = {10.1007/978-3-319-78375-8_14},417 note = {Full version: IACR Cryptology ePrint Archive, Report 2017/1113}418}419420@misc{lee2011generic,421 author = {Lee, Hyung Tae and Cheon, Jung Hee and Hong, Jin},422 title = {Accelerating {ID}-based Encryption Based on Trapdoor {DL} Using Pre-computation},423 howpublished = {IACR Cryptology ePrint Archive, Report 2011/187},424 year = {2011},425 url = {https://eprint.iacr.org/2011/187},426 note = {Discrete-logarithm computation with precomputation (preprocessing) in a fixed group}427}428429@article{bernstein2012two,430 author = {Bernstein, Daniel J. and Lange, Tanja},431 title = {Two Grumpy Giants and a Baby},432 journal = {The Open Book Series},433 year = {2013},434 volume = {1},435 number = {1},436 pages = {87--111},437 doi = {10.2140/obs.2013.1.87},438 note = {Proceedings of ANTS X (2012)}439}440441@incollection{galbraith2010interval,442 author = {Galbraith, Steven D. and Ruprai, Raminder S.},443 title = {Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval},444 booktitle = {Public Key Cryptography --- PKC 2010},445 series = {Lecture Notes in Computer Science},446 volume = {6056},447 publisher = {Springer},448 year = {2010},449 pages = {368--383},450 doi = {10.1007/978-3-642-13013-7_22}451}452453@article{galbraith2016recent,454 author = {Galbraith, Steven D. and Gaudry, Pierrick},455 title = {Recent Progress on the Elliptic Curve Discrete Logarithm Problem},456 journal = {Designs, Codes and Cryptography},457 year = {2016},458 volume = {78},459 number = {1},460 pages = {51--72},461 doi = {10.1007/s10623-015-0146-7}462}463464@article{pohlig1978improved,465 author = {Pohlig, Stephen C. and Hellman, Martin E.},466 title = {An Improved Algorithm for Computing Logarithms over {GF}($p$) and Its Cryptographic Significance},467 journal = {IEEE Transactions on Information Theory},468 year = {1978},469 volume = {24},470 number = {1},471 pages = {106--110},472 doi = {10.1109/TIT.1978.1055817}473}474475@article{menezes1993reducing,476 author = {Menezes, Alfred J. and Okamoto, Tatsuaki and Vanstone, Scott A.},477 title = {Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field},478 journal = {IEEE Transactions on Information Theory},479 year = {1993},480 volume = {39},481 number = {5},482 pages = {1639--1646},483 doi = {10.1109/18.259647}484}485486@article{frey1994remark,487 author = {Frey, Gerhard and R{\"u}ck, Hans-Georg},488 title = {A Remark Concerning $m$-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves},489 journal = {Mathematics of Computation},490 year = {1994},491 volume = {62},492 number = {206},493 pages = {865--874},494 doi = {10.1090/S0025-5718-1994-1218343-6}495}496497@article{semaev1998evaluation,498 author = {Semaev, Igor A.},499 title = {Evaluation of Discrete Logarithms in a Group of $p$-Torsion Points of an Elliptic Curve in Characteristic $p$},500 journal = {Mathematics of Computation},501 year = {1998},502 volume = {67},503 number = {221},504 pages = {353--356},505 doi = {10.1090/S0025-5718-98-00887-4}506}507508@article{smart1999discrete,509 author = {Smart, Nigel P.},510 title = {The Discrete Logarithm Problem on Elliptic Curves of Trace One},511 journal = {Journal of Cryptology},512 year = {1999},513 volume = {12},514 number = {3},515 pages = {193--196},516 doi = {10.1007/s001459900052}517}518519@article{satoh1998fermat,520 author = {Satoh, Takakazu and Araki, Kiyomichi},521 title = {Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curves},522 journal = {Commentarii Mathematici Universitatis Sancti Pauli},523 year = {1998},524 volume = {47},525 number = {1},526 pages = {81--92},527 note = {Errata: same journal 48 (1999), no. 2, 211--213. No DOI; bibliographic data confirmed through citing sources}528}529530@misc{semaev2004summation,531 author = {Semaev, Igor},532 title = {Summation Polynomials and the Discrete Logarithm Problem on Elliptic Curves},533 howpublished = {IACR Cryptology ePrint Archive, Report 2004/031},534 year = {2004},535 url = {https://eprint.iacr.org/2004/031}536}537538@article{gaudry2009index,539 author = {Gaudry, Pierrick},540 title = {Index Calculus for Abelian Varieties of Small Dimension and the Elliptic Curve Discrete Logarithm Problem},541 journal = {Journal of Symbolic Computation},542 year = {2009},543 volume = {44},544 number = {12},545 pages = {1690--1702},546 doi = {10.1016/j.jsc.2008.08.005}547}548549@article{diem2011discrete,550 author = {Diem, Claus},551 title = {On the Discrete Logarithm Problem in Elliptic Curves},552 journal = {Compositio Mathematica},553 year = {2011},554 volume = {147},555 number = {1},556 pages = {75--104},557 doi = {10.1112/S0010437X10005075}558}559560@incollection{petit2012elliptic,561 author = {Petit, Christophe and Quisquater, Jean-Jacques},562 title = {On Polynomial Systems Arising from a {W}eil Descent},563 booktitle = {Advances in Cryptology --- ASIACRYPT 2012},564 series = {Lecture Notes in Computer Science},565 volume = {7658},566 publisher = {Springer},567 year = {2012},568 pages = {451--466},569 doi = {10.1007/978-3-642-34961-4_28}570}571572@article{bos2012solving,573 author = {Bos, Joppe W. and Kaihara, Marcelo E. and Kleinjung, Thorsten and Lenstra, Arjen K. and Montgomery, Peter L.},574 title = {Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles Using Sloppy Reduction},575 journal = {International Journal of Applied Cryptography},576 year = {2012},577 volume = {2},578 number = {3},579 pages = {212--228},580 doi = {10.1504/IJACT.2012.045590}581}582583@incollection{wenger2014solving,584 author = {Wenger, Erich and Wolfger, Paul},585 title = {Solving the Discrete Logarithm of a 113-bit {K}oblitz Curve with an {FPGA} Cluster},586 booktitle = {Selected Areas in Cryptography --- SAC 2014},587 series = {Lecture Notes in Computer Science},588 volume = {8781},589 publisher = {Springer},590 year = {2014},591 pages = {363--379},592 doi = {10.1007/978-3-319-13051-4_22},593 note = {Also IACR Cryptology ePrint Archive, Report 2014/368}594}595596@article{wenger2016harder,597 author = {Wenger, Erich and Wolfger, Paul},598 title = {Harder, Better, Faster, Stronger: Elliptic Curve Discrete Logarithm Computations on {FPGAs}},599 journal = {Journal of Cryptographic Engineering},600 year = {2016},601 volume = {6},602 number = {4},603 pages = {287--297},604 doi = {10.1007/s13389-015-0108-z},605 note = {Also IACR Cryptology ePrint Archive, Report 2015/143}606}607608@misc{bernstein2016faster,609 author = {Bernstein, Daniel J. and Engels, Susanne and Lange, Tanja and Niederhagen, Ruben and Paar, Christof and Schwabe, Peter and Zimmermann, Ralf},610 title = {Faster Elliptic-Curve Discrete Logarithms on {FPGAs}},611 howpublished = {IACR Cryptology ePrint Archive, Report 2016/382},612 year = {2016},613 url = {https://eprint.iacr.org/2016/382}614}615616@techreport{certicom2009challenge,617 author = {{Certicom Research}},618 title = {Certicom {ECC} Challenge},619 institution = {Certicom Corp.},620 year = {2009},621 note = {Original date November 6, 1997; latest update November 10, 2009},622 url = {https://www.certicom.com/content/dam/certicom/images/pdfs/challenge-2009.pdf}623}624625@article{shor1997polynomial,626 author = {Shor, Peter W.},627 title = {Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer},628 journal = {SIAM Journal on Computing},629 year = {1997},630 volume = {26},631 number = {5},632 pages = {1484--1509},633 doi = {10.1137/S0097539795293172}634}635636@incollection{roetteler2017quantum,637 author = {Roetteler, Martin and Naehrig, Michael and Svore, Krysta M. and Lauter, Kristin},638 title = {Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms},639 booktitle = {Advances in Cryptology --- ASIACRYPT 2017},640 series = {Lecture Notes in Computer Science},641 volume = {10625},642 publisher = {Springer},643 year = {2017},644 pages = {241--270},645 doi = {10.1007/978-3-319-70697-9_9}646}647648@article{schnorr1991efficient,649 author = {Schnorr, Claus-Peter},650 title = {Efficient Signature Generation by Smart Cards},651 journal = {Journal of Cryptology},652 year = {1991},653 volume = {4},654 number = {3},655 pages = {161--174},656 doi = {10.1007/BF00196725}657}658659@article{pointcheval2000security,660 author = {Pointcheval, David and Stern, Jacques},661 title = {Security Arguments for Digital Signatures and Blind Signatures},662 journal = {Journal of Cryptology},663 year = {2000},664 volume = {13},665 number = {3},666 pages = {361--396},667 doi = {10.1007/s001450010003}668}669670@incollection{seurin2012exact,671 author = {Seurin, Yannick},672 title = {On the Exact Security of {S}chnorr-Type Signatures in the Random Oracle Model},673 booktitle = {Advances in Cryptology --- EUROCRYPT 2012},674 series = {Lecture Notes in Computer Science},675 volume = {7237},676 publisher = {Springer},677 year = {2012},678 pages = {554--571},679 doi = {10.1007/978-3-642-29011-4_33}680}681682@incollection{paillier2005discrete,683 author = {Paillier, Pascal and Vergnaud, Damien},684 title = {Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log},685 booktitle = {Advances in Cryptology --- ASIACRYPT 2005},686 series = {Lecture Notes in Computer Science},687 volume = {3788},688 publisher = {Springer},689 year = {2005},690 pages = {1--20},691 doi = {10.1007/11593447_1}692}693694@article{brown2005generic,695 author = {Brown, Daniel R. L.},696 title = {Generic Groups, Collision Resistance, and {ECDSA}},697 journal = {Designs, Codes and Cryptography},698 year = {2005},699 volume = {35},700 number = {1},701 pages = {119--152},702 doi = {10.1007/s10623-003-6154-z}703}704705@incollection{vaudenay2003security,706 author = {Vaudenay, Serge},707 title = {The Security of {DSA} and {ECDSA}},708 booktitle = {Public Key Cryptography --- PKC 2003},709 series = {Lecture Notes in Computer Science},710 volume = {2567},711 publisher = {Springer},712 year = {2003},713 pages = {309--323},714 doi = {10.1007/3-540-36288-6_23}715}716717@inproceedings{fersch2016provable,718 author = {Fersch, Manuel and Kiltz, Eike and Poettering, Bertram},719 title = {On the Provable Security of {(EC)DSA} Signatures},720 booktitle = {Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 2016)},721 publisher = {ACM},722 year = {2016},723 pages = {1651--1662},724 doi = {10.1145/2976749.2978413}725}726727@incollection{fersch2017one,728 author = {Fersch, Manuel and Kiltz, Eike and Poettering, Bertram},729 title = {On the One-Per-Message Unforgeability of {(EC)DSA} and Its Variants},730 booktitle = {Theory of Cryptography --- TCC 2017},731 series = {Lecture Notes in Computer Science},732 volume = {10678},733 publisher = {Springer},734 year = {2017},735 pages = {519--534},736 doi = {10.1007/978-3-319-70503-3_17}737}738739@incollection{groth2022security,740 author = {Groth, Jens and Shoup, Victor},741 title = {On the Security of {ECDSA} with Additive Key Derivation and Presignatures},742 booktitle = {Advances in Cryptology --- EUROCRYPT 2022},743 series = {Lecture Notes in Computer Science},744 volume = {13276},745 publisher = {Springer},746 year = {2022},747 pages = {365--396},748 doi = {10.1007/978-3-031-06944-4_13}749}750751@article{howgravegraham2001lattice,752 author = {Howgrave-Graham, Nick A. and Smart, Nigel P.},753 title = {Lattice Attacks on Digital Signature Schemes},754 journal = {Designs, Codes and Cryptography},755 year = {2001},756 volume = {23},757 number = {3},758 pages = {283--290},759 doi = {10.1023/A:1011214926272}760}761762@incollection{breitner2019biased,763 author = {Breitner, Joachim and Heninger, Nadia},764 title = {Biased Nonce Sense: Lattice Attacks Against Weak {ECDSA} Signatures in Cryptocurrencies},765 booktitle = {Financial Cryptography and Data Security --- FC 2019},766 series = {Lecture Notes in Computer Science},767 volume = {11598},768 publisher = {Springer},769 year = {2019},770 pages = {3--20},771 doi = {10.1007/978-3-030-32101-7_1}772}773774@inproceedings{bellare2006multi,775 author = {Bellare, Mihir and Neven, Gregory},776 title = {Multi-signatures in the Plain Public-Key Model and a General Forking Lemma},777 booktitle = {Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006)},778 publisher = {ACM},779 year = {2006},780 pages = {390--399},781 doi = {10.1145/1180405.1180453}782}783784@article{maxwell2019simple,785 author = {Maxwell, Gregory and Poelstra, Andrew and Seurin, Yannick and Wuille, Pieter},786 title = {Simple {S}chnorr Multi-Signatures with Applications to {B}itcoin},787 journal = {Designs, Codes and Cryptography},788 year = {2019},789 volume = {87},790 number = {9},791 pages = {2139--2164},792 doi = {10.1007/s10623-019-00608-x}793}794795@incollection{nick2021musig2,796 author = {Nick, Jonas and Ruffing, Tim and Seurin, Yannick},797 title = {{MuSig2}: Simple Two-Round {S}chnorr Multi-signatures},798 booktitle = {Advances in Cryptology --- CRYPTO 2021},799 series = {Lecture Notes in Computer Science},800 volume = {12825},801 publisher = {Springer},802 year = {2021},803 pages = {189--221},804 doi = {10.1007/978-3-030-84242-0_8}805}806807@incollection{kocher1996timing,808 author = {Kocher, Paul C.},809 title = {Timing Attacks on Implementations of {D}iffie-{H}ellman, {RSA}, {DSS}, and Other Systems},810 booktitle = {Advances in Cryptology --- CRYPTO '96},811 series = {Lecture Notes in Computer Science},812 volume = {1109},813 publisher = {Springer},814 year = {1996},815 pages = {104--113},816 doi = {10.1007/3-540-68697-5_9}817}818819@incollection{brumley2011remote,820 author = {Brumley, Billy Bob and Tuveri, Nicola},821 title = {Remote Timing Attacks Are Still Practical},822 booktitle = {Computer Security --- ESORICS 2011},823 series = {Lecture Notes in Computer Science},824 volume = {6879},825 publisher = {Springer},826 year = {2011},827 pages = {355--371},828 doi = {10.1007/978-3-642-23822-2_20}829}830831@inproceedings{aldaya2020ladderleak,832 author = {Aranha, Diego F. and Novaes, Felipe Rodrigues and Takahashi, Akira and Tibouchi, Mehdi and Yarom, Yuval},833 title = {{LadderLeak}: Breaking {ECDSA} with Less than One Bit of Nonce Leakage},834 booktitle = {Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS 2020)},835 publisher = {ACM},836 year = {2020},837 pages = {225--242},838 doi = {10.1145/3372297.3417268}839}840841@article{jancar2020minerva,842 author = {Jan{\v{c}}ar, J{\'a}n and Sedl{\'a}{\v{c}}ek, Vladim{\'i}r and {\v{S}}venda, Petr and S{\'y}s, Marek},843 title = {Minerva: The Curse of {ECDSA} Nonces},844 journal = {IACR Transactions on Cryptographic Hardware and Embedded Systems},845 year = {2020},846 volume = {2020},847 number = {4},848 pages = {281--308},849 doi = {10.46586/tches.v2020.i4.281-308}850}851852@techreport{pornin2013rfc6979,853 author = {Pornin, Thomas},854 title = {Deterministic Usage of the Digital Signature Algorithm ({DSA}) and Elliptic Curve Digital Signature Algorithm ({ECDSA})},855 institution = {Internet Engineering Task Force},856 type = {RFC},857 number = {6979},858 year = {2013},859 doi = {10.17487/RFC6979},860 url = {https://www.rfc-editor.org/rfc/rfc6979}861}862863@misc{wuille2020bip340,864 author = {Wuille, Pieter and Nick, Jonas and Ruffing, Tim},865 title = {{BIP} 340: {S}chnorr Signatures for secp256k1},866 howpublished = {Bitcoin Improvement Proposal 340},867 year = {2020},868 url = {https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki},869 note = {Status: Deployed; type: Specification; assigned 2020-01-19}870}871872@misc{wuille2020bip341,873 author = {Wuille, Pieter and Nick, Jonas and Towns, Anthony},874 title = {{BIP} 341: {T}aproot: {S}eg{W}it Version 1 Spending Rules},875 howpublished = {Bitcoin Improvement Proposal 341},876 year = {2020},877 url = {https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki},878 note = {Status: Deployed; consensus layer (soft fork); requires BIP 340}879}880881@misc{nakamoto2008bitcoin,882 author = {Nakamoto, Satoshi},883 title = {Bitcoin: A Peer-to-Peer Electronic Cash System},884 howpublished = {White paper},885 year = {2008},886 url = {https://bitcoin.org/bitcoin.pdf}887}888889@misc{wuille2013libsecp256k1,890 author = {Wuille, Pieter and Maxwell, Gregory and Nick, Jonas and Ruffing, Tim and others},891 title = {libsecp256k1: Optimized {C} Library for {ECDSA} and {BIP}-340 Signatures on Curve secp256k1},892 howpublished = {Software, Bitcoin Core project, GitHub},893 year = {2024},894 url = {https://github.com/bitcoin-core/secp256k1},895 note = {The GLV endomorphism $\lambda\cdot(x,y)=(\beta x,y)$ and the scalar split are implemented in \texttt{src/scalar\_impl.h}; accessed 2026-11-01}896}897898@techreport{certicom2009sec1,899 author = {{Certicom Research}},900 title = {{SEC} 1: Elliptic Curve Cryptography, Version 2.0},901 institution = {Standards for Efficient Cryptography Group},902 year = {2009},903 month = may,904 note = {May 21, 2009},905 url = {https://www.secg.org/sec1-v2.pdf}906}907908@techreport{certicom2010sec2,909 author = {{Certicom Research}},910 title = {{SEC} 2: Recommended Elliptic Curve Domain Parameters, Version 2.0},911 institution = {Standards for Efficient Cryptography Group},912 year = {2010},913 month = jan,914 note = {January 27, 2010},915 url = {https://www.secg.org/sec2-v2.pdf}916}917918@techreport{nist2023fips186,919 author = {{National Institute of Standards and Technology}},920 title = {Digital Signature Standard ({DSS})},921 institution = {U.S. Department of Commerce},922 type = {Federal Information Processing Standards Publication},923 number = {FIPS 186-5},924 year = {2023},925 month = feb,926 doi = {10.6028/NIST.FIPS.186-5}927}928929@techreport{nist2015fips180,930 author = {{National Institute of Standards and Technology}},931 title = {Secure Hash Standard ({SHS})},932 institution = {U.S. Department of Commerce},933 type = {Federal Information Processing Standards Publication},934 number = {FIPS 180-4},935 year = {2015},936 month = aug,937 doi = {10.6028/NIST.FIPS.180-4}938}939940@misc{bernstein2014safecurves,941 author = {Bernstein, Daniel J. and Lange, Tanja},942 title = {{SafeCurves}: Choosing Safe Curves for Elliptic-Curve Cryptography},943 howpublished = {Web page},944 year = {2014},945 url = {https://safecurves.cr.yp.to},946 note = {Accessed 2026-11-01}947}948949@incollection{merkle1989one,950 author = {Merkle, Ralph C.},951 title = {One Way Hash Functions and {DES}},952 booktitle = {Advances in Cryptology --- CRYPTO '89},953 series = {Lecture Notes in Computer Science},954 volume = {435},955 publisher = {Springer},956 year = {1990},957 pages = {428--446},958 doi = {10.1007/0-387-34805-0_40}959}960961@incollection{damgard1989design,962 author = {Damg{\aa}rd, Ivan Bjerre},963 title = {A Design Principle for Hash Functions},964 booktitle = {Advances in Cryptology --- CRYPTO '89},965 series = {Lecture Notes in Computer Science},966 volume = {435},967 publisher = {Springer},968 year = {1990},969 pages = {416--427},970 doi = {10.1007/0-387-34805-0_39}971}972973@incollection{chabaud1998differential,974 author = {Chabaud, Florent and Joux, Antoine},975 title = {Differential Collisions in {SHA-0}},976 booktitle = {Advances in Cryptology --- CRYPTO '98},977 series = {Lecture Notes in Computer Science},978 volume = {1462},979 publisher = {Springer},980 year = {1998},981 pages = {56--71},982 doi = {10.1007/BFb0055720}983}984985@incollection{gilbert2003security,986 author = {Gilbert, Henri and Handschuh, Helena},987 title = {Security Analysis of {SHA-256} and Sisters},988 booktitle = {Selected Areas in Cryptography --- SAC 2003},989 series = {Lecture Notes in Computer Science},990 volume = {3006},991 publisher = {Springer},992 year = {2004},993 pages = {175--193},994 doi = {10.1007/978-3-540-24654-1_13}995}996997@incollection{wang2005finding,998 author = {Wang, Xiaoyun and Yin, Yiqun Lisa and Yu, Hongbo},999 title = {Finding Collisions in the Full {SHA-1}},1000 booktitle = {Advances in Cryptology --- CRYPTO 2005},1001 series = {Lecture Notes in Computer Science},1002 volume = {3621},1003 publisher = {Springer},1004 year = {2005},1005 pages = {17--36},1006 doi = {10.1007/11535218_2}1007}10081009@incollection{stevens2017first,1010 author = {Stevens, Marc and Bursztein, Elie and Karpman, Pierre and Albertini, Ange and Markov, Yarik},1011 title = {The First Collision for Full {SHA-1}},1012 booktitle = {Advances in Cryptology --- CRYPTO 2017},1013 series = {Lecture Notes in Computer Science},1014 volume = {10401},1015 publisher = {Springer},1016 year = {2017},1017 pages = {570--596},1018 doi = {10.1007/978-3-319-63688-7_19}1019}10201021@inproceedings{leurent2020sha1,1022 author = {Leurent, Ga{\"e}tan and Peyrin, Thomas},1023 title = {{SHA-1} is a Shambles: First Chosen-Prefix Collision on {SHA-1} and Application to the {PGP} Web of Trust},1024 booktitle = {29th USENIX Security Symposium (USENIX Security 20)},1025 publisher = {USENIX Association},1026 year = {2020},1027 url = {https://www.usenix.org/conference/usenixsecurity20/presentation/leurent},1028 note = {Also IACR Cryptology ePrint Archive, Report 2020/014}1029}10301031@incollection{nikolic2008collisions,1032 author = {Nikoli{\'c}, Ivica and Biryukov, Alex},1033 title = {Collisions for Step-Reduced {SHA-256}},1034 booktitle = {Fast Software Encryption --- FSE 2008},1035 series = {Lecture Notes in Computer Science},1036 volume = {5086},1037 publisher = {Springer},1038 year = {2008},1039 pages = {1--15},1040 doi = {10.1007/978-3-540-71039-4_1}1041}10421043@incollection{indesteege2008collisions,1044 author = {Indesteege, Sebastiaan and Mendel, Florian and Preneel, Bart and Rechberger, Christian},1045 title = {Collisions and Other Non-random Properties for Step-Reduced {SHA-256}},1046 booktitle = {Selected Areas in Cryptography --- SAC 2008},1047 series = {Lecture Notes in Computer Science},1048 volume = {5381},1049 publisher = {Springer},1050 year = {2009},1051 pages = {276--293},1052 doi = {10.1007/978-3-642-04159-4_18},1053 note = {Also IACR Cryptology ePrint Archive, Report 2008/131}1054}10551056@incollection{sanadhya2008new,1057 author = {Sanadhya, Somitra Kumar and Sarkar, Palash},1058 title = {New Collision Attacks against Up to 24-Step {SHA-2}},1059 booktitle = {Progress in Cryptology --- INDOCRYPT 2008},1060 series = {Lecture Notes in Computer Science},1061 volume = {5365},1062 publisher = {Springer},1063 year = {2008},1064 pages = {91--103},1065 doi = {10.1007/978-3-540-89754-5_8},1066 note = {Also IACR Cryptology ePrint Archive, Report 2008/270}1067}10681069@incollection{mendel2011finding,1070 author = {Mendel, Florian and Nad, Tomislav and Schl{\"a}ffer, Martin},1071 title = {Finding {SHA-2} Characteristics: Searching through a Minefield of Contradictions},1072 booktitle = {Advances in Cryptology --- ASIACRYPT 2011},1073 series = {Lecture Notes in Computer Science},1074 volume = {7073},1075 publisher = {Springer},1076 year = {2011},1077 pages = {288--307},1078 doi = {10.1007/978-3-642-25385-0_16}1079}10801081@incollection{mendel2013improving,1082 author = {Mendel, Florian and Nad, Tomislav and Schl{\"a}ffer, Martin},1083 title = {Improving Local Collisions: New Attacks on Reduced {SHA-256}},1084 booktitle = {Advances in Cryptology --- EUROCRYPT 2013},1085 series = {Lecture Notes in Computer Science},1086 volume = {7881},1087 publisher = {Springer},1088 year = {2013},1089 pages = {262--278},1090 doi = {10.1007/978-3-642-38348-9_16},1091 note = {Also IACR Cryptology ePrint Archive, Report 2015/350}1092}10931094@incollection{eichlseder2014branching,1095 author = {Eichlseder, Maria and Mendel, Florian and Schl{\"a}ffer, Martin},1096 title = {Branching Heuristics in Differential Collision Search with Applications to {SHA-512}},1097 booktitle = {Fast Software Encryption --- FSE 2014},1098 series = {Lecture Notes in Computer Science},1099 volume = {8540},1100 publisher = {Springer},1101 year = {2015},1102 pages = {473--488},1103 doi = {10.1007/978-3-662-46706-0_24},1104 note = {Also IACR Cryptology ePrint Archive, Report 2014/302}1105}11061107@incollection{dobraunig2015analysis,1108 author = {Dobraunig, Christoph and Eichlseder, Maria and Mendel, Florian},1109 title = {Analysis of {SHA-512/224} and {SHA-512/256}},1110 booktitle = {Advances in Cryptology --- ASIACRYPT 2015},1111 series = {Lecture Notes in Computer Science},1112 volume = {9453},1113 publisher = {Springer},1114 year = {2015},1115 pages = {612--630},1116 doi = {10.1007/978-3-662-48800-3_25},1117 note = {Also IACR Cryptology ePrint Archive, Report 2016/374}1118}11191120@incollection{li2024new,1121 author = {Li, Yingxin and Liu, Fukang and Wang, Gaoli},1122 title = {New Records in Collision Attacks on {SHA-2}},1123 booktitle = {Advances in Cryptology --- EUROCRYPT 2024},1124 series = {Lecture Notes in Computer Science},1125 volume = {14654},1126 publisher = {Springer},1127 year = {2024},1128 pages = {158--186},1129 doi = {10.1007/978-3-031-58716-0_6},1130 note = {Also IACR Cryptology ePrint Archive, Report 2024/349; extended journal version in Journal of Cryptology 39 (2026), article 27, doi:10.1007/s00145-026-09582-9}1131}11321133@incollection{li2024first,1134 author = {Li, Yingxin and Liu, Fukang and Wang, Gaoli and Dong, Xiaoyang and Sun, Siwei},1135 title = {The First Practical Collision for 31-Step {SHA-256}},1136 booktitle = {Advances in Cryptology --- ASIACRYPT 2024},1137 series = {Lecture Notes in Computer Science},1138 publisher = {Springer},1139 year = {2024},1140 pages = {237--266},1141 doi = {10.1007/978-981-96-0941-3_8}1142}11431144@misc{zhang2026collision,1145 author = {Zhang, Zhuolong and Li, Muzhou and Gao, Lei and Wang, Meiqin},1146 title = {Collision Attacks on {SHA-256} up to 37 Steps with Improved Trail Search},1147 howpublished = {IACR Cryptology ePrint Archive, Report 2026/232},1148 year = {2026},1149 url = {https://eprint.iacr.org/2026/232}1150}11511152@incollection{aoki2009preimages,1153 author = {Aoki, Kazumaro and Guo, Jian and Matusiewicz, Krystian and Sasaki, Yu and Wang, Lei},1154 title = {Preimages for Step-Reduced {SHA-2}},1155 booktitle = {Advances in Cryptology --- ASIACRYPT 2009},1156 series = {Lecture Notes in Computer Science},1157 volume = {5912},1158 publisher = {Springer},1159 year = {2009},1160 pages = {578--597},1161 doi = {10.1007/978-3-642-10366-7_34}1162}11631164@incollection{khovratovich2012bicliques,1165 author = {Khovratovich, Dmitry and Rechberger, Christian and Savelieva, Alexandra},1166 title = {Bicliques for Preimages: Attacks on {Skein-512} and the {SHA-2} Family},1167 booktitle = {Fast Software Encryption --- FSE 2012},1168 series = {Lecture Notes in Computer Science},1169 volume = {7549},1170 publisher = {Springer},1171 year = {2012},1172 pages = {244--263},1173 doi = {10.1007/978-3-642-34047-5_15},1174 note = {Also IACR Cryptology ePrint Archive, Report 2011/286}1175}11761177@incollection{mironov2006applications,1178 author = {Mironov, Ilya and Zhang, Lintao},1179 title = {Applications of {SAT} Solvers to Cryptanalysis of Hash Functions},1180 booktitle = {Theory and Applications of Satisfiability Testing --- SAT 2006},1181 series = {Lecture Notes in Computer Science},1182 volume = {4121},1183 publisher = {Springer},1184 year = {2006},1185 pages = {102--115},1186 doi = {10.1007/11814948_13}1187}11881189@incollection{nejati2017adaptive,1190 author = {Nejati, Saeed and Liang, Jia Hui and Gebotys, Catherine and Czarnecki, Krzysztof and Ganesh, Vijay},1191 title = {Adaptive Restart and {CEGAR}-Based Solver for Inverting Cryptographic Hash Functions},1192 booktitle = {Verified Software: Theories, Tools, and Experiments --- VSTTE 2017},1193 series = {Lecture Notes in Computer Science},1194 volume = {10712},1195 publisher = {Springer},1196 year = {2017},1197 pages = {120--131},1198 doi = {10.1007/978-3-319-72308-2_8}1199}12001201@inproceedings{alamgir2024sha256,1202 author = {Alamgir, Nahiyan and Nejati, Saeed and Bright, Curtis},1203 title = {{SHA-256} Collision Attack with Programmatic {SAT}},1204 booktitle = {Joint Proceedings of the 9th Workshop on Practical Aspects of Automated Reasoning (PAAR) and the 9th Satisfiability Checking and Symbolic Computation Workshop (SC-Square)},1205 series = {CEUR Workshop Proceedings},1206 volume = {3717},1207 publisher = {CEUR-WS.org},1208 year = {2024},1209 pages = {91--110},1210 url = {https://ceur-ws.org/Vol-3717/},1211 note = {Also arXiv:2406.20072}1212}12131214@inproceedings{biere2020cadical,1215 author = {Biere, Armin and Fazekas, Katalin and Fleury, Mathias and Heisinger, Maximilian},1216 title = {{CaDiCaL}, {Kissat}, {Paracooba}, {Plingeling} and {Treengeling} Entering the {SAT} Competition 2020},1217 booktitle = {Proceedings of SAT Competition 2020 --- Solver and Benchmark Descriptions},1218 editor = {Balyo, Tomas and Froleyks, Nils and Heule, Marijn and Iser, Markus and J{\"a}rvisalo, Matti and Suda, Martin},1219 series = {Department of Computer Science Report Series B},1220 volume = {B-2020-1},1221 publisher = {University of Helsinki},1222 year = {2020},1223 pages = {50--53}1224}12251226@incollection{biere2024cadical,1227 author = {Biere, Armin and Faller, Tobias and Fazekas, Katalin and Fleury, Mathias and Froleyks, Nils and Pollitt, Florian},1228 title = {{CaDiCaL} 2.0},1229 booktitle = {Computer Aided Verification --- CAV 2024},1230 series = {Lecture Notes in Computer Science},1231 volume = {14682},1232 publisher = {Springer},1233 year = {2024},1234 pages = {133--152},1235 doi = {10.1007/978-3-031-65627-9_7}1236}12371238@incollection{demoura2008z3,1239 author = {de Moura, Leonardo and Bj{\o}rner, Nikolaj},1240 title = {{Z3}: An Efficient {SMT} Solver},1241 booktitle = {Tools and Algorithms for the Construction and Analysis of Systems --- TACAS 2008},1242 series = {Lecture Notes in Computer Science},1243 volume = {4963},1244 publisher = {Springer},1245 year = {2008},1246 pages = {337--340},1247 doi = {10.1007/978-3-540-78800-3_24}1248}12491250@incollection{tseitin1983complexity,1251 author = {Tseitin, Grigori S.},1252 title = {On the Complexity of Derivation in Propositional Calculus},1253 booktitle = {Automation of Reasoning: 2: Classical Papers on Computational Logic 1967--1970},1254 publisher = {Springer},1255 year = {1983},1256 pages = {466--483},1257 doi = {10.1007/978-3-642-81955-1_28},1258 note = {Originally published in 1968 (Russian), translated 1970}1259}12601261@incollection{demoura2021lean,1262 author = {de Moura, Leonardo and Ullrich, Sebastian},1263 title = {The {Lean} 4 Theorem Prover and Programming Language},1264 booktitle = {Automated Deduction --- CADE 28},1265 series = {Lecture Notes in Computer Science},1266 volume = {12699},1267 publisher = {Springer},1268 year = {2021},1269 pages = {625--635},1270 doi = {10.1007/978-3-030-79876-5_37}1271}12721273@article{boving2025interactive,1274 author = {B{\"o}ving, Henrik and Bhat, Siddharth and Cicolini, Luisa and Keizer, Alex and Frenot, Leon and Mohamed, Abdalrhman and Stefanesco, Leo and Khan, Harun and Clune, Josh and Barrett, Clark and Grosser, Tobias},1275 title = {Interactive Bitvector Reasoning Using Verified Bit-Blasting},1276 journal = {Proceedings of the ACM on Programming Languages},1277 year = {2025},1278 volume = {9},1279 number = {OOPSLA2},1280 pages = {3259--3285},1281 doi = {10.1145/3763167},1282 note = {The Lean 4 \texttt{bv\_decide} tactic}1283}12841285@article{fawzi2022discovering,1286 author = {Fawzi, Alhussein and Balog, Matej and Huang, Aja and Hubert, Thomas and Romera-Paredes, Bernardino and Barekatain, Mohammadamin and Novikov, Alexander and Ruiz, Francisco J. R. and Schrittwieser, Julian and Swirszcz, Grzegorz and Silver, David and Hassabis, Demis and Kohli, Pushmeet},1287 title = {Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning},1288 journal = {Nature},1289 year = {2022},1290 volume = {610},1291 pages = {47--53},1292 doi = {10.1038/s41586-022-05172-4}1293}12941295@article{romeraparedes2024mathematical,1296 author = {Romera-Paredes, Bernardino and Barekatain, Mohammadamin and Novikov, Alexander and Balog, Matej and Kumar, M. Pawan and Dupont, Emilien and Ruiz, Francisco J. R. and Ellenberg, Jordan S. and Wang, Pengming and Fawzi, Omar and Kohli, Pushmeet and Fawzi, Alhussein},1297 title = {Mathematical Discoveries from Program Search with Large Language Models},1298 journal = {Nature},1299 year = {2024},1300 volume = {625},1301 pages = {468--475},1302 doi = {10.1038/s41586-023-06924-6}1303}13041305@article{davies2021advancing,1306 author = {Davies, Alex and Veli{\v{c}}kovi{\'c}, Petar and Buesing, Lars and Blackwell, Sam and Zheng, Daniel and Toma{\v{s}}ev, Nenad and Tanburn, Richard and Battaglia, Peter and Blundell, Charles and Juh{\'a}sz, Andr{\'a}s and Lackenby, Marc and Williamson, Geordie and Hassabis, Demis and Kohli, Pushmeet},1307 title = {Advancing Mathematics by Guiding Human Intuition with {AI}},1308 journal = {Nature},1309 year = {2021},1310 volume = {600},1311 pages = {70--74},1312 doi = {10.1038/s41586-021-04086-x}1313}13141315@article{trinh2024solving,1316 author = {Trinh, Trieu H. and Wu, Yuhuai and Le, Quoc V. and He, He and Luong, Thang},1317 title = {Solving Olympiad Geometry without Human Demonstrations},1318 journal = {Nature},1319 year = {2024},1320 volume = {625},1321 pages = {476--482},1322 doi = {10.1038/s41586-023-06747-5}1323}13241325@misc{lu2024ai,1326 author = {Lu, Chris and Lu, Cong and Lange, Robert Tjarko and Foerster, Jakob and Clune, Jeff and Ha, David},1327 title = {The {AI} Scientist: Towards Fully Automated Open-Ended Scientific Discovery},1328 howpublished = {arXiv:2408.06292},1329 year = {2024},1330 url = {https://arxiv.org/abs/2408.06292}1331}13321333@misc{novikov2025alphaevolve,1334 author = {Novikov, Alexander and V{\~u}, Ng{\^a}n and Eisenberger, Marvin and Dupont, Emilien and Huang, Po-Sen and Wagner, Adam Zsolt and Shirobokov, Sergey and Kozlovskii, Borislav and others},1335 title = {{AlphaEvolve}: A Coding Agent for Scientific and Algorithmic Discovery},1336 howpublished = {arXiv:2506.13131},1337 year = {2025},1338 url = {https://arxiv.org/abs/2506.13131}1339}13401341@incollection{sica2002analysis,1342 author = {Sica, Francesco and Ciet, Mathieu and Quisquater, Jean-Jacques},1343 title = {Analysis of the {G}allant-{L}ambert-{V}anstone Method Based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves},1344 booktitle = {Selected Areas in Cryptography --- SAC 2002},1345 series = {Lecture Notes in Computer Science},1346 volume = {2595},1347 publisher = {Springer},1348 year = {2003},1349 pages = {21--36},1350 doi = {10.1007/3-540-36492-7_3}1351}13521353@article{galbraith2011endomorphisms,1354 author = {Galbraith, Steven D. and Lin, Xibin and Scott, Michael},1355 title = {Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves},1356 journal = {Journal of Cryptology},1357 year = {2011},1358 volume = {24},1359 number = {3},1360 pages = {446--469},1361 doi = {10.1007/s00145-010-9065-y}1362}13631364@incollection{galbraith2009endomorphisms,1365 author = {Galbraith, Steven D. and Lin, Xibin and Scott, Michael},1366 title = {Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves},1367 booktitle = {Advances in Cryptology --- EUROCRYPT 2009},1368 series = {Lecture Notes in Computer Science},1369 volume = {5479},1370 publisher = {Springer},1371 year = {2009},1372 pages = {518--535},1373 doi = {10.1007/978-3-642-01001-9_30}1374}13751376@article{cheon2012speeding,1377 author = {Cheon, Jung Hee and Hong, Jin and Kim, Minkyu},1378 title = {Accelerating {P}ollard's Rho Algorithm on Finite Fields},1379 journal = {Journal of Cryptology},1380 year = {2012},1381 volume = {25},1382 number = {2},1383 pages = {195--242},1384 doi = {10.1007/s00145-010-9093-7},1385 note = {Journal version of ``Speeding up the Pollard rho method on prime fields'', ASIACRYPT 2008, doi:10.1007/978-3-540-89255-7\_29 (tag tracing)}1386}13871388@article{harris1960probability,1389 author = {Harris, Bernard},1390 title = {Probability Distributions Related to Random Mappings},1391 journal = {The Annals of Mathematical Statistics},1392 year = {1960},1393 volume = {31},1394 number = {4},1395 pages = {1045--1062},1396 doi = {10.1214/aoms/1177705677}1397}13981399@misc{bailey2009breaking,1400 author = {Bailey, Daniel V. and Batina, Lejla and Bernstein, Daniel J. and Birkner, Peter and Bos, Joppe W. and Chen, Hsieh-Chung and Cheng, Chen-Mou and van Damme, Gauthier and de Meulenaer, Giacomo and Dominguez Perez, Luis Julian and Fan, Junfeng and G{\"u}neysu, Tim and Gurkaynak, Frank and Kleinjung, Thorsten and Lange, Tanja and Mentens, Nele and Niederhagen, Ruben and Paar, Christof and Regazzoni, Francesco and Schwabe, Peter and Uhsadel, Leif and Van Herrewege, Anthony and Yang, Bo-Yin},1401 title = {Breaking {ECC2K-130}},1402 howpublished = {IACR Cryptology ePrint Archive, Report 2009/541},1403 year = {2009},1404 url = {https://eprint.iacr.org/2009/541},1405 note = {Describes the planned cross-platform attack; the Certicom challenge document of November 2009 still lists ECC2K-130 as unsolved}1406}14071408@article{stinson2002some,1409 author = {Stinson, Douglas R.},1410 title = {Some Baby-Step Giant-Step Algorithms for the Low {H}amming Weight Discrete Logarithm Problem},1411 journal = {Mathematics of Computation},1412 year = {2002},1413 volume = {71},1414 number = {237},1415 pages = {379--391},1416 doi = {10.1090/S0025-5718-01-01310-2}1417}14181419@article{hasse1936theorie,1420 author = {Hasse, Helmut},1421 title = {Zur {T}heorie der abstrakten elliptischen {F}unktionenk{\"o}rper {I}, {II}, {III}},1422 journal = {Journal f{\"u}r die reine und angewandte Mathematik},1423 year = {1936},1424 volume = {175},1425 pages = {55--62, 69--88, 193--208},1426 doi = {10.1515/crll.1936.175.55},1427 note = {Parts II and III: doi:10.1515/crll.1936.175.69, doi:10.1515/crll.1936.175.193}1428}14291430@article{deuring1941typen,1431 author = {Deuring, Max},1432 title = {Die {T}ypen der {M}ultiplikatorenringe elliptischer {F}unktionenk{\"o}rper},1433 journal = {Abhandlungen aus dem Mathematischen Seminar der Universit{\"a}t Hamburg},1434 year = {1941},1435 volume = {14},1436 pages = {197--272},1437 doi = {10.1007/BF02940746}1438}1439