Abstract
There are many cryptosystems that are based on modular arithmetic (also known in some contexts as residue arithmetic); examples of such systems are given in the next chapter. This chapter covers some of the fundamentals of modular arithmetic and will be a brief review or introduction, according to the reader’s background. The first section of the chapter gives some basic definitions and mathematical properties. The second section is on the basic arithmetic operations, squares, and square roots. The third section is on the Chinese Remainder Theorem, a particularly important result in the area. And the last section is on residue number systems, unconventional representations that can facilitate fast, carry-free arithmetic.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
See the corollary to Theorem 6.3, proof in the Appendix.
- 2.
Some texts give this definition with respect to only a prime modulus. Our purposes require this more general definition.
- 3.
One could just as well use the terms “square” and “nonsquare,” but standard terminology is what it is.
- 4.
Note the symmetry in both tables of the example, which symmetry indicates that it suffices to consider just half of the residues.
- 5.
A proof of the split is given in the Appendix (Corollary A.4).
References
A. R. Omondi and B. Premkumar. 2007. Residue Number Systems: Theory and Implementation. Imperial College Press, London, UK.
P. V. A. Mohan. 2016. Residue Number Systems: Theory and Applications. Birkhauser, Basel, Switzerland.
D. M. Burton. 2010. Elementary Number Theory. McGraw-Hill Education, New York, USA.
G.H. Hardy and E.M. Wright. 2008. An Introduction to the Theory of Numbers. Oxford University Press, Oxford, UK.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
R. Omondi, A. (2020). Mathematical Fundamentals I: Number Theory. In: Cryptography Arithmetic. Advances in Information Security, vol 77. Springer, Cham. https://doi.org/10.1007/978-3-030-34142-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-34142-8_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34141-1
Online ISBN: 978-3-030-34142-8
eBook Packages: Computer ScienceComputer Science (R0)