[go: up one dir, main page]
Scribd
Upload
17 views51 pages

Basic Number Theory and Algebra

The document outlines a lecture on basic number theory and algebra. It discusses how numbers are represented in cryptographic systems and how mathematical operations are used to encrypt and decrypt messages. To build, analyze, and attack these cryptosystems, tools from number theory are required, especially the theory of congruences. The lecture covers topics like divisibility, primes, greatest common divisors, congruences, the Chinese Remainder Theorem, Fermat's Little Theorem, Euler's Theorem, primitive roots, inverting matrices modulo n, square roots modulo n, and algebraic structures like groups, rings, and fields.

Uploaded by

Marielle Landicho
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views51 pages

Basic Number Theory and Algebra

The document outlines a lecture on basic number theory and algebra. It discusses how numbers are represented in cryptographic systems and how mathematical operations are used to encrypt and decrypt messages. To build, analyze, and attack these cryptosystems, tools from number theory are required, especially the theory of congruences. The lecture covers topics like divisibility, primes, greatest common divisors, congruences, the Chinese Remainder Theorem, Fermat's Little Theorem, Euler's Theorem, primitive roots, inverting matrices modulo n, square roots modulo n, and algebraic structures like groups, rings, and fields.

Uploaded by

Marielle Landicho
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 51

Lecture 2

Basic Number Theory and Algebra


In modern cryptographic systems,the messages
are represented by numerical values prior to
being encrypted and transmitted. The
encryption processes are mathematical
operations that turn the input numerical value
into output numerical values. Building,
analyzing, and attacking these cryptosystem
requires mathematical tools. The most
important of these is number theory, especially
the theory of congruences.
Outline
❑ Basic Notions
❑ Solving ax+by=d=gcd(a,b)
❑ Congruence
❑ The Chinese Remainder Theorem
❑ Fermat’s Little Theorem and Euler’s Theorem
❑ Primitive Root
❑ Inverting Matrices Mod n
❑ Square Roots Mod n
❑ Groups Rings Fields
1 Basic Notions
1.1 Divisibility
1.1 Divisibility (Continued)
1.1 Divisibility (Continued)
1.2 Prime

The primes less than 200:


2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
59 61 67 71 73 79 83 89 97 101 103 107 109
113 127 131 137 139 149 151 157 163 167
173 179 181 191 193 197 199
1.2 Prime (Continued)
1.2 Prime
(Continued)
1.2 Prime
(Continued)
1.3 Greatest Common Divisor
1.3 Greatest Common Divisor (Continued)
1.3 Greatest Common Divisor (Continued)
1.3 Greatest Common Divisor (Continued)
1.3 Greatest Common Divisor (Continued)
2 Solving ax+by=d=gcd(a,b)
3 Congruences
3.1 Addition, Subtraction, Multiplication
3.1 Addition, Subtraction, Multiplication
(Continued)
3.2 Division
3.2 Division (Continued)
3.2 Division (Continued)
3.3 Division (Continued)
3.2 Division (Continued)
4 The Chinese Remainder Theorem
4 The Chinese Remainder Theorem (Continued)
4 The Chinese Remainder Theorem (Continued)
4 The Chinese Remainder Theorem (Continued)
4 The Chinese Remainder Theorem (Continued)
5 Fermat’s Little Theorem and Euler’s
Theorem
5 Fermat’s Little Theorem and Euler’s Theorem
(Continued)
5 Fermat’s Little Theorem and Euler’s Theorem
(Continued)
5 Fermat’s Little Theorem and Euler’s Theorem
(Continued)
5 Fermat’s Little Theorem and Euler’s Theorem
(Continued)
5 Fermat’s Little Theorem and Euler’s Theorem
(Continued)
6 Primitive Root
6 Primitive Root (Continued)
7 Inverting Matrices Mod n
7 Inverting Matrices Mod n (Continued)
7 Inverting Matrices Mod n (Continued)
8 Square Roots Mod n
8 Square Roots Mod n (Continued)
8 Square Roots Mod n (Continued)
8 Square Roots Mod n (Continued)
9 Groups, Rings, Fields
9.1 Groups
9.1 Groups (Continued)
9.2 Rings
9.2 Rings (Continued)
9.3 Fields
Thank you!

You might also like