Mathematics of Public Key Cryptography


Mathematics of Public Key Cryptography

Public key cryptography is a major interdisciplinary subject with many real-world applications, such as digital signatures. A strong background in the mathematics underlying public key cryptography is essential for a deep understanding of the subject, and this book provides exactly that for students and researchers in mathematics, computer science and electrical engineering. Carefully written to communicate the major ideas and techniques of public key cryptography to a wide readership, this text is enlivened throughout with historical remarks and insightful perspectives on the development of the subject. Numerous examples, proofs and exercises make it suitable as a textbook for an advanced course, as well as for self-study. For more experienced researchers it serves as a convenient reference for many important topics: the Pollard algorithms, Maurer reduction, isogenies, algebraic tori, hyperelliptic curves and many more.


 Reviews:

".. the reader is assumed to have a minimum background in group theory, algorithms and complexity, together with a basic knowledge of abstract algebra that includes ring and field theory. The book is suitable in principle for PhD. students in mathematics and related areas."
-Mathematical Reviews

Reference Title: References

Reference Type:

[1] M. Abdalla , M. Bellare and P. Rogaway , DHIES: An Encryption Scheme based on the Diffie–Hellman Problem, Preprint, 2001.
[2] L. M. Adleman and J. DeMarrais , A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 61(203) (1993), 1–15.
[3] L. M. Adleman , K. L. Manders and G. L. Miller , On taking roots in finite fields, Foundations of Computer Science (FOCS), IEEE, 1977, 175–178.
[4] L.M. Adleman , J. De Marrais and M.-D. Huang , A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. In ANTS I ( L. M. Adleman and M.-D. Huang , eds.), LNCS, vol. 877, Springer, 1994, pp. 28–40.
[5] G. B. Agnew , R. C. Mullin , I. M. Onyszchuk and S. A. Vanstone , An implementation for a fast public-key cryptosystem, J. Crypt. 3(2) (1991), 63–79.
[6] M. Agrawal , N. Kayal and N. Saxena , PRIMES is in P, Ann. of Math. 160(2) (2004), 781–793.
[7] E. Agrell , T. Eriksson , A. Vardy and K. Zeger , Closest point search in lattices, IEEE Trans. Inf. Theory 48(8) (2002), 2201–2214.
[8] A. Akavia , Solving hidden number problem with one bit oracle and advice. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 337–354.
[9] W. Alexi , B. Chor , O. Goldreich and C.-P. Schnorr , RSA and Rabin functions: certain parts are as hard as the whole, SIAM J. Comput. 17(2) (1988), 194–209.
[10] W. R. Alford , A. Granville and C. Pomerance , There are infinitely many Carmichael numbers, Ann. of Math. 139(3) (1994), 703–722.
[11] A. Antipa , D. R. L. Brown , R. P. Gallant , R. J. Lambert , R. Struik and S. A. Vanstone , Accelerated verification of ECDSA signatures. In SAC 2005 ( B. Preneel and S. E. Tavares , eds.), LNCS, vol. 3897, Springer, 2006, pp. 307–318.
[12] C. Arène , T. Lange , M. Naehrig and C. Ritzenthaler , Faster computation of the Tate pairing, J. Number Theory 131(5) (2011), 842–857.
[13] J. Arney and E. D. Bender , Random mappings with constraints on coalescence and number of origins, Pacific J. Math. 103 (1982), 269–294.
[14] E. Artin , Galois Theory, 2nd edn, Notre Dame, 1959.
[15] M. F. Atiyah and I. G. Macdonald , Introduction to Commutative Algebra, Addison-Wesley, 1969.
[16] R. Avanzi , H. Cohen , C. Doche , G. Frey , T. Lange , K. Nguyen and F. Vercauteren , Handbook of Elliptic and Hyperelliptic Cryptography, Chapman & Hall/CRC, 2006.
[17] L. Babai , On Lovász lattice reduction and the nearest lattice point problem, Combinatorica 6(1) (1986), 1–13.
[18] L. Babai and E. Szemerédi , On the complexity of matrix group problems I, Foundations of Computer Science (FOCS) (1996), 229–240.
[19] E. Bach , Bounds for primality testing and related problems, Math. Comp. 55(191) (1990), 355–380.
[20] E. Bach , Toward a theory of Pollard's rho method, Inf. Comput. 90(2) (1991), 139–155.
[21] E. Bach and J. Shallit , Algorithmic Number Theory, MIT Press, 1996.
[22] E. Bach and J. Sorenson , Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313–328.
[23] S. Bai and R. P. Brent , On the efficiency of Pollard's rho method for discrete logarithms, CATS 2008 ( J. Harland and P. Manyem , eds.), Australian Computer Society, 2008, pp. 125–131.
[24] D. V. Bailey , L. Batina , D. J. Bernstein , P. Birkner , J. W. Bos , H.-C. Chen , C.-M. Cheng , G. van Damme , G. de Meulenaer , L. Julian Dominguez Perez , J. Fan , T. Güneysu , F. Gurkaynak , T. Kleinjung , T. Lange , N. Mentens , R. Niederhagen , C. Paar , F. Regazzoni , P. Schwabe , L. Uhsadel , A. Van Herrewege and B.-Y. Yang , Breaking ECC2K-130, Cryptology ePrint Archive, Report 2009/541, 2009.
[25] R. Balasubramanian and N. Koblitz , The improbability that an elliptic curve has sub-exponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm, J. Crypt. 11(2) (1998), 141–145.
[26] P. S. L. M. Barreto , S. D. Galbraith , C. Ó hÉigeartaigh and M. Scott , Efficient pairing computation on supersingular abelian varieties, Des. Codes Crypt. 42(3) (2007), 239–271.
[27] P. S. L. M. Barreto , H. Y. Kim , B. Lynn and M. Scott , Efficient algorithms for pairing-based cryptosystems, CRYPTO 2002 ( M. Yung , ed.), LNCS, vol. 2442, Springer, 2002, pp. 354–369.
[28] P. S. L. M. Barreto and M. Naehrig , Pairing-friendly elliptic curves of prime order, SAC 2005 ( B. Preneel and S. E. Tavares , eds.), LNCS, vol. 3897, Springer, 2006, pp. 319–331.
[29] A. Bauer , Vers une généralisation rigoureuse des méthodes de Coppersmith pour la recherche de petites racines de polynmes, Ph.D. thesis, Université de Versailles Saint-Quentin-en-Yvelines, 2008.
[30] M. Bellare , R. Canetti and H. Krawczyk , A modular approach to the design and analysis of authentication and key exchange protocols, Symposium on the Theory of Computing (STOC), ACM, 1998, pp. 419–428.
[31] M. Bellare , J. A. Garay and T. Rabin , Fast batch verification for modular exponentiation and digital signatures, EUROCRYPT 1998 ( K. Nyberg , ed.), LNCS, vol. 1403, Springer, 1998, pp. 236–250.
[32] M. Bellare , S. Goldwasser and D. Micciancio , “Pseudo-Random” number generation within cryptographic algorithms: the DSS case, CRYPTO 1997 ( B. S. Kaliski Jr. , ed.), LNCS, vol. 1294, Springer, 1997, pp. 277–291.
[33] M. Bellare and G. Neven , Multi-signatures in the plain public-key model and a general forking lemma, CCS 2006 ( A. Juels , R. N. Wright and S. De Capitani di Vimercati , eds.), ACM, 2006, pp. 390–399.
[34] M. Bellare , D. Pointcheval and P. Rogaway , Authenticated key exchange secure against dictionary attacks, EUROCRYPT 2000 ( B. Preneel , ed.), LNCS, vol. 1807, Springer, 2000, pp. 139–155.
[35] M. Bellare and P. Rogaway , Random oracles are practical: a paradigm for designing efficient protocols, CCS 1993, ACM, 1993, pp. 62–73.
[36] M. Bellare Entity authentication and key distribution, CRYPTO 1993 ( D. R. Stinson , ed.), LNCS, vol. 773, Springer, 1994, pp. 232–249.
[37] M. Bellare Optimal asymmetric encryption – how to encrypt with RSA, EUROCRYPT 1994 ( A. De Santis , ed.), LNCS, vol. 950, Springer, 1995, pp. 92–111.
[38] M. Bellare The exact security of digital signatures – how to sign with RSA and Rabin. In EUROCRYPT 1996 ( U. M. Maurer , ed.), LNCS, vol. 1070, Springer, 1996, pp. 399–416.
[39] K. Bentahar , The equivalence between the DHP and DLP for elliptic curves used in practical applications, revisited. In IMA Cryptography and Coding ( N. P. Smart , ed.), LNCS, vol. 3796, Springer, 2005, pp. 376–391.
[40] K. Bentahar , Theoretical and practical efficiency aspects in cryptography, Ph.D. thesis, University of Bristol, 2008.
[41] D. J. Bernstein , Pippenger's exponentiation algorithm, Preprint, 2002.
[42] D. J. Bernstein , T. Lange and P. Schwabe , On the correct use of the negation map in the Pollard rho method. In PKC 2011 ( D. Catalano , N. Fazio , R. Gennaro , and A. Nicolosi , eds.), LNCS, vol. 6571, Springer, 2011, pp. 128–146.
[43] D. J. Bernstein , T. Lange and P. Schwabe , Curve 25519: New Diffie–Hellman speed records. In PKC 2006 ( M. Yung , Y. Dodis , A. Kiayias and T. Malkin , eds.), LNCS, vol. 3958, Springer, 2006, pp. 207–228.
[44] D. J. Bernstein , T. Lange and P. Schwabe , Proving tight security for Rabin–Williams signatures. In EUROCRYPT 2008 ( N. P. Smart , ed.), LNCS, vol. 4965, Springer, 2008, pp. 70–87.
[45] D. J. Bernstein , T. Lange and P. Schwabe , Faster rho for elliptic curves, Rump session talk, ANTS IX, 2010.
[46] D. J. Bernstein , P. Birkner , M. Joye , T. Lange and C. Peters , Twisted Edwards curves. In Africacrypt 2008 ( S. Vaudenay , ed.), LNCS, vol. 5023, Springer, 2008, pp. 389–405.
[47] D. J. Bernstein , P. Birkner , T. Lange and C. Peters , ECM using Edwards Curves, Cryptology ePrint Archive, Report 2008/016, 2008.
[48] D. J. Bernstein , J. Buchmann and E. Dahmen , Post Quantum Cryptography, Springer, 2008.
[49] D. J. Bernstein and T. Lange , Explicit Formulas Database, 2007 (www.hyperelliptic.org/EFD).
[50] D. J. Bernstein Faster addition and doubling on elliptic curves. In ASIACRYPT 2007 ( K. Kurosawa , ed.), LNCS, vol. 4833, Springer, 2007, pp. 29–50.
[51] D. J. Bernstein Analysis and optimization of elliptic-curve single-scalar multiplication, Contemporary Mathematics 461 (2008), 1–19.
[52] D. J. Bernstein Type-II optimal polynomial bases. In WAIFI 2010 ( M. A. Hasan and T. Helleseth , eds.), LNCS, vol. 6087, Springer, 2010, pp. 41–61.
[53] D. J. Bernstein , T. Lange and R. R. Farashahi , Binary Edwards curves. In CHES 2008, ( E. Oswald and P. Rohatgi , eds.), LNCS, vol. 5154, Springer, 2008, pp. 244–265.
[54] G. Bisson and A. V. Sutherland , Computing the endomorphism ring of an ordinary elliptic curve over a finite field, J. Number Theory 131(5) (2011), 815–831.
[55] S. R. Blackburn and S. Murphy , The number of partitions in Pollard rho, unpublished manuscript, 1998.
[56] S. R. Blackburn and E. Teske , Baby-step–giant-step algorithms for non-uniform distributions. In ANTS IV ( W. Bosma , ed.), LNCS, vol. 1838, Springer, 2000, pp. 153–168.
[57] I. F. Blake , R. Fuji-Hara , R. C. Mullin and S. A. Vanstone , Computing logarithms in finite fields of characteristic two, SIAM J. Algebraic and Discrete Methods 5(2) (1984), 272–285.
[58] I. F. Blake and T. Garefalakis , On the complexity of the discrete logarithm and Diffie–Hellman problems, J. Complexity 20(2–3) (2004), 148–170.
[59] I. F. Blake , T. Garefalakis and I. E. Shparlinski , On the bit security of the Diffie–Hellman key, Appl. Algebra Eng. Commun. Comput. 16(6) (2006), 397–404.
[60] I. F. Blake , G. Seroussi and N. P. Smart , Elliptic Curves in Cryptography, Cambridge University Press, 1999.
[61] I. F. Blake , G. Seroussi and N. P. Smart , Advances in Elliptic Curve Cryptography, Cambridge University Press, 2005.
[62] D. Bleichenbacher , Generating ElGamal signatures without knowing the secret key, EUROCRYPT 1996 ( U. M. Maurer , ed.), LNCS, vol. 1070, Springer, 1996, pp. 10–18.
[63] D. Bleichenbaucher , Compressing Rabin signatures. In CT-RSA 2004 ( T. Okamoto , ed.), LNCS, vol. 2964, Springer, 2004, pp. 126–128.
[64] D. Bleichenbacher and A. May , New attacks on RSA with small secret CRT-exponents. In PKC 2006 ( M. Yung , Y. Dodis , A. Kiayias and T. Malkin , eds.), LNCS, vol. 3958, Springer, 2006, pp. 1–13.
[65] D. Bleichenbacher and P. Q. Nguyen , Noisy polynomial interpolation and noisy Chinese remaindering. In EUROCRYPT 2000 ( B. Preneel , ed.), LNCS, vol. 1807, Springer, 2000, pp. 53–69.
[66] J. Blömer and A. May , Low secret exponent RSA revisited. In Cryptography and Lattices (CaLC) ( J. H. Silverman , ed.), LNCS, vol. 2146, Springer, 2001, pp. 4–19.
[67] J. Blömer and A. May , A tool kit for finding small roots of bivariate polynomials over the integers. In EUROCRYPT 2005 ( R. Cramer , ed.), LNCS, vol. 3494, Springer, 2005, pp. 251–267.
[68] M. Blum and S. Micali , How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. Comput. 13(4) (1984), 850–864.
[69] D. Boneh , Simplified OAEP for the RSA and Rabin functions. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 275–291.
[70] D. Boneh , Finding smooth integers in short intervals using CRT decoding, J. Comput. Syst. Sci. 64(4) (2002), 768–784.
[71] D. Boneh and X. Boyen , Short signatures without random oracles. In EUROCRYPT 2004 ( C. Cachin and J. Camenisch , eds.), LNCS, vol. 3027, Springer, 2004, pp. 56–73.
[72] D. Boneh and X. Boyen , Short signatures without random oracles and the SDH assumption in bilinear groups, J. Crypt. 21(2) (2008), 149–177.
[73] D. Boneh and G. Durfee , Cryptanalysis of RSA with private key d less than N0.292 , IEEE Trans. Inf. Theory 46(4) (2000), 1339–1349.
[74] D. Boneh , G. Durfee and N. Howgrave-Graham , Factoring N = pr q for large r. In CRYPTO 1999 ( M. J. Wiener , ed.), LNCS, vol. 1666, Springer, 1999, pp. 326–337.
[75] D. Boneh and M. K. Franklin , Identity based encryption from the Weil pairing. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 213–229.
[76] D. Boneh and M. K. Franklin , Identity based encryption from theWeil pairing, SIAM J. Comput. 32(3) (2003), 586–615.
[77] D. Boneh , A. Joux and P. Nguyen , Why textbook ElGamal and RSA encryption are insecure. In ASIACRYPT 2000 ( T. Okamoto , ed.), LNCS, vol. 1976, Springer, 2000, pp. 30–43.
[78] D. Boneh and R. J. Lipton , Algorithms for black-box fields and their application to cryptography. In CRYPTO 1996 ( N. Koblitz , ed.), LNCS, vol. 1109, Springer, 1996, pp. 283–297.
[79] D. Boneh and I. E. Shparlinski , On the unpredictability of bits of the elliptic curve Diffie–Hellman scheme. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 201–212.
[80] D. Boneh and R. Venkatesan , Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes. In CRYPTO 1996 ( N. Koblitz , ed.), LNCS, vol. 1109, Springer, 1996, pp. 129–142.
[81] D. Boneh and R. Venkatesan , Rounding in lattices and its cryptographic applications. In Symposium on Discrete Algorithms (SODA), ACM/SIAM, 1997, pp. 675–681.
[82] D. Boneh and R. Venkatesan , Breaking RSA may not be equivalent to factoring. In EUROCRYPT 1998 ( K. Nyberg , ed.), LNCS, vol. 1403, Springer, 1998, pp. 59–71.
[83] A. Borodin and I. Munro , The Computational Complexity of Algebraic and Numeric Problems, Elsevier, 1975.
[84] J. W. Bos , M. E. Kaihara and T. Kleinjung , Pollard Rho on Elliptic Curves, Preprint, 2009.
[85] J. W. Bos , M. E. Kaihara and P. L. Montgomery , Pollard rho on the Playstation 3, Handouts of SHARCS 2009, 2009, pp. 35–50.
[86] J. W. Bos , T. Kleinjung and A. K. Lenstra , On the use of the negation map in the Pollard rho method. In ANTS IX ( G. Hanrot , F. Morain and E. Thomé , eds.), LNCS, vol. 6197, Springer, 2010, pp. 66–82.
[87] W. Bosma and H. W. Lenstra Jr. , Complete systems of two addition laws for elliptic curves, J. Number Theory 53 (1995), 229–240.
[88] A. Bostan , F. Morain , B. Salvy and E. Schost , Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77(263) (2008), 1755–1778.
[89] C. Boyd and A. Mathuria , Protocols for authentication and key establishment, Information Security and Cryptography, Springer, 2003.
[90] X. Boyen , The uber-assumption family. In Pairing 2008 ( S. D. Galbraith and K. G. Paterson , eds.), LNCS, vol. 5209, Springer, 2008, pp. 39–56.
[91] V. Boyko , M. Peinado and R. Venkatesan , Speeding up discrete log and factoring based schemes via precomputations. In EUROCRYPT 1998 ( K. Nyberg , ed.), LNCS, vol. 1403, Springer, 1998, pp. 221–235.
[92] S. Brands , An efficient off-line electronic cash system based on the representation problem, Tech. report, CWI Amsterdam, 1993, CS-R9323.
[93] R. P. Brent , An improved Monte Carlo factorization algorithm, BIT (1980), 176–184.
[94] R. P. Brent and J. M. Pollard , Factorization of the eighth Fermat number, Math. Comp. 36(154) (1981), 627–630.
[95] R. P. Brent and P. Zimmermann , Modern Computer Arithmetic, Cambridge University Press, 2010.
[96] R. P. Brent and P. Zimmermann , An O(M(n)logn) algorithm for the Jacobi symbol. In ANTS IX ( G. Hanrot , F. Morain and E. Thomé , eds.), LNCS, vol. 6197, Springer, 2010, pp. 83–95.
[97] E. Bresson , Y. Lakhnech , L. Mazaré and B. Warinschi , A generalization of DDH with applications to protocol analysis and computational soundness. In CRYPTO 2007 ( A. J. Menezes , ed.), LNCS, vol. 4622, Springer, 2007, pp. 482–499.
[98] E. F. Brickell , D. Pointcheval , S. Vaudenay and M. Yung , Design validations for discrete logarithm based signature schemes. In PKC 2000 ( H. Imai and Y. Zheng , eds.), LNCS, vol. 1751, Springer, 2000, pp. 276–292.
[99] E. Brier , C. Clavier and D. Naccache , Cryptanalysis of RSA signatures with fixed-pattern padding. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 433–439.
[100] R. Bröker , Constructing supersingular elliptic curves, J. Comb. Number Theory 1(3) (2009), 269–273.
[101] R. Bröker , D. X. Charles and K. Lauter , Evaluating large degree isogenies and applications to pairing based cryptography. In Pairing 2008 ( S. D. Galbraith and K. G. Paterson , eds.), LNCS, vol. 5209, Springer, 2008, pp. 100–112.
[102] R. Bröker , K. Lauter and A. V. Sutherland , Modular polynomials via isogeny volcanoes, http://arxiv.org/abs/1001.0402, 2010, to appear in Math. Comp..
[103] R. Bröker and A. V. Sutherland , An explicit height bound for the classical modular polynomial, The Ramanujan Journal 22(3) (2010), 293–313.
[104] D. R. L. Brown and R. P. Gallant , The static Diffie–Hellman problem, Cryptology ePrint Archive, Report 2004/306, 2004.
[105] B. B. Brumley and K. U. Järvinen , Koblitz curves and integer equivalents of Frobenius expansions. In SAC 2007 ( C. M. Adams , A. Miri and M. J. Wiener , eds.), LNCS, vol. 4876, Springer, 2007, pp. 126–137.
[106] J. P. Buhler and P. Stevenhagen , Algorithmic Number Theory, MSRI Publications, Cambridge University Press, 2008.
[107] M. Burmester and Y. Desmedt , A secure and efficient conference key distribution system. In EUROCRYPT 1994 ( A. De Santis , ed.), LNCS, vol. 950, Springer, 1995, pp. 267–275.
[108] R. Canetti , O. Goldreich and S. Halevi , The random oracle model, revisited. In Symposium on the Theory of Computing (STOC), ACM, 1998, pp. 209–218.
[109] R. Canetti and H. Krawczyk , Analysis of key-exchange protocols and their use for building secure channels. In EUROCRYPT 2001 ( B. Pfitzmann , ed.), LNCS, vol. 2045, Springer, 2001, pp. 453–474.
[110] E. R. Canfield , P. Erdös and C. Pomerance , On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17(1) (1983), 1–28.
[111] D. G. Cantor , Computing in the Jacobian of an hyperelliptic curve, Math. Comp. 48(177) (1987), 95–101.
[112] D. Cash , E. Kiltz and V. Shoup , The twin Diffie–Hellman problem and applications. In EUROCRYPT 2008 ( N. P. Smart , ed.), LNCS, vol. 4965, Springer, 2008, pp. 127–145.
[113] J. W. S. Cassels , An Introduction to the Geometry of Numbers, Springer, 1959.
[114] J. W. S. Cassels , Lectures on Elliptic Curves, Cambridge University Press, 1991.
[115] J. W. S. Cassels and E. V. Flynn , Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2, Cambridge University Press, 1996.
[116] J. W. S. Cassels and A. Frölich , Algebraic Number Theory, Academic Press, 1967.
[117] D. Catalano , R. Gennaro , N. Howgrave-Graham and P. Q. Nguyen , Paillier's cryptosystem revisited. In CCS 2001, ACM, 2001, pp. 206–214.
[118] L. S. Charlap and R. Coley , An elementary introduction to elliptic curves II, CCR Expository Report 34, Institute for Defense Analysis, 1990.
[119] L. S. Charlap and D. P. Robbins , An elementary introduction to elliptic curves, CRD Expository Report 31, 1988.
[120] D. X. Charles , K. E. Lauter and E. Z. Goren , Cryptographic hash functions from expander graphs, J. Crypt. 22(1) (2009), 93–113.
[121] D. Chaum , E. van Heijst and B. Pfitzmann , Cryptographically strong undeniable signatures, unconditionally secure for the signer. In CRYPTO 1991 ( J. Feigenbaum , ed.), LNCS, vol. 576, Springer, 1992, pp. 470–484.
[122] J.-H. Cheon , Security analysis of the strong Diffie–Hellman problem. In EUROCRYPT 2006 ( S. Vaudenay , ed.), LNCS, vol. 4004, Springer, 2006, pp. 1–11.
[123] J.-H. Cheon , Discrete logarithm problem with auxiliary inputs, J. Crypt. 23(3) (2010), 457–476.
[124] J. H. Cheon , J. Hong and M. Kim , Speeding up the Pollard rho method on prime fields. In ASIACRYPT 2008 ( J. Pieprzyk , ed.), LNCS, vol. 5350, Springer, 2008, pp. 471–488.
[125] J. H. Cheon and H.-T. Kim , Analysis of low Hamming weight products, Discrete Appl. Math. 156(12) (2008), 2264–2269.
[126] M. A. Cherepnev , On the connection between the discrete logarithms and the Diffie–Hellman problem, Discr. Math. Appl. 6(4) (1996), 341–349.
[127] H. Cohen , A Course in Computational Algebraic Number Theory, GTM 138, Springer, 1993.
[128] P. Cohen , On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. Cambridge Philos. Soc. 95(3) (1984), 389–402.
[129] S. A. Cook , An overviewof computational complexity, Commun. ACM 26(6) (1983), 400–408.
[130] D. Coppersmith , Fast evaluation of logarithms in fields of characteristic 2, IEEE Trans. Inf. Theory 30(4) (1984), 587–594.
[131] D. Coppersmith , Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Crypt. 10(4) (1997), 233–260.
[132] D. Coppersmith , Finding small solutions to small degree polynomials. In Cryptography and Lattices (CaLC) ( J. H. Silverman , ed.) LNCS, vol. 2146, Springer, 2001, pp. 20–31.
[133] D. Coppersmith , J.-S. Coron , F. Grieu , S. Halevi , C. Jutla , D. Naccache and J. P. Stern , Cryptanalysis of ISO/IEC 9796-1, J. Crypt. 21(1) (2008), 27–51.
[134] D. Coppersmith , M. K. Franklin , J. Patarin and M. K. Reiter , Low-exponent RSA with related messages In EUROCRYPT 1996 ( U.M. Maurer , ed.), LNCS, vol. 1070, Springer, 1996, pp. 1–9.
[135] D. Coppersmith , A. M. Odlzyko and R. Schroeppel , Discrete logarithms in GF(p), Algorithmica 1(1–4) (1986), 1–15.
[136] T. H. Cormen , C. E. Leiserson , R. L. Rivest and C. Stein , Introduction to Algorithms, 2nd edn, MIT press, 2001.
[137] J.-S. Coron , On the exact security of full domain hash. In CRYPTO 2000 ( M. Bellare , ed.), LNCS, vol. 1880, Springer, 2000, pp. 229–235.
[138] J.-S. Coron Optimal security proofs for PSS and other signature schemes. In EUROCRYPT 2002 ( L. R. Knudsen , ed.), LNCS, vol. 2332, Springer, 2002, pp. 272–287.
[139] J.-S. Coron Finding small roots of bivariate integer polynomial equations: a direct approach. In CRYPTO 2007 ( A. Menezes , ed.), LNCS, vol. 4622, Springer, 2007, pp. 379–394.
[140] J.-S. Coron and A. May , Deterministic polynomial-time equivalence of computing the RSA secret key and factoring, J. Crypt. 20(1) (2007), 39–50.
[141] J.-S. Coron , D. M'Raïhi and C. Tymen , Fast generation of pairs (k, [k]P) for Koblitz elliptic curves. In SAC 2001 ( S. Vaudenay and A.M. Youssef , eds.), vol. 2259, Springer, 2001, pp. 151–164.
[142] J.-S. Coron , D. Naccache , M. Tibouchi and R.-P. Weinmann , Practical cryptanalysis of ISO/IEC 9796-2 and EMV signatures. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 428–444.
[143] J.-M. Couveignes , Computing l-isogenies with the p-torsion. In ANTS II ( H. Cohen , ed.), LNCS, vol. 1122, Springer, 1996, pp. 59–65.
[144] J.-M. Couveignes , L. Dewaghe and F. Morain , Isogeny cycles and the Schoof–Elkies–Atkin algorithm, Research Report LIX/RR/96/03, 1996.
[145] D. A. Cox , Primes of the Form x2 + ny2, Wiley, 1989.
[146] D. A. Cox , J. Little and D. O'Shea, Ideals, Varieties and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra, 2nd edn, Springer, 1997.
[147] R. Cramer and V. Shoup , A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In CRYPTO 1998 ( H. Krawczyk , ed.), LNCS, vol. 1462, Springer, 1998, pp. 13–25.
[148] R. Cramer and V. Shoup Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT 2002 ( L.R. Knudsen , ed.), LNCS, vol. 2332, Springer, 2002, pp. 45–64.
[149] R. Cramer and V. Shoup Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. Comput. 33(1) (2003), 167–226.
[150] R. Crandall and C. Pomerance , Prime Numbers: A Computational Perspective, 2nd edn, Springer, 2005.
[151] C.W. Curtis , Linear Algebra: An Introductory Approach, Undergraduate Texts in Mathematics, Springer, 1984.
[152] I. Damgård , On the randomness of Legendre and Jacobi sequences. In CRYPTO 1988 ( S. Goldwasser , ed.), LNCS, vol. 403, Springer, 1990, pp. 163–172.
[153] G. Davidoff , P. Sarnak and A. Valette , Elementary Number Theory, Group Theory, and Ramanujan Graphs, Cambridge University Press, 2003.
[154] M. Davis and E. J. Weyuker , Computability, Complexity and Languages, Academic Press, 1983.
[155] P. de Rooij , On Schnorr's preprocessing for digital signature schemes, J.|Crypt. 10(1) (1997), 1–16.
[156] B. den Boer , Diffie–Hellman is as strong as discrete log for certain primes. In CRYPTO 1988 ( S. Goldwasser , ed.), LNCS, vol. 403, Springer, 1990, pp. 530–539.
[157] Y. Desmedt and A. M. Odlyzko , A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes. In CRYPTO 1985 ( H. C.Williams , ed.), LNCS, vol. 218, Springer, 1986, pp. 516–522.
[158] L. Dewaghe , Un corollaire aux formules de Vélu, Preprint, 1995.
[159] C. Diem , The GHS-attack in odd characteristic, J.|Ramanujan Math.|Soc. 18(1) (2003), 1–32.
[160] C. Diem On the discrete logarithm problem in elliptic curves over non-prime finite fields, Lecture at ECC 2004, 2004.
[161] C. Diem An index calculus algorithm for plane curves of small degree. In ANTS VII ( F. Hess , S. Pauli and M.E. Pohst , eds.), LNCS, vol. 4076, Springer, 2006, pp. 543–557.
[162] C. Diem , An index calculus algorithm for non-singular plane curves of high genus, talk at ECC 2006.
[163] C. Diem On the Discrete Logarithm Problem in Elliptic Curves, Compositio Math. 147 (2011), 75–104.
[164] C. Diem On the discrete logarithm problem in class groups of curves, Math.|Comp. 80(273) (2011), 443–475.
[165] C. Diem and E. Thom é, Index calculus in class groups of non-hyperelliptic curves of genus three, J.|Crypt. 21(4) (2008), 593–611.
[166] W. Diffie and M. E. Hellman , New directions in cryptography, IEEE Trans.|Inf. Theory 22 (1976), 644–654.
[167] V. S. Dimitrov , G. A. Jullien and W. C. Miller , Theory and applications of the double-base number system, IEEE Trans. Computers 48(10) (1999), 1098–1106.
[168] V. S. Dimitrov , K. U. Järvinen, M. J. Jacobson , W. F. Chan and Z. Huang , Provably sublinear point multiplication on Koblitz curves and its hardware implementation, IEEE Trans. Computers 57(11) (2008), 1469–1481.
[169] C. Doche , T. Icart and D. R. Kohel , Efficient scalar multiplication by isogeny decompositions. In PKC 2006 ( M. Yung , Y. Dodis , A. Kiayias and T. Malkin , eds.), LNCS, vol. 3958, Springer, 2006, pp. 191–206.
[170] A. Dujella , A variant of Wiener's attack on RSA, Computing 85(1–2) (2009), 77–83.
[171] I. M. Duursma , Class numbers for some hyperelliptic curves. In Arithmetic, Geometry and Coding Theory ( R. Pellikaan , M. Perret and S.G. Vladut , eds.), Walter de Gruyter, 1996, pp. 45–52.
[172] I. M. Duursma , P. Gaudry and F. Morain , Speeding up the discrete log computation on curves with automorphisms. In ASIACRYPT 1999 ( K. Y.|Lam , E. Okamoto and C. Xing , eds.), LNCS, vol. 1716, Springer, 1999, pp. 103–121.
[173] I. M. Duursma and H.-s. Lee , Tate pairing implementation for hyperelliptic curves y2 = xp – x + d. In ASIACRYPT 2003 ( C.-s. Laih , ed.), LNCS, vol. 2894, Springer, 2003, pp. 111–123.
[174] S. Edixhoven , Le couplage Weil: de la géométrie à l'arithmétique, Notes from a seminar in Rennes, 2002.
[175] H. M. Edwards , A normal form for elliptic curves, Bulletin of the AMS 44 (2007), 393–422.
[176] D. Eisenbud , Commutative Algebra with a View Toward Algebraic Geometry, GTM, vol. 150, Springer, 1999.
[177] T. ElGamal , A public key cryptosystem and a signature scheme based on discrete logarithms. In CRYPTO 1984 ( G.R. Blakley and D. Chaum , eds.), LNCS, vol. 196, Springer, 1985, pp. 10–18.
[178] N. D. Elkies , Elliptic and modular curves over finite fields and related computational issues. In Computational Perspectives on Number Theory ( D.A. Buell and J.T. Teitelbaum , eds.), Studies in Advanced Mathematics, AMS, 1998, pp. 21–76.
[179] A. Enge , Computing modular polynomials in quasi-linear time, Math. Comp. 78(267) (2009), 1809–1824.
[180] A. Enge and P. Gaudry , A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), 83–103.
[181] A. Enge and P. Gaudry , An L(1/3 + ε) algorithm for the discrete logarithm problem for low degree In EUROCRYPT 2007 ( M. Naor , ed.), LNCS, vol. 4515, Springer, 2007, pp. 379– 393.
[182] A. Enge , P. Gaudry and E. Thomé , An L(1/3) discrete logarithm algorithm for low degree curves, J. Crypt. 24(1) (2011), 24–41.
[183] A. Enge and A. Stein , Smooth ideals in hyperelliptic function fields, Math. Comp. 71(239) (2002), 1219–1230.
[184] S. Erickson , M. J. Jacobson Jr. , N. Shang , S. Shen and A. Stein , Explicit formulas for real hyperelliptic curves of genus 2 in affine representation, WAIFI 2007 ( C. Carlet and B. Sunar , eds.), LNCS, vol. 4547, Springer, 2007, pp. 202–218.
[185] L. De Feo , Fast algorithms for towers of finite fields and isogenies, Ph.D. thesis, L'École Polytechnique, 2010.
[186] R. Fischlin and C.-P. Schnorr , Stronger security proofs for RSA and Rabin bits, J. Crypt. 13(2) (2000), 221–244.
[187] P. Flajolet and A. M. Odlyzko , Random mapping statistics. In EUROCRYPT 1989 ( J.-J. Quisquater and J. Vandewalle , eds.), LNCS, vol. 434, Springer, 1990, pp. 329–354.
[188] P. Flajolet and R. Sedgewick , Analytic Combinatorics, Cambridge University Press, 2009.
[189] R. Flassenberg and S. Paulus , Sieving in function fields, Experiment. Math. 8(4) (1999), 339–349.
[190] K. Fong , D. Hankerson , J. López and A. J. Menezes , Field inversion and point halving revisited, IEEE Trans. Computers 53(8) (2004), 1047–1059.
[191] C. Fontaine and F. Galand , A survey of homomorphic encryption for nonspecialists, EURASIP Journal on Information Security 2007(15) (2007), 1–10.
[192] M. Fouquet and F. Morain , Isogeny volcanoes and the SEA algorithm. In ANTS V ( C. Fieker and D. R. Kohel , eds.), LNCS, vol. 2369, Springer, 2002, pp. 276–291.
[193] D. M. Freeman , O. Goldreich , E. Kiltz , A. Rosen and G. Segev , More constructions of lossy and correlation-secure trapdoor functions. In PKC 2010 ( P. Q. Nguyen and D. Pointcheval , eds.), LNCS, vol. 6065, Springer, 2010, pp. 279–295.
[194] D. Freeman , M. Scott and E. Teske , A taxonomy of pairing-friendly elliptic curves, J. Crypt..23(2) (2010), 224–280.
[195] G. Grey , How to disguise an elliptic curve, talk at ECC 1998, Waterloo, 1998.
[196] G. Frey and H.-G. Rück , A remark concerning m-divisibility and the discrete logarithm problem in the divisor class group of curves, Math. Comp. 62(206) (1994), 865–874.
[197] M. D. Fried and M. Jarden , Field Arithmetic, 3rd edn, Springer, 2008.
[198] E. Fujisaki , T. Okamoto , D. Pointcheval and J. Stern , RSA-OAEP is secure under the RSA assumption, J. Crypt. 17(2) (2004), 81–104.
[199] W. Fulton , Algebraic Curves, Addison-Wesley, 1989, Out of print, but freely available here: www.math.lsa.umich.edu/∼wfulton/.
[200] S. D. Galbraith , Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138.
[201] S. D. Galbraith , Supersingular curves in cryptography. In ASIACRYPT 2001 ( C. Boyd , ed.), LNCS, vol. 2248, Springer, 2001, pp. 495–513.
[202] S. D. Galbraith , M. Harrison and D. J. Mireles Morales , Efficient hyperelliptic arithmetic using balanced representation for divisors. In ANTS VIII ( A. J. van der Poorten and A. Stein , eds.), LNCS, vol. 5011, Springer, 2008, pp. 342–356.
[203] S. D. Galbraith , C. Heneghan and J. F. McKee , Tunable balancing of RSA. In ACISP 2005 ( C. Boyd and J. M. Gonzàlez Nieto , eds.), LNCS, vol. 3574, Springer, 2005, pp. 280–292.
[204] S. D. Galbraith , F. Hess and N. P. Smart , Extending the GHS Weil descent attack. In EUROCRYPT 2002 ( L. R. Knudsen , ed.), LNCS, vol. 2332, Springer, 2002, pp. 29–44.
[205] S. D. Galbraith , F. Hess and F. Vercauteren , Aspects of pairing inversion, IEEE Trans. Inf. Theory 54(12) (2008), 5719–5728.
[206] S. D. Galbraith and M. Holmes , A Non-Uniform Birthday Problem with Applications to Discrete Logarithms, Cryptology ePrint Archive, Report 2010/616, 2010.
[207] S. D. Galbraith , X. Lin and M. Scott , Endomorphisms for faster elliptic curve cryptography on a large class of curves. In EUROCRYPT 2009 ( A. Joux , ed.), LNCS, vol. 5479, Springer, 2009, pp. 518–535.
[208] S. D. Galbraith and J. F. McKee , The probability that the number of points on an elliptic curve over a finite field is prime, J. Lond. Math. Soc. 62(3) (2000), 671–684.
[209] S. D. Galbraith , J. M. Pollard and R. S. Ruprai , Computing Discrete Logarithms in an Interval, Cryptology ePrint Archive, Report 2010/617, 2010.
[210] S. D. Galbraith and R. S. Ruprai , An improvement to the Gaudry–Schost algorithm for multidimensional discrete logarithm problems. In IMA Cryptography and Coding ( M. G. Parker , ed.), LNCS, vol. 5921, Springer, 2009, pp. 368–382.
[211] S. D. Galbraith and R. S. Ruprai , Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval. In PKC 2010 ( P. Q. Nguyen and D. Pointcheval , eds.), LNCS, vol. 6056, Springer, 2010, pp. 368–383.
[212] S. D. Galbraith and N. P. Smart , A cryptographic application of Weil descent. In IMA Cryptography and Coding ( M. Walker , ed.), LNCS, vol. 1746, Springer, 1999, pp. 191–200.
[213] S. D. Galbraith and A. Stolbunov , Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves, Preprint, 2011.
[214] S. D. Galbraith and E. R. Verheul , An analysis of the vector decomposition problem. In PKC 2008 ( R. Cramer , ed.), LNCS, vol. 4939, Springer, 2008, pp. 308–327.
[215] R. P. Gallant , R. J. Lambert and S. A. Vanstone , Improving the parallelized Pollard lambda search on binary anomalous curves, Math. Comp. 69 (2000), (232) 1699–1705.
[216] R. P. Gallant , R. J. Lambert and S. A. Vanstone , Faster point multiplication on elliptic curves with efficient endomorphisms. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 190–200.
[217] N. Gama , P. Q. Nguyen and O. Regev , Lattice enumeration using extreme pruning. In EUROCRYPT 2010 ( H. Gilbert , ed.), LNCS, vol. 6110, Springer, 2010, pp. 257–278.
[218] S. Gao , Normal bases over finite fields, Ph.D. thesis, Waterloo, 1993.
[219] T. Garefalakis , The generalised Weil pairing and the discrete logarithm problem on elliptic curves, Theor. Comput. Sci. 321(1) (2004), 59–72.
[220] J. von zur Gathen and J. Gerhard , Modern Computer Algebra, Cambridge University Press, 1999.
[221] J. von zur Gathen and M. Giesbrecht , Constructing normal bases in finite fields, J. Symb. Comput. 10(6) (1990), 547–570.
[222] J. von zur Gathen , I. E. Shparlinski and A. Sinclair , Finding points on curves over finite fields, SIAM J. Comput. 32(6) (2003), 1436–1448.
[223] P. Gaudry , An algorithm for solving the discrete log problem on hyperelliptic curves. In EUROCRYPT 2000 ( B. Preneel , ed.), LNCS, vol. 1807, Springer, 2000, pp. 19–34.
[224] P. Gaudry , Fast genus 2 arithmetic based on theta functions, J. Math. Crypt. 1(3) (2007), 243–265.
[225] P. Gaudry , Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symb. Comput. 44(12) (2009), 1690–1702.
[226] P. Gaudry , F. Hess and N. P. Smart , Constructive and destructive facets of Weil descent on elliptic curves, J. Crypt. 15 (2002), 19–46.
[227] P. Gaudry and D. Lubicz , The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines, Finite Fields Appl. 15 (2009), 246–260.
[228] P. Gaudry and É. Schost , A low-memory parallel version of Matsuo, Chao, and Tsujii's algorithm. In ANTS VI ( D. A. Buell , ed.), LNCS, vol. 3076, Springer, 2004, pp. 208–222.
[229] P. Gaudry , E. Thomé , N. Thériault and C. Diem , A double large prime variation for small genus hyperelliptic index calculus, Math. Comp. 76(257) (2007), 475–492.
[230] C. Gentry , The geometry of provable security: some proofs of security in which lattices make a surprise appearance, The LLL Algorithm ( P. Q. Nguyen and B. Vallée , eds.), Springer, 2010, pp. 391–426.
[231] M. Girault , An identity-based identification scheme based on discrete logarithms modulo a composite number. In EUROCRYPT 1990 ( I. Damgàrd , ed.), LNCS, vol. 473, Springer, 1991, pp. 481–486.
[232] M. Girault , G. Poupard and J. Stern , On the fly authentication and signature schemes based on groups of unknown order, J. Crypt. 19 (2006), 463–487.
[233] O. Goldreich , S. Goldwasser and S. Halevi , Public-key cryptosystems from lattice reduction problem. In CRYPTO 1997 ( B. S. Kaliski Jr. , ed.), LNCS, vol. 1294, Springer, 1997, pp. 112–131.
[234] O. Goldreich , D. Ron and M. Sudan , Chinese remaindering with errrors, IEEE Trans. Inf. Theory 46(4) (2000), 1330–1338.
[235] S. Goldwasser , S. Micali and R. L. Rivest , A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput. 17(2) (1988), 281–308.
[236] G. Gong and L. Harn , Public-key cryptosystems based on cubic finite field extensions, IEEE Trans. Inf. Theory 45(7) (1999), 2601–2605.
[237] M. I. González Vasco , M. Näslund and I. E. Shparlinski , New results on the hardness of Diffie–Hellman bits, PKC 2004 ( F. Bao , R. H. Deng and J. Zhou , eds.), LNCS, vol. 2947, Springer, 2004, pp. 159–172.
[238] M. I. González Vasco and I. E. Shparlinski , On the security of Diffie–Hellman bits. In Cryptography and Computational Number Theory ( H. Wang K. Y. Lam , I. E. Shparlinski and C. Xing , eds.), Progress in Computer Science and Applied Logic, Birkhäuser, 2001, pp. 257–268.
[239] D. M. Gordon , On the number of elliptic pseudoprimes, Math. Comp. 52(185) (1989), 231–245.
[240] D. M. Gordon and K. S. McCurley , Massively parallel computation of discrete logarithms. In CRYPTO 1992 ( E. F. Brickell , ed.), LNCS, vol. 740, Springer, 1993, pp. 312–323.
[241] R. Granger , F. Hess , R. Oyono , N. Thériault and F. Vercauteren , Ate pairing on hyperelliptic curves. In EUROCRYPT 2007 ( M. Naor , ed.), LNCS, vol. 4515, Springer, 2007, pp. 430–447.
[242] R. Granger and F. Vercauteren , On the discrete logarithm problem on algebraic tori. In CRYPTO 2005 ( V. Shoup , ed.), LNCS, vol. 3621, Springer, 2005, pp. 66–85.
[243] A. Granville , Smooth numbers: computational number theory and beyond. In Algorithmic Number Theory ( J. P. Buhler and P. Stevenhagen , eds.), MSRI Proceedings, vol. 44, Cambridge University Press, 2008, pp. 267–323.
[244] B. H. Gross , Heights and the special values of L-series. In CMS Conf. Proc., vol. 7, 1987, pp. 115–187.
[245] M. Grötschel , L. Lovász and A. Schrijver , Geometric Algorithms and Combinatorial Optimization, Springer, 1993.
[246] R. K. Guy , Unsolved Problems in Number Theory, 2nd edn, Springer, 1994.
[247] J. L. Hafner and K. S. McCurley , Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20(6) (1991), 1068–1083.
[248] D. Hankerson , A. Menezes and S. Vanstone , Guide to Elliptic Curve Cryptography, Springer, 2004.
[249] G. Hanrot and D. Stehlé , Improved analysis of Kannan's shortest lattice vector algorithm. In CRYPTO 2007 ( A. Menezes , ed.), LNCS, vol. 4622, Springer, 2007, pp. 170–186.
[250] G. H. Hardy and E. M. Wright , An Introduction to the Theory of Numbers, 5th edn, Oxford University Press, 1980.
[251] R. Harley , Fast Arithmetic on Genus Two Curves, Preprint, 2000.
[252] R. Hartshorne , Algebraic Geometry, GTM, vol. 52, Springer, 1997.
[253] J. Håstad and M. Näslund , The security of all RSA and discrete log bits, J. ACM 51(2) (2004), 187–230.
[254] G. Havas , B. S. Majewski and K. R. Matthews , Extended GCD and Hermite normal form algorithms via lattice basis reduction, Experimental Math. 7(2) (1998), 125–136.
[255] B. Helfrich , Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, Theor. Comput. Sci. 41 (1985), 125–139.
[256] F. Hess , A note on the Tate pairing of curves over finite fields, Arch. Math. 82 (2004), 28–32.
[257] F. Hess , Pairing lattices. In Pairing 2008 ( S. D. Galbraith and K. G. Paterson , eds.), LNCS, vol. 5209, Springer, 2008, pp. 18–38.
[258] F. Hess , N. Smart and F. Vercauteren , The eta pairing revisited, IEEE Trans. Inf. Theory 52(10) (2006), 4595–4602.
[259] N. J. Higham , Accuracy and Stability of Numerical Algorithms, 2nd edn, SIAM, 2002.
[260] Y. Hitchcock , P. Montague , G. Carter and E. Dawson , The efficiency of solving multiple discrete logarithm problems and the implications for the security of fixed elliptic curves, Int. J. Inf. Secur. 3 (2004), 86–98.
[261] J. Hoffstein , J. Pipher and J. H. Silverman , An Introduction to Mathematical Cryptography, Springer, 2008.
[262] J. Hoffstein and J. H. Silverman , Random small Hamming weight products with applications to cryptography, Discrete Appl. Math. 130(1) (2003), 37–49.
[263] D. Hofheinz and E. Kiltz , The group of signed quadratic residues and applications. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 637–653.
[264] S. Hohenberger and B. Waters , Short and stateless signatures from the RSA assumption. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 654–670.
[265] J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
[266] J. Horwitz and R. Venkatesan , Random Cayley digraphs and the discrete logarithm. In ANTS V ( C. Fieker and D. R. Kohel , eds.), LNCS, vol. 2369, Springer, 2002, pp. 416–430.
[267] E. W. Howe , On the group orders of elliptic curves over finite fields, Compositio Mathematica 85 (1993), 229–247.
[268] N. Howgrave-Graham , Finding small roots of univariate modular equations revisited. In IMA Cryptography and Coding ( M. Darnell , ed.), LNCS, vol. 1355, Springer, 1997, pp. 131–142.
[269] N. Howgrave-Graham , Approximate integer common divisors, Cryptography and Lattices (CaLC) ( J. H. Silverman , ed.), LNCS, vol. 2146, Springer, 2001, pp. 51–66.
[270] N. Howgrave-Graham and N. P. Smart , Lattice attacks on digital signature schemes, Des. Codes Crypt. 23 (2001), 283–290.
[271] T. W. Hungerford , Algebra, GTM vol. 73, Springer, 1974.
[272] D. Husemöller , Elliptic Curves, 2nd edn, GTM, vol. 111, Springer, 2004.
[273] T. Icart , How to hash into elliptic curves. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 303–316.
[274] T. Iijima , K. Matsuo , J. Chao and S. Tsujii , Construction of Frobenius maps of twist elliptic curves and its application to elliptic scalar multiplication. In Symposium on Cryptography and Information Security (SCIS) 2002, IEICE Japan, 2002, pp. 699–702.
[275] T. Jager and J. Schwenk , On the equivalence of generic group models. In ProvSec 2008 ( K. Chen J. Baek , F. Bao and X. Lai , eds.), LNCS, vol. 5324, Springer, 2008, pp. 200–209.
[276] D. Jao , D. Jetchev and R. Venkatesan , On the bits of elliptic curve Diffie–Hellman keys. In INDOCRYPT 2007 ( K. Srinathan , C. Pandu Rangan and M. Yung , eds.), LNCS, vol. 4859, Springer, 2007, pp. 33–47.
[277] D. Jao , S. D. Miller and R. Venkatesan , Do all elliptic curves of the same order have the same difficulty of discrete log?. In ASIACRYPT 2005 ( B. K. Roy , ed.), LNCS, vol. 3788, Springer, 2005, pp. 21–40.
[278] D. Jao , S. D. Miller and R. Venkatesan , Expander graphs based on GRH with an application to elliptic curve cryptography, J. Number Theory 129(6) (2009), 1491–1504.
[279] D. Jao and V. Soukharev , A subexponential algorithm for evaluating large degree isogenies. In ANTS IX ( G. Hanrot , F. Morain and E. Thomé , eds.), LNCS, vol. 6197, Springer, 2010, pp. 219–233.
[280] D. Jao and K. Yoshida , Boneh–Boyen signatures and the strong Diffie–Hellman problem. In Pairing 2009 ( H. Shacham and B. Waters , eds.), LNCS, vol. 5671, Springer, 2009, pp. 1–16.
[281] D. Jetchev and R. Venkatesan , Bits security of the elliptic curve Diffie–Hellman secret keys. In CRYPTO 2008 ( D. Wagner , ed.), LNCS, vol. 5157, Springer, 2008, pp. 75–92.
[282] Z.-T. Jiang , W.-L. Xu and Y.-M. Wang , Polynomial analysis of DH secrete key and bit security, Wuhan University Journal of Natural Sciences 10(1) (2005), no. 1, 239–242.
[283] A. Joux , Algorithmic Cryptanalysis, Chapman & Hall/CRC, 2009.
[284] A. Joux and R. Lercier , The function field sieve in the medium prime case. In EUROCRYPT 2006 ( S. Vaudenay , ed.), LNCS, vol. 4004, Springer, 2006.
[285] A. Joux , R. Lercier , N. P. Smart and F. Vercauteren , The number field sieve in the medium prime case. In CRYPTO 2006 ( C. Dwork , ed.), LNCS, vol. 4117, Springer, 2006, pp. 326–344.
[286] M. Joye and G. Neven , Identity-based cryptography, Cryptology and Information Security, vol. 2, IOS Press, 2008.
[287] M. Joye and S.-M. Yen , Optimal left-to-right binary signed-digit recoding, IEEE Trans. Computers 49(7) (2000), 740–748.
[288] M. J. Jacobson Jr. , N. Koblitz , J. H. Silverman , A. Stein and E. Teske , Analysis of the Xedni calculus attack, Des. Codes Crypt. 20(1) (2000), 1–64.
[289] M. J. Jacobson Jr. and A. J. van der Poorten , Computational aspects of NUCOMP. In ANTS V ( C. Fieker and D. R. Kohel , eds.), LNCS, vol. 2369, Springer, 2002, pp. 120–133.
[290] C. S. Jutla , On finding small solutions of modular multivariate polynomial equations. In EUROCRYPT 1998 ( K. Nyberg , ed.), LNCS, vol. 1403, Springer, 1998, pp. 158–170.
[291] M. Kaib and H. Ritter , Block reduction for arbitrary norms, Technical Report, Universität Frankfurt am Main, 1994.
[292] M. Kaib and C.-P. Schnorr , The generalized Gauss reduction algorithm, Journal of Algorithms 21(3) (1996), 565–578.
[293] B. S. Kaliski Jr. , Elliptic curves and cryptography: a pseudorandom bit generator and other tools, Ph.D. thesis, MIT, 1988.
[294] W. van der Kallen , Complexity of the Havas, Majewski, Matthews LLL Hermite normal form algorithm, J. Symb. Comput. 30(3) (2000), 329–337.
[295] R. Kannan , Improved algorithms for integer programming and related lattice problems. In Symposium on the Theory of Computing (STOC), ACM, 1983, pp. 193–206.
[296] R. Kannan , Minkowski's convex body theorem and integer programming, Mathematics of Operations Research 12(3) (1987), 415–440.
[297] R. Kannan and A. Bachem , Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), 499–507.
[298] M. Katagi , T. Akishita , I. Kitamura and T. Takagi , Some improved algorithms for hyperelliptic curve cryptosystems using degenerate divisors. In ICISC 2004 ( C. Park and S. Chee , eds.), LNCS, vol. 3506, Springer, 2004, pp. 296–312.
[299] M. Katagi , I. Kitamura , T. Akishita and T. Takagi , Novel efficient implementations of hyperelliptic curve cryptosystems using degenerate divisors. In WISA 2004 ( C.-H. Lim and M. Yung , eds.), LNCS, vol. 3325, Springer, 2004, pp. 345–359.
[300] J. Katz and Y. Lindell , Introduction to Modern Cryptography, Chapman & Hall/CRC, 2008.
[301] J. H. Kim , R. Montenegro , Y. Peres and P. Tetali , A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm. In ANTS VIII ( A. J. van der Poorten and A. Stein , eds.), LNCS, vol. 5011, Springer, 2008, pp. 402–415.
[302] J. H. Kim , R. Montenegro and P. Tetali , Near optimal bounds for collision in Pollard rho for discrete log. In Foundations of Computer Science (FOCS), IEEE, 2007, pp. 215–223.
[303] B. King , A point compression method for elliptic curves defined over GF(2n). In PKC 2004 ( F. Bao , R. H. Deng , and J. Zhou , eds.), LNCS, vol. 2947, Springer, 2004, pp. 333–345.
[304] S. Kim and J.-H. Cheon , A parameterized splitting system and its application to the discrete logarithm problem with low Hamming weight product exponents. In PKC 2008 ( R. Cramer , ed.), LNCS, vol. 4939, Springer, 2008, pp. 328–343.
[305] J. F. C. Kingman and S. J. Taylor , Introduction to Measure Theory and Probability, Cambridge University Press, 1966.
[306] P. N. Klein , Finding the closest lattice vector when it's unusually close, Symposium on Discrete Algorithms (SODA), ACM/SIAM, 2000, pp. 937–941.
[307] E. W. Knudsen , Elliptic scalar multiplication using point halving. In ASIACRYPT 1999 ( K.-Y. Lam , E. Okamoto and C. Xing , eds.), LNCS, vol. 1716, Springer, 1999, pp. 135–149.
[308] D. E. Knuth , Art of Computer Programming, Volume 2: Semi-Numerical Algorithms, 3rd edn, Addison-Wesley, 1997.
[309] N. Koblitz , Elliptic curve cryptosystems, Math. Comp. 48(177) (1987), 203–209.
[310] N. Koblitz , Primality of the number of points on an elliptic curve over a finite field, Pacific J. Math. 131(1) (1988), 157–165.
[311] N. Koblitz , Hyperelliptic cryptosystems, J. Crypt. 1 (1989), 139–150.
[312] N. Koblitz , CM curves with good cryptographic properties. In CRYPTO 1991 ( J. Feigenbaum , ed.), LNCS, vol. 576, Springer, 1992, pp. 279–287.
[313] N. Koblitz , A Course in Number Theory and Cryptography, 2nd edn, GTM vol. 114, Springer, 1994.
[314] C. K. Koç and T. Acar , Montgomery multplication in GF(2k), Des. Codes Crypt. 14(1) (1998), 57–69.
[315] D. R. Kohel , Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California, Berkeley, 1996.
[316] D. R. Kohel , Constructive and Destructive Facets of Torus-based Cryptography, Preprint, 2004.
[317] D. R. Kohel and I. E. Shparlinski , On exponential sums and group generators for elliptic curves over finite fields. In ANTS IV ( W. Bosma , ed.), LNCS, vol. 1838, Springer, 2000, pp. 395–404.
[318] S. Kozaki , T. Kutsuma and K. Matsuo , Remarks on Cheon's algorithms for pairing-related problems, Pairing 2007 ( T. Takagi , T. Okamoto , E. Okamoto and T. Okamoto , eds.), LNCS, vol. 4575, Springer, 2007, pp. 302–316.
[319] M. Kraitchik , Théorie des Nombres, Vol. 1, Gauthier-Villars, Paris, 1922.
[320] F. Kuhn and R. Struik , Random walks revisited: extensions of Pollard's rho algorithm for computing multiple discrete logarithms. In SAC 2001 ( S. Vaudenay and A. M. Youssef , eds.), LNCS, vol. 2259, Springer, 2001, pp. 212–229.
[321] R. M. Kuhn , Curves of genus 2 with split Jacobian, Trans. Amer. Math. Soc. 307(1) (1988), 41–49.
[322] R. Kumar and D. Sivakumar , Complexity of SVP – a reader's digest, SIGACT News, Complexity Theory Column 32 (2001), 13.
[323] K. Kurosawa and Y. Desmedt , A new paradigm of hybrid encryption scheme. In CRYPTO 2004 ( M. K. Franklin , ed.), LNCS, vol. 3152, Springer, 2004, pp. 426–442.
[324] J. C. Lagarias , H. W. Lenstra Jr. and C.-P. Schnorr , Korkin–Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10(4) (1990), 333–348.
[325] C. Lanczos , Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bureau of Standards 49 (1952), 33–53.
[326] S. Lang , Introduction to Algebraic Geometry, Wiley, 1964.
[327] S. Lang , Algebraic Number Theory, GTM, vol. 110, Springer, 1986.
[328] S. Lang , Elliptic Functions, 2nd edn, GTM, vol. 112, Springer, 1987.
[329] S. Lang , Algebra, 3rd edn, Addison-Wesley, 1993.
[330] T. Lange , Koblitz curve cryptosystems, Finite Fields Appl. 11(2) (2005), 200–229.
[331] E. Lee , H.-S. Lee and C.-M. Park , Efficient and Generalized Pairing Computation on Abelian Varieties, IEEE Trans. Inf. Theory 55(4) (2009), 1793–1803.
[332] A. K. Lenstra , Factorization of polynomials. In Computational Methods in Number Theory, ( H. W. Lenstra Jr. and R. Tijdeman , eds.) Mathematical Center Tracts 154, Mathematisch Centrum Amsterdam, 1984, pp. 169–198.
[333] A. K. Lenstra , Integer factoring, Des. Codes Crypt. 19(2/3) (2000), 101–128.
[334] A. K. Lenstra and H. W. Lenstra Jr. , The Development of the Number Field Sieve, LNM, vol. 1554, Springer, 1993.
[335] A. K. Lenstra , H. W. Lenstra Jr. and L. Lovász , Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.
[336] A. K. Lenstra and I. E. Shparlinski , Selective forgery of RSA signatures with fixed-pattern padding. In PKC 2002 ( D. Naccache and P. Paillier , eds.), LNCS, vol. 2274, Springer, 2002, pp. 228–236.
[337] A. K. Lenstra and E. R. Verheul , The XTR public key system. In CRYPTO 2000 ( M. Bellare , ed.), LNCS, vol. 1880, Springer, 2000, pp. 1–19.
[338] A. K. Lenstra and E. R. Verheul , Fast irreducibility and subgroup membership testing in XTR. In PKC 2001 ( K. Kim , ed.), LNCS, vol. 1992, Springer, 2001, pp. 73–86.
[339] H. W. Lenstra Jr. , Factoring integerswith elliptic curves, Annals of Mathematics 126(3) (1987), 649–673.
[340] H. W. Lenstra Jr. , Elliptic curves and number theoretic algorithms. In Proc. International Congr. Math., Berkeley 1986, AMS, 1988, pp. 99–120.
[341] H. W. Lenstra Jr. , Finding isomorphisms between finite fields, Math. Comp. 56(193) (1991), 329–347.
[342] H. W. Lenstra Jr. , J. Pila and C. Pomerance , A hyperelliptic smoothness test I, Phil. Trans. R. Soc. Lond. A 345 (1993), 397–408.
[343] H. W. Lenstra Jr. and C. Pomerance , A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5(3) (1992), no. 3, 483–516.
[344] R. Lercier , Computing isogenies in F2 n . In ANTS II ( H. Cohen , ed.), LNCS, vol. 1122, Springer, 1996, pp. 197–212.
[345] R. Lercier and F. Morain , Algorithms for computing isogenies between elliptic curves, Computational Perspectives on Number Theory ( D. A. Buell and J. T. Teitelbaum , eds.), Studies in Advanced Mathematics, vol. 7, AMS, 1998, pp. 77–96.
[346] R. Lercier and T. Sirvent , On Elkies subgroups of ℓ-torsion points in elliptic curves defined over a finite field, J. Théor. Nombres Bordeaux 20(3) (2008), 783–797.
[347] G. Leurent and P. Q. Nguyen , How risky is the random oracle model?. In CRYPTO 2009 ( S. Halevi , ed.), LNCS, vol. 5677, Springer, 2009, pp. 445–464.
[348] K.-Z. Li and F. Oort , Moduli of supersingular abelian varieties, LNM, vol. 1680, Springer, 1998.
[349] W.-C. Li , M. Näslund and I. E. Shparlinski , Hidden number problem with the trace and bit security of XTR and LUC. In CRYPTO 2002 ( M. Yung , ed.), LNCS, vol. 2442, Springer, 2002, pp. 433–448.
[350] R. Lidl and H. Niederreiter , Introduction to Finite Fields and Their Applications, Cambridge University Press, 1994.
[351] R. Lidl and H. Niederreiter , Finite Fields, Cambridge University Press, 1997.
[352] R. Lindner and C. Peikert , Better key sizes (and attacks) for LWE-based encryption, CT-RSA 2011 ( A. Kiayias , ed.), LNCS, vol. 6558, 2011, pp. 1–23.
[353] P. Lockhart , On the discriminant of a hyperelliptic curve, Trans. Amer. Math. Soc. 342(2) (1994), 729–752.
[354] D. L. Long and A. Wigderson , The discrete logarithm hides O(log n) bits, SIAM J. Comput. 17(2) (1988), 363–372.
[355] D. Lorenzini , An Invitation to Arithmetic Geometry, Graduate Studies in Mathematics, vol. 106, AMS, 1993.
[356] L. Lovász , An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, 1986.
[357] L. Lovász and H. E. Scarf , The generalized basis reduction algorithm, Mathematics of Operations Research 17(3) (1992), 751–764.
[358] R. Lovorn Bender and C. Pomerance , Rigorous discrete logarithm computations in finite fields via smooth polynomials. In Computational Perspectives on Number Theory ( D. A. Buell and J. T. Teitelbaum , eds.), Studies in Advanced Mathematics, vol. 7, AMS, 1998, pp. 221–232.
[359] M. Luby , Pseudorandomness and Cryptographic Applications, Princeton, 1996.
[360] H. Lüneburg , On a little but useful algorithm. In AAECC-3, 1985 ( J. Calmet , ed.), LNCS, vol. 229, Springer, 1986, pp. 296–301.
[361] C. Mauduit and A. Sárközy , On finite pseudorandom binary sequences I: measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), 365–377.
[362] U. M. Maurer , Towards the equivalence of breaking the Diffie–Hellman protocol and computing discrete logarithms. In CRYPTO 1994 ( Y. Desmedt , ed.), LNCS, vol. 839, Springer, 1994, pp. 271–281.
[363] U. M. Maurer , Fast generation of prime numbers and secure public-key cryptographic parameters, J. Crypt. 8(3) (1995), 123–155.
[364] U. M. Maurer , Abstract models of computation in cryptography. In IMA Int. Conf. ( N. P. Smart , ed.), LNCS, vol. 3796, Springer, 2005, pp. 1–12.
[365] U. M. Maurer and S. Wolf , Diffie–Hellman oracles. In CRYPTO 1996 ( N. Koblitz , ed.), LNCS, vol. 1109, Springer, 1996, pp. 268–282.
[366] U. M. Maurer and S. Wolf , On the complexity of breaking the Diffie–Hellman protocol, Technical Report 244, Institute for Theoretical Computer Science, ETH Zurich, 1996.
[367] U. M. Maurer and S. Wolf , Lower bounds on generic algorithms in groups. In EUROCRYPT 1998 ( K. Nyberg , ed.), LNCS, vol. 1403, Springer, 1998, pp. 72–84.
[368] U. M. Maurer and S. Wolf , The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms, SIAM J. Comput. 28(5) (1999), 1689–1721.
[369] U. M. Maurer and S. Wolf , The Diffie–Hellman protocol, Des. Codes Crypt. 19(2/3) (2000), 147–171.
[370] A. May , New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, Paderborn, 2003.
[371] A. May , Using LLL-reduction for solving RSA and factorization problems: a survey. In The LLL Algorithm ( P. Q. Nguyen and B. Vallée , eds.), Springer, 2010, pp. 315–348.
[372] J. F. McKee , Subtleties in the distribution of the numbers of points on elliptic curves over a finite prime field, J. London Math. Soc. 59(2) (1999), 448–460.
[373] W. Meier and O. Staffelbach , Efficient multiplication on certain non-supersingular elliptic curves. In CRYPTO 1992 ( E. F. Brickell , ed.), LNCS, vol. 740, Springer, 1993, pp. 333–344.
[374] A. Menezes and S. A. Vanstone , The implementation of elliptic curve cryptosystems. In AUSCRYPT 1990 ( J. Seberry and J. Pieprzyk , eds.), LNCS, vol. 453, Springer, 1990, pp. 2–13.
[375] A. J. Menezes , T. Okamoto and S. A. Vanstone , Reducing elliptic curve logarithms to a finite field, IEEE Trans. Inf. Theory 39(5) (1993), 1639–1646.
[376] A.J. Menezes , P.C. van Oorschot and S.A. Vanstone , Handbook of Applied Cryptography, CRC Press, 1996.
[377] J.-F. Mestre , La méthode des graphes. exemples et applications, Proceedings of the International Conference on Class Numbers and Fundamental Units of Algebraic Number fields (Katata, 1986), Nagoya University, 1986, pp. 217–242.
[378] D. Micciancio and S. Goldwasser , Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer, 2002.
[379] D. Micciancio and O. Regev , Lattice-based cryptography. In Post Quantum Cryptography ( D. J. Bernstein , J. Buchmann and E. Dahmen , eds.), Springer, 2009, pp. 147–191.
[380] D. Micciancio and P. Voulgaris , Faster exponential time algorithms for the shortest vector problem. In SODA ( M. Charikar , ed.), SIAM, 2010, pp. 1468–1480.
[381] D. Micciancio and B. Warinschi , A linear space algorithm for computing the Hermite normal form. In ISSAC, 2001, pp. 231–236.
[382] S. D. Miller and R. Venkatesan , Spectral analysis of Pollard rho collisions. In ANTS VII ( F. Hess , S. Pauli and M. E. Pohst , eds.), LNCS, vol. 4076, Springer, 2006, pp. 573–581.
[383] V. S. Miller , Short programs for functions on curves, Unpublished manuscript, 1986.
[384] V. S. Miller , Use of elliptic curves in cryptography. In CRYPTO 1985 ( H. C. Williams , ed.), LNCS, vol. 218, Springer, 1986, pp. 417–426.
[385] V. S. Miller , The Weil pairing, and its efficient calculation, J. Crypt. 17(4) (2004), 235–261.
[386] A. Miyaji , T. Ono and H. Cohen , Efficient elliptic curve exponentiation. In ICICS 1997 ( Y. Han , T. Okamoto and S. Qing , eds.), LNCS, vol. 1334, Springer, 1997, pp. 282–291.
[387] B. Möller , Algorithms for multi-exponentiation. In SAC 2001 ( S. Vaudenay and A. M. Youssef , eds.), LNCS, vol. 2259, Springer, 2001, pp. 165–180.
[388] B. Möller , Improved techniques for fast exponentiation. In ICISC 2002 ( P.-J. Lee and C.-H. Lim , eds.), LNCS, vol. 2587, Springer, 2003, pp. 298–312.
[389] B. Möller , Fractional windows revisited: improved signed-digit representations for efficient exponentiation. In ICISC 2004 ( C. Park and S. Chee , eds.), LNCS, vol. 3506, Springer, 2005, pp. 137–153.
[390] R. Montenegro and P. Tetali , How long does it take to catch a wild kangaroo?. In Symposium on Theory of Computing (STOC), 2009, pp. 553–559.
[391] P. L. Montgomery , Modular multiplication without trial division, Math. Comp. 44(170) (1985), 519–521.
[392] P. L. Montgomery , Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48(177) (1987), 243–264.
[393] F. Morain and J.-L. Nicolas , On Cornacchia's Algorithm for Solving the Diophantine Equation u2 + dv2 = m, Preprint, 1990.
[394] F. Morain and J. Olivos , Speeding up the computations on an elliptic curve using addition subtraction chains. In Theoretical Informatics and Applications, vol. 24, 1990, pp. 531–543.
[395] C. J. Moreno , Algebraic Curves over Finite Fields, Cambridge University Press, 1991.
[396] W. H. Mow , Universal lattice decoding: principle and recent advances, Wireless Communications and Mobile Computing 3(5) (2003), 553–569.
[397] V. Müller , Fast multiplication on elliptic curves over small fields of characteristic two, J. Crypt. 11(4) (1998), 219–234.
[398] D. Mumford , Abelian Varieties, Oxford University Press, 1970.
[399] D. Mumford , Tata lectures on theta II, Progess in Mathematics, vol. 43, Birkhäuser, 1984.
[400] M. R. Murty , Ramanujan graphs, J. Ramanujan Math. Soc. 18(1) (2003), 1–20.
[401] R. Murty and I. E. Shparlinski , Group structure of elliptic curves over finite fields and applications, Topics in Geometry, Coding Theory and Cryptography ( A. Garcia and H. Stichtenoth , eds.), Springer-Verlag, 2006, pp. 167–194.
[402] A. Muzereau , N. P. Smart and F. Vercauteren , The equivalence between the DHP and DLP for elliptic curves used in practical applications, LMS J. Comput. Math. 7 (2004), 50–72.
[403] D. Naccache , D. M'Raïhi , S. Vaudenay and D. Raphaeli , Can D.S.A. be improved? Complexity trade-offs with the digital signature standard. In EUROCRYPT 1994 ( A. De Santis , ed.), LNCS, vol. 950, Springer, 1995, pp. 77–85.
[404] D. Naccache and I. E. Shparlinski , Divisibility, smoothness and cryptographic applications, Algebraic Aspects of Digital Communications ( T. Shaska and E. Hasimaj , eds.) NATO Series for Peace and Security, 24 IOS Press, 2009, pp. 115–173.
[405] V. I. Nechaev , Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes 55(2) (1994), 165–172.
[406] G. Neven , N. P. Smart and B. Warinschi , Hash function requirements for Schnorr signatures, J. Math. Crypt. 3(1) (2009), 69–87.
[407] P. Nguyen and D. Stehlé , Floating-point LLL revisited. In EUROCRYPT 2005 ( R. Cramer , ed.), LNCS, vol. 3494, Springer, 2005, pp. 215–233.
[408] P. Nguyen and D. Stehlé , Low-dimensional lattice basis reduction revisited, ACM Transactions on Algorithms 5(4:46) (2009), 1–48.
[409] P. Q. Nguyen , Public key cryptanalysis. In Recent Trends in Cryptography ( I. Luengo , ed.), AMS, 2009, pp. 67–119.
[410] P. Q. Nguyen and O. Regev , Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In EUROCRYPT 2006 ( S. Vaudenay , ed.), LNCS, vol. 4004, Springer, 2006, pp. 271–288.
[411] P. Q. Nguyen and I. E. Shparlinski , The insecurity of the digital signature algorithm with partially known nonces, J. Crypt. 15(3) (2002), 151–176.
[412] P. Q. Nguyen and I. E. Shparlinski , The insecurity of the elliptic curve digital signature algorithm with partially known nonces, Des. Codes Crypt. 30(2) (2003), 201–217.
[413] P. Q. Nguyen and D. Stehlé , Low-dimensional lattice basis reduction revisited. In ANTS VI ( D. A. Buell , ed.), LNCS, vol. 3076, Springer, 2004, pp. 338–357.
[414] P. Q. Nguyen and J. Stern , Lattice reduction in cryptology: an update. In ANTS IV ( W. Bosma , ed.), LNCS, vol. 1838, Springer, 2000, pp. 85–112.
[415] P. Q. Nguyen and J. Stern , The two faces of lattices in cryptology. In Cryptography and Lattices (CaLC) ( J. H. Silverman , ed.), LNCS, vol. 2146, Springer, 2001, pp. 146–180.
[416] P. Q. Nguyen and B. Vallée , The LLL algorithm: survey and applications, Information Security and Cryptography, Springer, 2009.
[417] P. Q. Nguyen and T. Vidick , Sieve algorithms for the shortest vector problem are practical, J. Math. Crypt. 2(2) (2008), 181–207.
[418] H. Niederreiter , A new efficient factorization algorithm for polynomials over small finite fields, Applicable Algebra in Engineering, Communication and Computing 4(2) (1993), 81–87.
[419] G. Nivasch , Cycle detection using a stack, Inf. Process. Lett. 90(3) (2004), 135–140.
[420] I. Niven , H. S. Zuckerman and H. L. Montgomery , An Introduction to the Theory of Numbers, 5th edn, Wiley, 1991.
[421] A. M. Odlyzko , Discrete logarithms in finite fields and their cryptographic significance. In EUROCRYPT 1984 ( T. Beth , N. Cot and I. Ingemarsson , eds.), LNCS, vol. 209, Springer, 1985, pp. 224–314.
[422] P. C. van Oorschot and M. J. Wiener , On Diffie–Hellman key agreement with short exponents. In EUROCRYPT 1996 ( U. M. Maurer , ed.), LNCS, vol. 1070, Springer, 1996, pp. 332–343.
[423] P. C. van Oorschot and M. J. Wiener , Parallel collision search with cryptanalytic applications, J. Crypt. 12(1) (1999), 1–28.
[424] P. Paillier , Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT 1999 ( J. Stern , ed.), LNCS, vol. 1592, Springer, 1999, pp. 223–238.
[425] P. Paillier , Impossibility proofs for RSA signatures in the standard model. In CT-RSA 2007 ( M. Abe , ed.), LNCS, vol. 4377, Springer, 2007, pp. 31–48.
[426] P. Paillier and D. Vergnaud , Discrete-log-based signatures may not be equivalent to discrete log.In ASIACRYPT 2005 ( B. K. Roy , ed.), LNCS, vol. 3788, Springer, 2005, pp. 1–20.
[427] P. Paillier and J. L. Villar , Trading one-wayness against chosen-ciphertext security in factoring-based encryption. In ASIACRYPT 2006 ( X. Lai and K. Chen , eds.), LNCS, vol. 4284, Springer, 2006, pp. 252–266.
[428] S. Patel and G. S. Sundaram , An efficient discrete log pseudo random generator. In CRYPTO 1998 ( H. Krawczyk , ed.), LNCS, vol. 1462, Springer, 1998, pp. 304–317.
[429] S. Paulus and H.-G. Rück , Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68(227) (1999), 1233–1241.
[430] R. Peralta , Simultaneous security of bits in the discrete log. In EUROCRYPT 1985 ( F. Pichler , ed.), LNCS, vol. 219, Springer, 1986, pp. 62–72.
[431] A. K. Pizer , Ramanujan graphs. In Computational Perspectives on Number Theory ( D. A. Buell and J. T. Teitelbaum , eds.), Studies in Advanced Mathematics, vol. 7, AMS, 1998, pp. 159–178.
[432] S. Pohlig and M. Hellman , An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inf. Theory 24 (1978), 106–110.
[433] D. Pointcheval and J. Stern , Security arguments for digital signatures and blind signatures, J. Crypt. 13(3) (2000), 361–396.
[434] D. Pointcheval and S. Vaudenay , On provable security for digital signature algorithms, Technical report LIENS 96-17, École Normale Supérieure, 1996.
[435] J. M. Pollard , Theorems on factorisation and primality testing, Proc. Camb. Phil. Soc. 76 (1974), 521–528.
[436] J. M. Pollard , A Monte Carlo method for factorization, BIT 15 (1975), 331–334.
[437] J. M. Pollard , Monte Carlo methods for index computation (mod p), Math. Comp. 32(143) (1978), 918–924.
[438] J. M. Pollard , Kangaroos, monopoly and discrete logarithms, J. Crypt. 13(4) (2000), 437–447.
[439] C. Pomerance , A tale of two sieves, Notices of the Amer. Math. Soc. 43 (1996), 1473–1485.
[440] V. R. Pratt , Every prime has a succinct certificate, SIAM J. Comput. 4(3) (1974), 214–220.
[441] X. Pujol and D. Stehlé , Rigorous and efficient short lattice vectors enumeration. In ASIACRYPT 2008 ( J. Pieprzyk , ed.), LNCS, vol. 5350, Springer, 2008, pp. 390–405.
[442] G. Qiao and K.-Y Lam , RSA signature algorithm for microcontroller implementation. In CARDIS 1998 ( J.-J. Quisquater and B. Schneier , eds.), LNCS, vol. 1820, Springer, 2000, pp. 353–356.
[443] J. J. Quisquater and C. Couvreur , Fast decipherment algorithm for RSA public-key cryptosystem, Electronics Letters (21) (1982), 905–907.
[444] M. O. Rabin , Digitalized signatures and public-key functions as intractable as factorization, Tech. Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, 1979.
[445] J.-F. Raymond and A. Stiglic , Security Issues in the Diffie–Hellman Key Agreement Protocol, Preprint, 2000.
[446] O. Regev , The learning with errors problem (invited survey), 25th Annual IEEE Conference on Computational Complexity, IEEE, 2010, pp. 191–204.
[447] M. Reid , Undergraduate Algebraic Geometry, Cambridge University Press, 1988.
[448] M. Reid , Graded rings and varieties in weighted projective space, Chapter of unfinished book, 2002.
[449] G. Reitwiesner , Binary arithmetic, Advances in Computers 1 (1960), 231–308.
[450] P. Rogaway , Formalizing human ignorance. In VIETCRYPT 2006 ( P. Q. Nguyen , ed.), LNCS, vol. 4341, Springer, 2006, pp. 211–228.
[451] S. Ross , A First Course in Probability, 6th edn, Prentice Hall, 2001.
[452] K. Rubin and A. Silverberg , Torus-based cryptography. In CRYPTO 2003 ( D. Boneh , ed.), LNCS, vol. 2729, Springer, 2003, pp. 349–365.
[453] K. Rubin and A. Silverberg , Compression in finite fields and torus-based cryptography, SIAM J. Comput. 37(5) (2008), 1401–1428.
[454] H.-G. Rück , A note on elliptic curves over finite fields, Math. Comp. 49(179) (1987), 301–304.
[455] H.-G. Rück , On the discrete logarithm in the divisor class group of curves, Math. Comp. 68(226) (1999), 805–806.
[456] A. Rupp , G. Leander , E. Bangerter , A. W. Dent and A.-R. Sadeghi , Sufficient conditions for intractability over black-box groups: generic lower bounds for generalized DL and DH problems. In ASIACRYPT 2008 ( J. Pieprzyk , ed.), LNCS, vol. 5350, Springer, 2008, pp. 489–505.
[457] A.-R. Sadeghi and M. Steiner , Assumptions related to discrete logarithms: why subtleties make a real difference. In EUROCRYPT 2001 ( B. Pfitzmann , ed.), LNCS, vol. 2045, Springer, 2001, pp. 244–261.
[458] A. Sárközy and C. L. Stewart , On pseudorandomness in families of sequences derived from the Legendre symbol, Periodica Math. Hung. 54(2) (2007), 163–173.
[459] T. Satoh , On Generalization of Cheon's Algorithm, Cryptology ePrint Archive, Report 2009/058, 2009.
[460] T. Satoh and K. Araki , Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Comment. Math. Univ. St. Paul. 47(1) (1998), 81–92.
[461] J. Sattler and C.-P. Schnorr , Generating random walks in groups, Ann. Univ. Sci. Budapest. Sect. Comput. 6 (1985), 65–79.
[462] A. Schinzel and M. Skalba , On equations y2 = xn + k in a finite field, Bull. Polish Acad. Sci. Math. 52(3) (2004), 223–226.
[463] O. Schirokauer , Using number fields to compute logarithms in finite fields, Math. Comp. 69(231) (2000), 1267–1283.
[464] O. Schirokauer , The special function field sieve, SIAM J. Discrete Math 16(1) (2002), 81–98.
[465] O. Schirokauer , The impact of the number field sieve on the discrete logarithm problem in finite fields. In Algorithmic Number Theory ( J. Buhler and P. Stevenhagen , eds.), MSRI publications, vol. 44, Cambridge University Press, 2008, pp. 397–420.
[466] O. Schirokauer , The number field sieve for integers of low weight, Math. Comp. 79(269) (2010), 583–602.
[467] O. Schirokauer , D. Weber and T. F. Denny , Discrete logarithms: the effectiveness of the index calculus method. In ANTS II ( H. Cohen , ed.), LNCS, vol. 1122, Springer, 1996, pp. 337–361.
[468] C.-P. Schnorr , A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53 (1987), 201–224.
[469] C.-P. Schnorr , Efficient identification and signatures for smart cards. In CRYPTO 1989 ( G. Brassard , ed.), LNCS, vol. 435, Springer, 1990, pp. 239–252.
[470] C.-P. Schnorr , Efficient signature generation by smart cards, J. Crypt. 4(3) (1991), 161–174.
[471] C.-P. Schnorr , Security of almost all discrete log bits, Electronic Colloquium on Computational Complexity (ECCC) 5(33) (1998), 1–13.
[472] C.-P. Schnorr , Progress on LLL and lattice reduction. In> The LLL Algorithm ( P. Q. Nguyen and B. Vallée , eds.), Springer, 2010, pp. 145–178.
[473] C.-P. Schnorr and M. Euchner , Lattice basis reduction: improved practical algorithms and solving subset sum problems, Math. Program. 66 (1994), 181–199.
[474] C.-P. Schnorr and H. W. Lenstra Jr. , A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43(167) (1984), 289–311.
[475] R. Schoof , Elliptic curves over finite fields and the computation of square roots (mod) p, Math. Comp. 44(170) (1985), 483–494.
[476] R. Schoof , Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A 46 (1987), 183–211.
[477] R. Schoof , Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), 219–254.
[478] A. Schrijver , Theory of Linear and Integer Programming, Wiley, 1986.
[479] R. Schroeppel , H. K. Orman , S. W. O'Malley and O. Spatscheck , Fast key exchange with elliptic curve systems. In CRYPTO 1995 ( D. Coppersmith , ed.), LNCS, vol. 963, Springer, 1995, pp. 43–56.
[480] E. Schulte-Geers , Collision search in a random mapping: some asymptotic results, Presentation at ECC 2000, Essen, Germany, 2000.
[481] M. Scott , Faster pairings using an elliptic curve with an efficient endomorphism. In INDOCRYPT 2005 ( S. Maitra , C. E. V. Madhavan and R. Venkatesan , eds.), LNCS, vol. 3797, Springer, 2005, pp. 258–269.
[482] R. Sedgewick , T. G. Szymanski and A. C.-C. Yao , The complexity of finding cycles in periodic functions, SIAM J. Comput. 11(2) (1982), 376–390.
[483] B. I. Selivanov , On waiting time in the scheme of random allocation of coloured particles, Discrete Math. Appl. 5(1) (1995), 73–82.
[484] I. A. Semaev , Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p, Math. Comp. 67(221) (1998), 353–356.
[485] I. A. Semaev , A 3-dimensional lattice reduction algorithm. In Cryptography and Lattices (CaLC) ( J. H. Silverman , ed.), LNCS, vol. 2146, Springer, 2001, pp. 181–193.
[486] I. A. Semaev , Summation Polynomials and the Discrete Logarithm Problem on Elliptic Curves, Cryptology ePrint Archive, Report 2004/031, 2004.
[487] J.-P. Serre , Sur la topologie des variétés algébriques en charactéristique p. In Symp. Int. Top. Alg., Mexico, 1958, pp. 24–53.
[488] J.-P. Serre , Local Fields, GTM, vol. 67, Springer, 1979.
[489] I. R. Shafarevich , Basic Algebraic Geometry, 2nd edn, Springer, 1995.
[490] J. O. Shallit , A Primer on Balanced Binary Representations, Preprint, 1992.
[491] A. Shallue and C. E. van de Woestijne , Construction of rational points on elliptic curves over finite fields. In ANTS VII ( F. Hess , S. Pauli and M. E. Pohst , eds.), LNCS, vol. 4076, Springer, 2006, pp. 510–524.
[492] D. Shanks , Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics, Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70.
[493] M. Shirase , D.-G. Han , Y. Hibino , H.-W. Kim and T. Takagi , Compressed XTR. In ACNS 2007 ( J. Katz and M. Yung , eds.), LNCS, vol. 4521, Springer, 2007, pp. 420–431.
[494] V. Shoup , Lower bounds for discrete logarithms and related problems. In EUROCRYPT 1997 ( W. Fumy , ed.), LNCS, vol. 1233, Springer, 1997, pp. 256–266.
[495] V. Shoup , On formal models for secure key exchange (version 4), 15 November 1999, Tech. report, IBM, 1999, Revision of Report RZ 3120.
[496] V. Shoup , OAEP reconsidered. In CRYPTO 2001 ( J. Kilian , ed.), LNCS, vol. 2139, Springer, 2001, pp. 239–259.
[497] V. Shoup , A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005.
[498] I. E. Shparlinski , Computing Jacobi symbols modulo sparse integers and polynomials and some applications, J. Algorithms 36 (2000), 241–252.
[499] I. E. Shparlinski , Cryptographic Applications of Analytic Number Theory, Birkhauser, 2003.
[500] I. E. Shparlinski , Playing “hide-and-seek” with numbers: the hidden number problem, lattices and exponential sums. In Public-Key Cryptography ( P. Garrett and D. Lieman , eds.), Proceedings of Symposia in Applied Mathematics, vol. 62, AMS, 2005, pp. 153–177.
[501] I. E. Shparlinski and A. Winterhof , A nonuniform algorithm for the hidden number problem in subgroups. In PKC 2004 ( F. Bao , R. H. Deng and J. Zhou , eds.), LNCS, vol. 2947, Springer, 2004, pp. 416–424.
[502] I. E. Shparlinski and A. Winterhof , A hidden number problem in small subgroups, Math. Comp. 74(252) (2005), 2073– 2080.
[503] A. Sidorenko , Design and analysis of provably secure pseudorandom generators, Ph.D. thesis, Eindhoven, 2007.
[504] C. L. Siegel , Lectures on the Geometry of Numbers, Springer, 1989.
[505] J. H. Silverman , The Arithmetic of Elliptic Curves, GTM, vol. 106, Springer, 1986.
[506] J. H. Silverman , Advanced Topics in the Arithmetic of Elliptic Curves, GTM, vol. 151, Springer, 1994.
[507] J. H. Silverman and J. Suzuki , Elliptic curve discrete logarithms and the index calculus. In ASIACRYPT 1998 ( K. Ohta and D. Pei , eds.), LNCS, vol. 1514, Springer, 1998, pp. 110–125.
[508] J. H. Silverman and J. Tate , Rational Points on Elliptic Curves, Springer, 1994.
[509] M. Sipser , Introduction to the Theory of Computation, Course Technology, 2005.
[510] M. Skalba , Points on elliptic curves over finite fields, Acta Arith. 117(3) (2005), 293–301.
[511] N. P. Smart , The discrete logarithm problem on elliptic curves of trace one, J. Cryptology 12(3) (1999), 193–196.
[512] N. P. Smart , Elliptic curve cryptosystems over small fields of odd characteristic, J. Crypt. 12(2) (1999), 141–151.
[513] N. P. Smart , Cryptography: An Introduction, McGraw-Hill, 2004.
[514] B. A. Smith , Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, J. Crypt. 22(4) (2009), 505–529.
[515] P. J. Smith and M. J. J. Lennon , LUC: a new public key system. In International Conference on Information Security ( E. Graham Dougall , ed.), IFIP Transactions, vol. A-37, North-Holland, 1993, pp. 103–117.
[516] P. J. Smith and C. Skinner , A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms. In ASIACRYPT 1994 ( J. Pieprzyk and R. Safavi-Naini , eds.), LNCS, vol. 917, Springer, 1994, pp. 357–364.
[517] J. A. Solinas , Efficient arithmetic on Koblitz curves, Des. Codes Crypt. 19 (2000), 195–249.
[518] J. A. Solinas , Low-weight binary representations for pairs of integers, Technical Report CORR 2001-41, 2001.
[519] M. Stam , On Montgomery-like representations of elliptic curves over GF(2k). In PKC 2003 ( Y. G. Desmedt , ed.), LNCS, vol. 2567, Springer, 2003, pp. 240–253.
[520] M. Stam , Speeding up subgroup cryptosystems, Ph.D. thesis, Eindhoven, 2003.
[521] M. Stam and A. K. Lenstra , Speeding up XTR. In ASIACRYPT 2001 ( C. Boyd , ed.), LNCS, vol. 2248, Springer, 2001, pp. 125–143.
[522] H. M. Stark , Class-numbers of complex quadratic fields. In Modular Functions of One Variable I ( W. Kuyk , ed.), LNM, vol. 320, Springer, 1972, pp. 153–174.
[523] D. Stehlé , Floating point LLL: Theoretical and practical aspects. In The LLL Algorithm ( P. Q. Nguyen and B. Vallée , eds.), Springer, 2010, pp. 179–213.
[524] D. Stehlé and P. Zimmermann , A binary recursive GCD algorithm. In ANTS VI ( D. A. Buell , ed.), LNCS, vol. 3076, Springer, 2004, pp. 411–425.
[525] P. Stevenhagen , The number field sieve. In Algorithmic Number Theory ( J. Buhler and P. Stevenhagen , eds.), MSRI publications, Cambridge University Press, 2008, pp. 83–99.
[526] I. Stewart , Galois Theory, 3rd edn, Chapman & Hall, 2003.
[527] I. Stewart and D. Tall , Algebraic Number Theory and Fermat's Last Theorem, 3rd edn, AK Peters, 2002.
[528] H. Stichtenoth , Die Hasse–Witt Invariante eines Kongruenzfunktionenkörpers, Arch. Math. 33 (1979), 357–360.
[529] H. Stichtenoth , Algebraic Function Fields and Codes, Springer, 1993.
[530] H. Stichtenoth and C. Xing , On the structure of the divisor class group of a class of curves over finite fields, Arch. Math. 65 (1995), 141–150.
[531] D. R. Stinson , Some baby-step–giant-step algorithms for the low Hamming weight discrete logarithm problem, Math. Comp. 71(237) (2001), 379–391.
[532] D. R. Stinson , Cryptography: Theory and Practice, 3rd edn, Chapman & Hall/CRC, 2005.
[533] A. Storjohann and G. Labahn , Asymptotically fast computation of Hermite normal forms of integer matrices, ISSAC 1996, ACM Press, 1996, pp. 259–266.
[534] E. G. Straus , Addition chains of vectors, American Mathematical Monthly 71(7) (1964), 806–808.
[535] A. H. Suk , Cryptanalysis of RSA with lattice attacks, MSc thesis, University of Illinois at Urbana-Champaign, 2003.
[536] A. V. Sutherland , Order computations in generic groups, Ph.D.thesis, MIT, 2007.
[537] A. V. Sutherland , Structure computation and discrete logarithms in finite abelian p-groups, Math. Comp. 80(273) (2011), 477–500.
[538] T. Takagi , Fast RSA-type cryptosystem modulo pkq. In CRYPTO 1998 ( H. Krawczyk , ed.), LNCS, vol. 1462, Springer, 1998, pp. 318–326.
[539] J. Talbot and D. Welsh , Complexity and Cryptography: An Introduction, Cambridge University Press, 2006.
[540] J. Tate , Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134– 144.
[541] E. Teske , A space efficient algorithm for group structure computation, Math. Comp. 67(224) (1998), 1637–1663.
[542] E. Teske , Speeding up Pollard's rhomethod for computing discrete logarithms. In ANTS III ( J. P. Buhler , ed.), LNCS, vol. 1423, Springer, 1998, pp. 541–554.
[543] E. Teske , On random walks for Pollard's rho method, Math. Comp. 70(234) (2001), 809–825.
[544] E. Teske , Computing discrete logarithms with the parallelized kangaroo method, Discrete Appl. Math. 130 (2003), 61–82.
[545] N. Thériault , Index calculus attack for hyperelliptic curves of small genus. In ASIACRYPT 2003 ( C.-S. zaih , ed.), LNCS, vol. 2894, Springer, 2003, pp. 75–92.
[546] E. Thomé , Algorithmes de calcul de logarithmes discrets dans les corps finis, Ph.D. thesis, L'École Polytechnique, 2003.
[547] W. Trappe and L. C. Washington , Introduction to Cryptography with Coding Theory, 2nd edn, Pearson, 2005.
[548] M. A. Tsfasman , Group of points of an elliptic curve over a finite field, Theory of Numbers and Its Applications, Tbilisi, 1985, pp. 286–287.
[549] J. W. M. Turk , Fast arithmetic operations on numbers and polynomials, Computational Methods in Number Theory, Part 1, Mathematical Centre Tracts 154, Amsterdam, 1984.
[550] B. Vallée , Une approche géométrique de la réduction de réseaux en petite dimension, Ph.D. thesis, Université de Caen, 1986.
[551] B. Vallée , Gauss' algorithm revisited, J. Algorithms 12(4) (1991), 556–572.
[552] S. Vaudenay , Hidden collisions on DSS. In CRYPTO 1996 ( N. Koblitz , ed.), LNCS, vol. 1109, Springer, 1996, pp. 83–88.
[553] S. Vaudenay , A Classical Introduction to Cryptography, Springer, 2006.
[554] F. Vercauteren , Optimal pairings, IEEE Trans. Inf. Theory 56(1) (2010), 455–461.
[555] E. R. Verheul , Certificates of recoverability with scale recovery agent security. In PKC 2000 ( H. Imai and Y. Zheng , eds.), LNCS, vol. 1751, Springer, 2000, pp. 258–275.
[556] E. R. Verheul , Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, J. Crypt. 17(4) (2004), 277–296.
[557] E. R. Verheul and H. C. A. van Tilborg , Cryptanalysis of ‘less short’ RSA secret exponents, Applicable Algebra in Engineering, Communication and Computing 8(5) (1997), 425–435.
[558] M.F. Vignéras , Arithmétique des algébres de quaternions, LNM, vol. 800, Springer, 1980.
[559] J. F. Voloch , A note on elliptic curves over finite fields, Bulletin de la Société Mathématique de France 116(4) (1988), 455–458.
[560] L. C. Washington , Elliptic Curves: Number Theory and Cryptography, 2nd edn, CRC Press, 2008.
[561] E. Waterhouse , Abelian varieties over finite fields, Ann. Sci. Ecole Norm. Sup. 2 (1969), 521–560.
[562] D. H. Wiedemann , Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory 32 (1986), 54–62.
[563] M. J. Wiener , Bounds on Birthday Attack Times, Cryptology ePrint Archive, Report 2005/318.
[564] M. J. Wiener , Cryptanalysis of short RSA secret exponents, IEEE Trans. Inf. Theory 36(3) (1990), 553–558.
[565] M. J. Wiener and R. J. Zuccherato , Faster attacks on elliptic curve cryptosystems. In SAC 1998 ( S. E. Tavares and H. Meijer , eds.), LNCS, vol. 1556, Springer, 1998, pp. 190–200.
[566] H. C. Williams , A modification of the RSA public key encryption procedure, IEEE Trans. Inf. Theory 26(6) (1980), 726–729.
[567] H. C. Williams , A p + 1 method of factoring, Math. Comp. 39(159) (1982), 225–234.
[568] D. J. Winter , The Structure of Fields, GTM 16, Springer, 1974.
[569] M. Woodroofe , Probability with Applications, McGraw-Hill, 1975.
[570] S.-M. Yen and C.-S. Laih , Improved digital signature suitable for batch verification, IEEE Trans. Computers 44(7) (1995), 957–959.
[571] S.-M. Yen , C.-S. Laih , and A. K. Lenstra , Multi-exponentiation, IEEE Proceedings Computers and Digital Techniques 141(6) (1994), 325–326.
[572] N. Yui , On the jacobian varieties of hyperelliptic curves over fields of characteristic p > 2, J. Algebra 52 (1978), 378–410.
[573] O. Zariski and P. Samuel , Commutative Algebra (Vol. I and II), Van Nostrand, Princeton University Press, 1960.
[574] N. Zierler , A conversion algorithm for logarithms on G F(2n), J. Pure Appl. Algebra 4 (1974), 353–356.
[575] P. Zimmermann , Private communication, 10 March 2009.