An analytic approach to smooth polynomials over finite fields

1. Abramowitz, M., and Stegun, I.Handbook of mathematical functions. Dover, New York, 1970.

   Google Scholar 

2. Bach, E., and Peralta, R. Asymptotic semismoothness probabilities. Math. Comp. 65 (1996), 1701–1715.

   Article  MATH  MathSciNet  Google Scholar 

3. Blum, M., and Micali, S. How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13 (1984), 850–864.

   Article  MATH  MathSciNet  Google Scholar 

4. Car, M. Théorèmes de densité dans F_q[x]. Acta Arith. 48 (1987), 145–165.

   MATH  MathSciNet  Google Scholar 

5. de Bruijn, N. On the number of positive integers ≤ x and free of prime factors >y. Indag. Math. 13 (1951), 2–12.

   Google Scholar 

6. Dickman, K. On the frequency of numbers containing prime factors of a certain relative magnitude. Ark. Mat. Astr.Fys. 22 (1930), 1–14.

   Google Scholar 

7. Diffie, W., and Hellman, M. New directions in cryptography. IEEE Trans. Inform. Theory 22 (1976), 644–654.

   Article  MATH  MathSciNet  Google Scholar 

8. ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory 31 (1985), 469–472.

   Article  MATH  MathSciNet  Google Scholar 

9. Flajolet P., Gordon, X., and Panario, D. The complete analysis of a polynomial factorization algorithm over finite fields. Submitted March 1998. [Extended abstract in Proc. 23rd ICALP Symp., Lecture Notes in Computer Science, vol. 1099, p. 232–243, 1996.] Full version in technical report 3370, INRIA, March 1998.

   Google Scholar 

10. Gao, S., von zur Gathen, J., and Panario, D. Gauss periods: orders and cryptographical applications. Math. Comp. 67 (1998), 343–352.

    Article  MATH  MathSciNet  Google Scholar 

11. Gourdon, X. Combinatoire, algorithmique et géométrie des polynÔmes. Thèse, école Polytechnique, 1996.

    Google Scholar 

12. Hildebrand, A., and Tenenbaum, G. Integers without large prime factors. J. Théorie des Nombres de Bordeaux 5 (1993), 411–484.

    MATH  MathSciNet  Google Scholar 

13. Lovorn, R. Rigourous, subexponential algorithms for discrete logarithm algorithms in F _p 2. PhD thesis, University of Georgia, 1992.

    Google Scholar 

14. Lovorn Bender, R., and Pomerance, C. Rigourous discrete logarithm computations in finite fields via smooth polynomials. In Computational Perspectives on Number Theory Proc. of a Conference in Honor of A.O.L. Atkin (Providence, 1998), vol. 7 of AMS/International Press Studies in Advanced Mathematics.

    Google Scholar 

15. Odlyzko, A. Discrete logarithms and their cryptographic significance. In Advances in Cryptology, Proceedings of Eurocrypt 1984 (1985), vol. 209 of Lecture Notes in Computer Science, Springer-Verlag, pp. 224–314.

    Google Scholar 

16. Odlyzko, A. Discrete logarithms and smooth polynomials. In Finite fields: theory, applications and algorithms, G. Mullen and P. J.-S. Shiue, Eds. Contemporary Mathematics 168, Amer. Math. Soc., 1994, pp. 269–278.

    Google Scholar 

17. Soundararajan, K. Asymptotic formulae for the counting function of smooth polynomials. To appear in J. London Math. Soc.

    Google Scholar 

18. Tenenbaum, G. Introduction to analytic and probabilistic number theory. Cambridge University Press, 1995.

    Google Scholar 

Download references