中国矿业大学：《密码学》课程教学资源（PPT讲稿）认证协议（Authentication Protocol）Lecture 3 Number Theory Basics I

Number Theory Basics I Lecture 3

Number Theory Basics I Lecture 3

Numbers Integers Real Arithmetic Operations Addition and subtraction Multiplication and division Exponentiation and logarithm

Numbers • Integers • Real Arithmetic Operations • Addition and subtraction • Multiplication and division • Exponentiation and logarithm

The geometry of numbers Infinity

The Geometry of Numbers • Infinity 0

Mapping line onto circle Stereographic Projection one-to-one mapping

Mapping Line onto Circle • Stereographic Projection – one-to-one mapping x P(x)

Mapping line to circle Wrap around Modular arithmetic

Mapping Line to Circle • Wrap around – Modular arithmetic

Modular arithmetic a= b mod m iff(a-b)=km+ b for some m the equivalence class under mod m m C anonical for rm:Zm={0,12,,m-},we use the positive remainder as the standard representation

Modular Arithmetic • a = b mod m iff (a-b) = km + b for some m • Zm the equivalence class under mod m • [a]m • Canonical form: Zm = {0,1,2,…,m-1}, we use the positive remainder as the standard representation

Modular arithmetic 1=m-1 mod m Zn={0,1,2,34,5,6} (Zm+, x,0, 1)defines a ring +,× are closed associative and commutative Operation x distributes over 0 is the identity for and 1 for x Additive inverse and multiplicative inverse

Modular Arithmetic • -1 = m -1 mod m • Z7 = {0,1,2,3,4,5,6} • (Zm, +, ,0, 1) defines a ring – +,  are closed – associative and commutative – Operation  distributes over + – 0 is the identity for + and 1 for  – Additive inverse and multiplicative inverse

Multiplicative Inverses and Congruence equations When does a number has a multiplicative inverse? When does a congruence equation ax= b mod m has a solution has a unique solution 5X=8mod12=>x=4 3x=8 mod 12==> no solution 3x=9mod12=>xin{3,7,11}

Multiplicative Inverses and Congruence Equations • When does a number has a multiplicative inverse? • When does a congruence equation ax = b mod m – has a solution – has a unique solution • 5x = 8 mod 12 ==> x = 4 • 3x = 8 mod 12 ==> no solution • 3x = 9 mod 12 ==> x in {3,7,11}

Greatest Common Divisor(GCD) gcd(12,15)=3 gcd(12, 25 )=1, relative prime Theorem: ax= b mod m has a unique solution for every number b in Zm iff gcd(a, m)=I

Greatest Common Divisor (GCD) • gcd(12,15) = 3 • gcd(12,25) = 1, relative prime • Theorem: ax = b mod m has a unique solution for every number b in Zm iff gcd(a,m) = 1

Proof Consider the map II(x) aX Suppose x*y and ax=ay mod m then a(x-y)=0 mod m. So if gcd(a, m)=1 then x=y mod m. Therefore, it is a bijection. Therefore, every ax=b mod m as a unique solution In particular ax=I mod m has a solution which implies that a has an inverse

Proof • Consider the map: Pa (x) = ax. Suppose x  y and ax = ay mod m then a(x-y) = 0 mod m. So if gcd(a,m) =1, then x = y mod m. Therefore, it is a bijection. Therefore, every ax = b mod m has a unique solution • In particular ax = 1 mod m has a solution, which implies that a has an inverse