Week 6: Introduction to Number Theory

In this unit we introduce some elementary concepts from number theory that are used in many modern ciphers and related security systems. We start with some basic definitions before discussing the division algorithm which lies at the heart of the important Euclidean algorithm. The discussion then moves on to look at prime numbers and describes how prime factorisation can be applied to express any integer, greater than one, as a product of primes. The concept of a greatest common divisor (GCD) of two positive integers is described and we discuss how prime factorisation can be used to calculate this quantity when the numbers are relatively small. We then introduce the Euclidean algorithm which provides an efficient method for calculating the GCD of two integers regardless of their size.

Added By:	Justin Bradley
Date Added:	21 Jun 2017 08:14
Name:
Viewing permissions:	World
URL:	http://hub.edshare.ac.uk/id/eprint/4684
Downloads & Views

Actions (login required)

View Item