# UCSD CSE 207 - Computational Number Theory (18 pages)

Previewing pages 1, 2, 3, 4, 5, 6 of 18 page document
View Full Document

## Computational Number Theory

Previewing pages 1, 2, 3, 4, 5, 6 of actual document.

View Full Document
View Full Document

## Computational Number Theory

73 views

Pages:
18
School:
University of California, San Diego
Course:
Cse 207 - Modern Cryptography

Unformatted text preview:

Chapter 9 Computational Number Theory 9 1 The basic groups We let Z 2 1 0 1 2 denote the set of integers We let Z 1 2 denote the set of positive integers and N 0 1 2 the set of non negative integers 9 1 1 Integers mod N If a b are integers not both zero then their greatest common divisor denoted gcd a b is the largest integer d such that d divides a and d divides b If gcd a b 1 then we say that a and b are relatively prime If a N are integers with N 0 then there are unique integers r q such that a N q r and 0 r N We call r the remainder upon division of a by N and denote it by a mod N We note that the operation a mod N is defined for both negative and non negative values of a but only for positive values of N When a is negative the quotient q will also be negative but the remainder r must always be in the indicated range 0 r N If a b are any integers and N is a positive integer we write a b mod N if a mod N b mod N We associate to any positive integer N the following two sets ZN 0 1 N 1 Z N i Z 1 i N 1 and gcd i N 1 The first set is called the set of integers mod N Its size is N and it contains exactly the integers that are possible values of a mod N as a ranges over Z We define the Euler Phi or totient function Z N by N Z N for all N Z That is N is the size of the set Z N 9 1 2 Groups Let G be a non empty set and let be a binary operation on G This means that for every two points a b G a value a b is defined Definition 9 1 1 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 COMPUTATIONAL NUMBER THEORY 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 The element b in the invertibility condition is referred to as the inverse of the element a and is denoted a 1 We now

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...