MATH 4383 - Number Theory and Cryptography - University of Houston

# MATH 4383 - Number Theory and Cryptography

(EFFECTIVE for 2018-2019 Catalog)

***This is a course guideline.  Students should contact instructor for the updated information on current course syllabus, textbooks, and course content***

Prerequisites: MATH 3330 or MATH 3336.

Catalog Course Description: Divisibility theory, primes and their distribution, theory of congruences and application in security, integer representations, Fermat's Little Theorem and Euler's Theorem, primitive roots, quadratic reciprocity, and introduction to cryptography

Textbook: Instructor's lecture notes

Course Content:

Number theory, once considered the purest of subjects, has become an essential tool in providing computer and Internet security. This course will cover the topics in the standard one semester introduction to number theory, as well its applications in computer science and cryptography. It includes:  Divisibility theory, primes and their distribution, theory of congruences and its application in security, Integer representations (binary and base expansions, base conversion algorithm), Fermat's Little Theorem and Euler's Theorem, primitive roots, quadratic reciprocity, and introduction to cryptography (classical cryptography, public key cryptography, RSA cryptosystem, cryptographic protocols).

Syllabus:

Chapter 1: Preliminaries

1.1 The number system and the Well-Ordering Principle
1.2 Mathematical Induction

Chapter 2:  Divisibility and Factorization

2.1 Divisibility, Greatest Common Divisors, Euclidean Algorithm
2.2 Least Common Multiple
2.3 Representations of integers (Decimal Representation and Binary Representation of integers)

Chapter 3: Solving Linear Diophantine Equations

Chapter 4: Primes

4.1 Prime Numbers
4.2 Unique Prime Factorization
4.3 Test of Primality by Trial Division

Chapter 5: The Theory of Congruences

5.1 The concept of congruences
5.2 Congruence Classes
5.3 Applications of Congruences: Check digits

Chapter 6: Solving Linear Congruences

6.1 Solving (single) linear congruence
6.2 Solving system of linear congruences, the Chinese Remainder Theorem

Chapter 7: Fermat's Theorem and Euler's Generalization

7.1 Fermat's Little Theorem
7.2 The general case: Euler's theorem

Chapter 8: Primitive Roots

8.1 The multiplicative order
8.2 Promitive Roots (mod n)
8.3 The modulus n which does not have primitive roots
8.4 The Existence Theorems
8.5 Applications: The use of primitive roots

9.1 Euler's Criterion
9.2 The Legendre Symbol and its properties
9.3 Examples of computing the Legendre symbol
9.4 Jacobi Symbol
9.5 Quadratic Residues and Primitive Roots

Chapter 10: Cryptography

10.1 Introduction
10.2 Symmetric-key cryptography
10.3 Assymetric Key or public key cryptography

CSD Accommodations:

Accommodation Forms: Students seeking academic adjustments/auxiliary aids must, in a timely manner (usually at the beginning of the semester), provide their instructor with a current Student Accommodation Form (SAF) (paper copy or online version, as appropriate) from the CSD office before an approved accommodation can be implemented.

Details of this policy, and the corresponding responsibilities of the student are outlined in The Student Academic Adjustments/Auxiliary Aids Policy (01.D.09) document under [STEP 4: Student Submission (5.4.1 & 5.4.2), Page 6]. For more information please visit the Center for Students with Disabilities Student Resources page.

Additionally, if a student is requesting a (CSD approved) testing accommodation, then the student will also complete a Request for Individualized Testing Accommodations (RITA) paper form to arrange for tests to be administered at the CSD office. CSD suggests that the student meet with their instructor during office hours and/or make an appointment to complete the RITA form to ensure confidentiality.

*Note: RITA forms must be completed at least 48 hours in advance of the original test date. Please consult your counselor ahead of time to ensure that your tests are scheduled in a timely manner. Please keep in mind that if you run over the agreed upon time limit for your exam, you will be penalized in proportion to the amount of extra time taken.

UH CAPS

Counseling and Psychological Services (CAPS) can help students who are having difficulties managing stress, adjusting to college, or feeling sad and hopeless. You can reach (CAPS) by calling 713-743-5454 during and after business hours for routine appointments or if you or someone you know is in crisis. No appointment is necessary for the "Let's Talk" program, a drop-in consultation service at convenient locations and hours around campus.