Help | Advanced Search
Number Theory
Authors and titles for recent submissions.
- Mon, 3 Jun 2024
- Fri, 31 May 2024
- Thu, 30 May 2024
- Wed, 29 May 2024
- Tue, 28 May 2024
Mon, 3 Jun 2024 (showing 8 of 8 entries )
Fri, 31 may 2024 (showing 12 of 12 entries ), thu, 30 may 2024 (showing first 5 of 11 entries ).
A Survey of Number Theory and Cryptography
Cite this chapter.
- Neal Koblitz 2
115 Accesses
2 Citations
Our purpose is to give an overview of the applications of number theory to public-key cryptography. We conclude by describing some tantalizing unsolved problems of number theory that turn out to have a bearing on the security of certain cryptosystems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
- Available as PDF
- Read on any device
- Instant download
- Own it forever
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Computational Number Theory and Cryptography
Number Theory
Essential Number Theory and Discrete Math
L.M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proc. 20th IEEE Symp. Foundations of Computer Science (1979), 55–60.
Google Scholar
L.M. Adleman and DeMarrais, J., A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 61 (1993), 1–15.
Article MathSciNet MATH Google Scholar
L.M. Adleman and Huang, M.-D., Primality Testing and Abelian Varieties over Finite Fields, Lect. Notes Math . 1512 , Springer-Verlag (1992).
Book MATH Google Scholar
L.M. Adleman, Pomerance, C. and Rumely, R.S., On distinguishing prime numbers from composite numbers, Annals Math . 117 (1983), 173–206.
G.B. Agnew, Mullin, R.C., Onyszchuk, I.M. and Vanstone, S.A., An implementation for a fast public-key cryptosystem, J. Cryptology 3 (1991), 63–79.
G.B. Agnew, Mullin, R.C. and Vanstone, S.A., An implementation of elliptic curve cryptosys-tems over F 2 155, IEEE Journal on Selected Areas in Communications 11 (1993), 804–813.
Article Google Scholar
W.R. Alford, Granville, A. and Pomerance, C, There are infinitely many Carmichael numbers, Annals Math . 139 (1994), 703–722.
A.O.L. Atkin, The number of points on, an elliptic curve modulo a prime, unpublished manuscript (1991).
A.O.L. Atkin and Morain, F., Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68.
E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms , MIT Press (1985).
MATH Google Scholar
E. Bach, Shallit, J., Algorithmic Number Theory , vol. 1, MIT Press (1996).
R. Balasubramanian and Koblitz, N., The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm, J. Cryptology 10 (1997).
I.F. Blake and Fuji-Hara, R., Mullin, R.C. and Vanstone, S.A., Computing logarithms in fields of characteristic two, SIAM J. Algebraic and Discrete Methods 5 (1984), 276–285.
D. Boneh and Upton, R., Algorithms for black-box fields and their applications to cryptography, Advances in Cryptology — Crypto ’96 , Springer-Verlag (1996), 283–297.
J. Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013.
J. Brillhart, Lehmer, D.H., Selfridge, J.L. Tuckerman, B. and Wagstaff, S.S. Jr., Factorizations of b n ± 1, b = 2, 3, 5, 6, 7,10, 11,12 Up to High Powers, Amer. Math. Soc . (1988).
J. Brillhart and Morrison, M., A method of factoring and the factorization of F 7 , Math. Comp. 29 (1975), 183–205.
MathSciNet MATH Google Scholar
J. Buchmann and Williams, H.C., A key exchange system based on imaginary quadratic fields, J. Cryptology 1 (1988), 107–118.
J. Buchmann and Williams, H.C., A key exchange system based on real quadratic fields, Advances in Cryptology — Crypto ’89 , Springer-Verlag (1990), 335–343.
E.R. Canfield, Paul Erdös and Pomerance, C, On a problem of Oppenheim concerning “Factorisatio Numerorum,” J. Number Theory 17 (1983), 1–28.
L. Charlap, Coley, R. and Robbins, D., Enumeration of rational points on elliptic curves over finite fields, unpublished manuscript (1991).
H. Cohen, A Course in Computational Algebraic Number Theory , Springer-Verlag (1993).
H. Cohen and Lenstra, A.K., Implementation of a new primality test, Math. Comp. 48 (1987), 103–121.
H. Cohen and Lenstra, H.W Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297–330.
D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Information Theory 30 (1984), 587–594.
D. Coppersmith, Odlyzko, A.M. and Schrœppel, R., Discrete logarithms in GF(p), Algorithmica 1 (1986), 1–15.
Article MATH Google Scholar
T. Denny, Shirokauer, O. and Weber, D., Discrete logarithms: the effectiveness of the index calculus method, in Henri Cohen, ed., Algorithmic Number Theory, Proc. Second Intern. Symp., ANTS-II , Springer-Verlag (1996), 337–361.
W. Diffie and Hellman, M., New directions in cryptography, IEEE Trans. Information Theory 22 (1976), 644–654.
J.D. Dixon, Factorization and primality testing, Amer. Math. Monthly 91 (1984), 333–352.
T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Information Theory 31 (1985), 469–472.
T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over G F ( p 2 ), IEEE Trans. Information Theory 31 (1985), 473–481.
S. Goldwasser and Kilian, J., Almost all primes can be quickly certified, Proc. 18th ACM Symp. Theory of Computing (1986), 316–329.
S. Goldwasser and Micali, S. Probabilistic encryption and how to play mental poker keeping secret all partial information, Proc. 14th ACM Symp. Theory of Computing (1982), 365–377.
S. Goldwasser and Micali, S., Probabilistic encryption, J. Comput. System Sci. 28 (1984), 270–299.
D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM J. Discrete Math. 6 (1993), 124–138.
D. Gordon, Discrete logarithms in GF(p n ) using the number field sieve, preprint (1995).
D. Gordon and McCurley, K., Massively parallel computation of discrete logarithms, Advances in Cryptology — Crypto ’92 , Springer-Verlag (1993), 312–323.
A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc. 39 (1992), 696–700.
R. Gupta and Murty, M.R., Primitive points on elliptic curves, Compositio Math . 58 (1986), 13–44.
R.K. Guy, Unsolved Problems in Number Theory , Springer-Verlag (1981).
M.E. Hellman and Pohlig, S., An improved algorithm for computing logarithms over GF ( p ) and its cryptographic significance, IEEE Trans. Information Theory 24 (1978), 106–110.
M.E. Hellman and Reyneri, J.M., Fast computation of discrete logarithms in GF(q), Advances in Cryptology — Crypto ’82 , Plenum Press (1983), 3–13.
D. Husemöller, Elliptic Curves , Springer-Verlag (1987).
K. Ireland and Rosen, M.I., A Classical Introduction to Modern Number Theory , 2nd ed., Springer-Verlag (1990).
D.E. Knuth, The Art of Computer Programming , vol. 2 , 2nd ed., Addison-Wesley (1981).
D.E. Knuth, The Art of Computer Programming , vol. 3 , Addison-Wesley (1973).
N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203–209.
N. Koblitz, Primality of the number of points on an elliptic curve over a finite field, Pacific J.Math. 131 (1988), 157–165.
N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139–150.
N. Koblitz, Constructing elliptic curve cryptosystems in characteristic 2, Advances in Cryptology — Crypto ’90 , Springer-Verlag (1991), 156–167.
N. Koblitz, Elliptic curve implementation of zero-knowledge blobs, J. Cryptology 4 (1991), 207–213.
N. Koblitz, CM-curves with good cryptographic properties, Advances in Cryptology — Crypto ’91 , Springer-Verlag (1992), 279–287.
N. Koblitz, Introduction to Elliptic Curves and Modular Forms , 2nd ed., Springer-Verlag (1993).
N. Koblitz, A Course in Number Theory and Cryptography , 2nd ed., Springer-Verlag (1994).
N. Koblitz, Algebraic Aspects of Cryptography , Springer-Verlag (1998).
M. Kraitchik, Théorie des nombres , vol. 1, Gauthier-Villars (1922).
B. LaMacchia and Odlyzko, A.M., Computation of discrete logarithms in prime fields, Designs, Codes and Cryptography 1 (1991), 47–62.
F. Lehmann, Maurer, M. Müller, V. and Shoup, V, Counting the number of points on elliptic curves over finite fields of characteristic greater than three, Algorithmic Number Theory, Lect. Notes Comp. Sci. 877 (1994), Springer-Verlag, 60–70.
A.K. Lenstra, Primality testing, Cryptology and Computational Number Theory, Proc. Symp. Appl. Math. 42 (1990), 13–25.
A.K. Lenstra and Lenstra, H.W. Jr., Algorithms in number theory, Handbook of Theoretical Computer Science , Elsevier (1990), 673–715.
A.K. Lenstra and Lenstra, H.W. Jr., The Development of the Number Field Sieve , Springer-Verlag (1993).
H.W. Lenstra, Jr., Factoring integers with elliptic curves, Annals Math . 126 (1987), 649–673.
H.W. Lenstra, Jr., Pila, J. and Pomerance, C, A hyperelliptic smoothness test. I, Philos. Trans. Roy. Soc. London 345 (1993), 397–408.
H.W. Lenstra, Jr., and Pomerance, C, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483–516.
R. Lercier and Morain, F., Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in Cryptology — Eurocrypt y 95 , Springer-Verlag (1995), 79–94.
R. Lidl and Niederreiter, H., Introduction to Finite Fields and Their Applications , Cambridge Univ. Press (1986).
B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33–186.
K. McCurley, The discrete logarithm problem, Cryptology and Computational Number Theory, Proc. Symp. Appl. Math. 42 (1990), 49–74.
K. McCurley, Odds and ends from cryptology and computational number theory, Cryptology and Computational Number Theory, Proc. Symp. Appl. Math. 42 (1990), 145–166.
A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Acad. Publ . (1993).
A. Menezes, Okamoto, T. and Vanstone, S.A., Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Information Theory 39 (1993), 1639–1646.
A. Menezes, van Oorschot, P. and Vanstone, S.A., Handbook of Applied Cryptography , CRC Press (1996).
A. Menezes and Vanstone, S.A., Elliptic curve cryptosystems and their implementation, J. Cryptology 6 (1993), 209–224.
A. Menezes, Vanstone, S.A. and Zuccherato, R.J., Counting points on elliptic curves over F 2 m, Math. Comp . 60 (1993), 407–420.
G.L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), 300–317.
V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology — Crypto ’85 , Springer-Verlag (1986), 417–426.
Book Google Scholar
PL. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243–264.
F. Morain, Implementation of the Goldwasser-Kilian-Atkin primality testing algorithm, INRIA report 911 (1988).
A.M. Odlyzko, Discrete logarithms and their cryptographic significance, Advances in Cryptology — Eurocrypt ’84 , Springer-Verlag (1985), 224–314.
A.M. Odlyzko, The future of integer factorization, Crypto Bytes , 1 (No. 2) (1995), 5–12.
MathSciNet Google Scholar
H.C. Pocklington, The determination of the prime and composite nature of large numbers by Fermat’s theorem, Proc. Cambridge Philos. Soc. 18 (1914–1916), 29–30.
J. Pollard, Monte Carlo methods for index computation mod p, Math. Comp . 32 (1978), 918–924.
C. Pomerance, Recent developments in primality testing, Math. Intelligencer 3 (1981), 97–105.
C. Pomerance, Analysis and comparison of some integer factoring algorithms, in H. W. Lenstra, Jr. and R. Tijdeman, ed., Computational Methods in Number Theory, Math. Centrum, Amsterdam , 154 (1982), 89–139.
C. Pomerance, The quadratic sieve factoring algorithm, Advances in Cryptology — Eurocrypt ’84 , Springer-Verlag (1985), 169–182.
C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity (1987), 119–143.
C. Pomerance, Factoring, Cryptology and Computational Number Theory, Proc. Symp. Appl Math. 42 (1990), 27–47.
C. Pomerance, Selfridge, J.L. and Wagstaff, S.S. Jr., The pseudoprimes to 25 – 10 9 , Math. Comp. 35(1980), 1003–1026.
G. Purdy, A high-security log-in procedure, Comm. of the ACM 17 (1974), 442–445.
M.O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128–138.
H. Riesel, Prime Numbers and Computer Methods for Factorization , Birkhäuser (1985).
R. Rivest, Cryptography, in Handbook of Theoretical Computer Science , vol. A, Elsevier (1990), 717–755.
R. Rivest, Shamir, A. and Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21 (1978), 120–126.
K. Rosen, Elementary Number Theory and Its Applications , 3rd ed., Addison-Wesley (1993).
R.S. Rumely, Recent advances in primality testing, Notices Amer. Math. Soc. 30 (1983), 475–477.
R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp . 44 (1985), 483–494.
E. Seah and Williams, H.C., Some primes of the form ( a n — 1)/( a — 1), Math. Comp. 33 (1979), 1337–1342.
D. Shanks, Five number-theoretic algorithms, Congressus Numerantium 7 (1972), 51–70.
D. Shanks, Solved and Unsolved Problems in Number Theory , 3rd ed., Chelsea (1985).
J. Silverman, The Arithmetic of Elliptic Curves , Springer-Verlag (1986).
P. van Oorschot, A comparison of practical public-key cryptosystems based on integer factorization and discrete logarithms, in G. Simmons, ed., Contemporary Cryptology: The Science of Information Integrity , IEEE Press (1992), 289–322.
E.P. Wigner, The unreasonable effectiveness of mathematics in the natural sciences, Comm. Pure Appl. Math. 13 (1960), 1–14.
M.V. Wilkes, Time-Sharing Computer Systems , Elsevier (1968).
Download references
Author information
Authors and affiliations.
Department of Mathematics, University of Washington, Box 354350, Seattle, WA, 98195, USA
Neal Koblitz
You can also search for this author in PubMed Google Scholar
Editor information
Editors and affiliations.
Centre for Advanced Study in Mathematics, Panjab University, Chandigarh, India
R. P. Bambah , V. C. Dumir & R. J. Hans-Gill , &
Rights and permissions
Reprints and permissions
Copyright information
© 2000 Hindustan Book Agency and (India) Indian National Science Academy
About this chapter
Koblitz, N. (2000). A Survey of Number Theory and Cryptography. In: Bambah, R.P., Dumir, V.C., Hans-Gill, R.J. (eds) Number Theory. Hindustan Book Agency, Gurgaon. https://doi.org/10.1007/978-93-86279-02-6_13
Download citation
DOI : https://doi.org/10.1007/978-93-86279-02-6_13
Publisher Name : Hindustan Book Agency, Gurgaon
Print ISBN : 978-81-85931-23-4
Online ISBN : 978-93-86279-02-6
eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
IMAGES
VIDEO
COMMENTS
Abstract and Figures. Number theory is a branch of mathematics that is primarily focused on the study of positive integers, or natural numbers, and their properties such as divisibility, prime ...
Overview. Research in Number Theory is a peer-reviewed journal focused on the mathematical disciplines of Number Theory and Arithmetic Geometry. Publishes high-quality original articles making significant contributions to these research areas. Actively seeks to publish seminal papers in emerging and interdisciplinary areas.
The journal now considers and welcomes also papers in Computational Number Theory. This journal has an Open Archive. All published items, including research articles, have unrestricted access and will remain permanently free to read and download 48 months after publication. All papers in the Archive are subject to Elsevier's user license.
These are notes for an 8-lecture rst course in number theory, taught in Oxford as a Part A short option course. The notes were comprehensively rewritten in 2017, but it was useful to have access to the earlier notes developed by Alan Lauder, Tim Browning, Andrew Cadwell, Roger Heath-Brown, Henri Johnston and Jennifer Balakrishnan.
These are notes for an 8-lecture rst course in number theory, taught in Oxford as a Part A short option course. The notes have been comprehensively rewritten in 2017, but it was useful to have access to the earlier notes developed by Alan Lauder, Tim Browning, Andrew Cadwell, Roger Heath-Brown, Henri Johnston and Jennifer Balakrishnan. Synopsis.
This paper mainly studies the development and applications of number theory, aiming ... which also provide new research methods for number theory. 1.2 The Subdivisions of Number Theory In terms of the field, number theory can be divided into many different subdivisions, of which elementary number theory, algebraic number theory, geometric ...
to mathematicians that topics in number theory attempt to unveil. Definition 2.3.If an integer phas no divisor other than 1 and itself, it is called a prime number. Otherwise, it is a composite number. Examples of prime numbers: 2, 3, 5, and 7; examples of composite numbers: 4, 6, 8, and 9.
Number Theory Revealed is a series of books intended to constitute a first introduction to number theory, giving a survey of the subject starting from the very beginning and proceeding up to some glimpses of contemporary research. The Introduction is a condensed version of the Masterclass, containing just what is needed for a first course in ...
Toshiki Matsusaka. Genki Shibukawa. Research 13 December 2023 Article: 3. 1. 2. …. 11. Next. Research in Number Theory is a peer-reviewed journal focused on the mathematical disciplines of Number Theory and Arithmetic Geometry.
number theory is the queen of mathematics (hence the title of [E.5.4]). If you don't yet know why that might be the case, you are in for a treat. Number theory was (and is still occasionally) called 'the higher arithmetic', and that is truly where it starts. Even a small child understands that there is
Comments: Comments are always welcome! Subjects: Number Theory (math.NT); Algebraic Geometry (math.AG) Total of 79 entries : 1-25 26-50 51-75 76-79. Showing up to 25 entries per page: fewer | more | all.
techniques used to construct ciphers. Overall, this paper will demonstrate that number theory is a crucial component of cryptography by allowing a coherent way of encrypting a message that is also challenging to decrypt. The discussion in this paper follows the set of notes [1] [2] [3] by Evan Dummit. 2. Number Theory Background 2.1. Basic ...
In fact, most of Ramanujan's research in number theory arose out of g-series and theta functions. Theta functions are the fundamen tal building blocks in the theory of elliptic functions, and Ramanujan independently developed his own theory of elliptic functions, which is quite unlike the classical theory.
Abstract. The research presents the discovery of the numerical relational system, as a communicative system, between what today it is called in mathematics types of numbers; from this perspective, the types of numbers are united to form the macrosystem, which is composed of Natural Numbers, Integers, Rational Numbers, and Real Numbers.
Number Theory Revealed is a series of books intended to constitute a first introduction to number theory, giving a survey of the subject starting from the very beginning and proceeding up to some glimpses of contemporary research. The Introduction is a condensed version of the Masterclass, containing just what is needed for a first course in number theory; but if you have even the slightest ...
An Introduction to Number Theory with Cryptography presents number theory along with many interesting applications, designed for an undergraduate-level course and gives instructors the option of integrating several other topics into their coverage. Number theory has a rich history. For many years it was one of the purest areas of pure mathematics, studied because of the intellectual ...
Mitrinovi József Sándor Borislav Crstici. Theory I. Babes-Bolyai University of Cluj, Cluj-Napoca, Romania. A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN-10 1-4020-3658-2 (e-book) ISBN-13 978-1-4020-3658-3 (e-book) Published by Springer, P.O. Box 17, 3300 AA Dordrecht, The Netherlands.
Prime Number: An integer > 1 is called a prime number (or) a prime in case there is no divisor ' ' of ' L' satisfying 1 < < L.If an integer > 1 is not a prime. It is called a composite number. Lattice Points: The co-ordinates of the points are an integer is called lattice points. Sum of Two Squares:
Abstract. Our purpose is to give an overview of the applications of number theory to public-key cryptography. We conclude by describing some tantalizing unsolved problems of number theory that turn out to have a bearing on the security of certain cryptosystems. Download to read the full chapter text.