algorithmic number theory and cryptography

Algorithmic number theory is also known as computational number theory. It uses computational methods to study problems in number theory, and it includes the design and analysis of algorithms for number-theoretic problems.

An important application is cryptography for secure communication in the presence of adversaries.

selected papers

Ency Crypto

Igor Shparlinski

Computational Diffie-Hellman Problem

In Encyclopedia of Cryptography, Security and Privacy, 2025

DOI Bib

@incollection{Shparlinski25,
  author = {Shparlinski, Igor},
  title = {Computational Diffie-Hellman Problem},
  booktitle = {Encyclopedia of Cryptography, Security and Privacy},
  pages = {403--407},
  year = {2025},
  url = {https://doi.org/10.1007/978-3-030-71522-9_882},
  doi = {10.1007/978-3-030-71522-9_882}
}

CRYPTO

Muhammed F. Esgin, Ron Steinfeld, Dongxi Liu, and Sushmita Ruj

Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs

In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V, 2023

DOI preprint Bib

@inproceedings{EsginSLR22,
  author = {Esgin, Muhammed F. and Steinfeld, Ron and Liu, Dongxi and Ruj, Sushmita},
  editor = {Handschuh, Helena and Lysyanskaya, Anna},
  title = {Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to
                    Rounding and VRFs},
  booktitle = {Advances in Cryptology - {CRYPTO} 2023 - 43rd Annual International
                    Cryptology Conference, {CRYPTO} 2023, Santa Barbara, CA, USA, August
                    20-24, 2023, Proceedings, Part {V}},
  series = {Lecture Notes in Computer Science},
  volume = {14085},
  pages = {484--517},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-38554-4\_16},
  doi = {10.1007/978-3-031-38554-4\_16}
}

Ann. of Math.

David Harvey, and Joris Hoeven

Integer multiplication in time O(n \log n)

Annals of Mathematics, 2021

DOI preprint Bib

@article{HarveyH21,
  author = {Harvey, David and van der Hoeven, Joris},
  title = {Integer multiplication in time $O(n \log n)$},
  journal = {Annals of Mathematics},
  publisher = {Department of Mathematics of Princeton University},
  volume = {193},
  number = {2},
  pages = {563 -- 617},
  year = {2021},
  doi = {10.4007/annals.2021.193.2.4}
}

STOC

Igor E. Shparlinski

Sparse polynomial approximation in finite fields

In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, 2001

DOI Bib

@inproceedings{Shparlinski01,
  author = {Shparlinski, Igor E.},
  editor = {Vitter, Jeffrey Scott and Spirakis, Paul G. and Yannakakis, Mihalis},
  title = {Sparse polynomial approximation in finite fields},
  booktitle = {Proceedings on 33rd Annual {ACM} Symposium on Theory of Computing,
                    July 6-8, 2001, Heraklion, Crete, Greece},
  pages = {209--215},
  publisher = {{ACM}},
  year = {2001},
  url = {https://doi.org/10.1145/380752.380803},
  doi = {10.1145/380752.380803}
}