GT CS 4803 - Very basic number theory
School name Georgia Tech
Pages 4

Unformatted text preview:

CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaVery basic number theory1Let Z = {. . . , "2, "1, 0, 1, 2, . . .} denote the set of integers. Let Z+ = {1, 2, . . .} denote the set of positive integers and N = {0, 1, 2, . . .} the set of non-negative integers.If a, N are integers with N > 0 then there are unique integers r, q such that a = Nq + r and 0 # r < N. We associate to any positive integer N the following two sets: ZN ={0, 1, . . . , N " 1}, ZN={ i!Z : 1#i#N"1 and gcd(i,N)=1 (relatively prime to N)} "2Groups•Def. Let G be a non-empty set and let ! denote a binary operation on G. We say that G is a group if it has the following properties: 1. Closure: For every a, b 󲰉 G it is the case that a ! b is also in G. 2. Associativity: For every a, b, c 󲰉 G it is the case that (a ! b) ! c = a ! (b ! c). 3. Identity: There exists an element 1 󲰉 G such that a ! 1 = 1 ! a = a for all a 󲰉 G. 4. Invertibility: For every a 󲰉 G there exists a unique b 󲰉 G such that a ! b = b ! a = 1. inverse, denoted a-13•Fact. Let N be a positive integer. Then ZN is a group under addition modulo N, and ZN is a group under multiplication modulo N. •In any group, we can define an exponentiation operation: if i = 0 then ai is defined to be 1, if i > 0 then ai = a ! a ! ! ! a (i times) if i < 0 then ai = a-1 ! a-1 ! ! ! a-1 (j=-i times)•For all a 󲰉 G and all i,j 󲰉 Z: •ai+j = ai ! aj •(ai)j = aij •a-i = (ai)-1= (a-1)i *4•The order of a group is its size•Fact. Let G be a group and let m = |G| be its order. Then am = 1 for all a 󲰉 G •Fact. Let G be a group and let m = |G| be its order. Then ai = ai mod m for all a 󲰉 G and all i 󲰉 Z.•Example. Let us work in the group Z21 ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} under the operation of multiplication modulo 21. m=12. 586 mod 21 = 586 mod 12 mod 21 = 52 mod 12 mod 21 = 25 mod 21 = 4 *5•If G is a group, a set S 󲰋 G is called a subgroup if it is a group in its own right, under the same operation as that under which G is a group. •Fact. Let G be a group and let S be a subgroup of G. Then the order of S divides the order of G.6Algorithms and their running times•Since in cryptography we will be working with BIG numbers, the complexity of algorithms taking numbers as inputs is measured as a function of the bit-length of the numbers.•E.g. PrintinBinary (A), where A=2k takes k operations7Some basic algorithms4 COMPUTATIONAL NUMBER THEORYAlgorithm Input Output Running TimeINT-DIV a, N (N > 0) (q, r) with a = Nq + r and 0 ≤ r < N O(|a| · |N |)MOD a, N (N > 0) a mod N O(|a| · |N |)EXT-GCD a, b ((a, b) "= (0, 0)) (d, a, b) with d = gcd(a, b) = aa + bb O(|a| · |b|)MOD-ADD a, b, N (a, b ∈ ZN) (a + b) mod N O(|N |)MOD-MULT a, b, N (a, b ∈ ZN) ab mod N O(|N |2)MOD-INV a, N (a ∈ Z∗N) b ∈ Z∗Nwith ab ≡ 1 (mod N ) O(|N |2)MOD-EXP a, n, N (a ∈ ZN) anmod N O(|n| · |N |2)EXPGa, n (a ∈ G) an∈ G 2|n| G-operationsFigure 9.1: Some basic algorithms and their running time. Unless otherwise indicated, aninput value is an integer and the running time is the number of bit operations. G denotes a group.9.2.2 Integer division and mod algorithmsWe define the integer division function as taking input two integers a, N, with N > 0, and returningthe quotient and remainder obtained by dividing a by N. That is, the function returns (q, r) such8Cyclic groups and generators•If g 󲰉 G is any member of the group, the order of g is defined to be the least positive integer n such that gn = 1. We let <g> = { gi : i 󲰉 Zn } = {g0,g1,..., gn-1} denote the set of group elements generated by g. This is a subgroup of order n. •Def. An element g of the group is called a generator of G if <g>=G, or, equivalently, if its order is m=|G|.•Def. A group is cyclic if it contains a generator.•If g is a generator of G, then for every a 󲰉 G there is a unique integer i 󲰉 Zm such that gi = a. This i is called the discrete logarithm of a to base g, and we denote it by DLogG,g(a). •DLogG,g(a) is a function that maps G to Zm, and moreover this function is a bijection.•The function of Zm to G defined by i ! gi is called the discrete exponentiation function9•Example. Let p = 11. Then Z11 = {1,2,3,4,5,6,7,8,9,10} has order p # 1 = 10. We find the subgroups generated by group elements 2 and 5. We raise them to the powers 0,...,9. •••<2> = {1,2,3,4,5,6,7,8,9,10}=Z11 <5> = {1,3,4,5,9}2 is a generator and thus Z11 is cyclic.*8 COMPUTATIONAL NUMBER THEORYFig. 9.1. (The input a is not required to be relatively prime to N even though it usually will be, sois listed as coming from ZN.) In that case, each group operation is implemented via MOD-MULTand takes O(|N|2) time, so the running time of the algorithm is O(|n| · |N|2). Since n is usuallyin ZN, this comes to O(|N |3). The salient fact to remember is that modular exponentiation is acubic time algorithm.9.3 Cyclic groups and generatorsLet G be a group, let 1 denote its identity element, and let m = |G| be the order of G. If g ∈ Gis any member of the group, the order of g is defined to be the least positive integer n such thatgn= 1. We let"g# = { gi: i ∈ Zn} = {g0, g1, . . . , gn−1}denote the set of group elements generated by g. A fact we do not prove, but is easy to verify, isthat this set is a subgroup of G. The order of this subgroup (which, by definition, is its size) is justthe order of g. Fact 9.6 tells us that the order n of g divides the order m of the group. An elementg of the group is called a generator of G if "g# = G, or, equivalently, if its order is m. If g is agenerator of G then for every a ∈ G there is a unique integer i ∈ Zmsuch …


View Full Document

GT CS 4803 - Very basic number theory

Download Very basic number theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Very basic number theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Very basic number theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?