Transcript Integers - SIUE Computer Science

MATH 224 – Discrete Mathematics
Integers and Computers
Integers and number theory are important building blocks for computer science.
(Number theory deals with the properties of integers.)
Why are integers so important in computer science?
Consider the memory of a computer. What does it store? Just sequences of zeros and
ones. When put all together the total memory may be interpreted as one large binary
integer.
How are integers most commonly represented in memory? What is the 32 bit
representation of 500? What is the 32 bit representation of -500?
3/27/2016
1
MATH 224 – Discrete Mathematics
Integers and Computers
How are letters (characters) stored inside a computer’s memory?
How are floating point numbers (i.e. numbers with fractional parts) stored?
How are text files; Word documents; C++ programs; and machine instructions
stored in memory?
At the lowest level, digital computers can only work with numbers.
How is audio stored with integers?
How are photographs stored with integers? Can color be represented by an
integer?
How are videos stored as integers?
3/27/2016
2
MATH 224 – Discrete Mathematics
Integer Terminology
Integers may be classified as either prime numbers or composite numbers. What is a
prime number, and what is a composite number?
The following is often referred to as the Fundamental Theorem of Arithmetic.
Every positive integer larger than 1 may be expressed as a single prime number or a
unique product of primes. This product is called the prime factorization of an integer.
Those numbers that are not primes, having two or more primes in their prime
factorization, are called composite numbers.
What about negative integers less than 1. Do they have a unique prime
factorization? Is there a way to make the factorization unique?
3/27/2016
3
MATH 224 – Discrete Mathematics
Division Algorithm (uniqueness of modulus)
The so called division algorithm is not really an algorithm, but instead states a
property of integers. It states that when an integer a is divided by a positive integer d,
the non-negative remainder r is unique. Note that d may not be equal to zero and r is
restricted to a value 0 ≤ r < d. What if d is negative?
Also note that r = a modulus d or in C++, r = = a % d.
If d is a divisor of a what is the value of a % d?
3/27/2016
4
MATH 224 – Discrete Mathematics
Other Important Terminology
Greatest common divisor: Given two integers, the largest number that divides both
evenly is called the greatest common divisor. Give an example of the use of the
greatest common divisor.
Relatively prime: Two numbers that do not have any common divisor other than 1
are said to be relatively prime.
Least common multiple: Given two integers, the smallest number that is divisible by
both of the integers is called the least common multiple. Give an example of the use
of the least common multiple.
3/27/2016
5
MATH 224 – Discrete Mathematics
Modular Arithmetic (the % operator in C++)
Modular Arithmetic deals with the remainder when one integer is divided by another.
So for example 12 ≡ 5 mod 7. Or in C++ (12 % 7 = = 5) is a true proposition. There
is an entire theory built on the modulus operator. In fact a set of values modulus a
prime number is sometimes called a field under the operations of addition and
multiplication.
For example 5*3 ≡ 1 mod 7, which implies that 3 is equivalent to 1/5 in arithmetic
modulo 7, and is called the multiplicative inverse. What is the multiplicative inverse
of 4 in mod 7 arithmetic?
And 5 + 2 ≡ 0 mod 7, which implies that 2 is equivalent to –5 in arithmetic modulo 7.
Thus 2 is the additive inverse of 5 in mod 7 arithmetic.
3/27/2016
6
MATH 224 – Discrete Mathematics
Modular Arithmetic Applications in CS
Some of these concepts related to modular arithmetic are used in CS.
• Modular arithmetic is used to specify negative integers in a way that makes
computation easier for computers,
• In the area of security, modular arithmetic is used for encryption and authentication.
What is encryption? Give an example of where it is used.
• Simple modular arithmetic is used to create hash tables for storing data such as the
symbol table for a program in C++.
• Modular arithmetic is used to create circular arrays to implement queues.
What is a
circular array and what is a queue in computer science?
• Modular arithmetic is used to generate random numbers by most random number
generators. These are called pseudo-random since they are not truly random.
3/27/2016
7
MATH 224 – Discrete Mathematics
Integer Representation Using Base Two
Why is base 2 used by most computers?
Negative integers are represented using the twos complement of the positive number.
For example, with an eight bit integer negative 32 corresponds to 224. Eight bit
numbers are viewed as numbers mod 256 since the integers from 0 to 255 may be
presented. Note that 32 + 224 % 256 = = 0. As binary numbers
32 is 0010 0000 and 224 is 1110 0000. Now if we add these together we have
0010 0000
+1110 0000
1 0000 0000
With eight bit numbers the one on the right is just dropped. To make this work all
integers with a leading one are interpreted as negative numbers.
Why does mod 256 not work for the multiplicative inverse?
3/27/2016
8
MATH 224 – Discrete Mathematics
Integer Representation Using Octal and Hexadecimal
For humans it is often easier to work with either octal, base 8, or hexadecimal, base 16
numbers.
Every digit of an octal number represents three bits in a binary representation and
every bit of a hexadecimal representation represents four bits in a binary
representation. Can you explain why these statements are true?
For example the binary number 0101 0001 has the hexadecimal representation of 5116,
and 1111 01011 has hexadecimal representation FB16 . What are these numbers in
decimal?
Finally, how are floating point numbers represented? I binary used to represent
them? In what way does it make sense to say that they look like integers in
memory?
3/27/2016
9
MATH 224 – Discrete Mathematics
The Euclidean Algorithm for the GCD
The Euclidean Algorithm is named after the Greek mathematician Euclid who is most
well know for his axioms of plane geometry. Euclid’s algorithm finds, the greatest
common divisor for two positive integers. Below is a version of this algorithm in C++
int function gcd (int a, int b) {
int x = a, y = b, r;
while (!(y = = 0)) {
r = x % y;
x = y;
y=r
}
return x;
} // end gcd
Lets apply this function to 60 and 210. What happens to the values of x and y after
the first pass through the while loop?
3/27/2016
10
MATH 224 – Discrete Mathematics
Public Key Encryption Using RSA
One of the most significant uses of modular arithmetic is encrypting messages so that
only the person having a special key is able to determine the original message. Below
are the basic steps of the RSA algorithm.
First everyone has the following information.
• An integer n = pq where p and q are very large prime numbers, but only the value
of n is know by everyone.
• An integer e that is relatively prime to (p−1)(q−1)
Second only the person receiving the message has the values of p and q. If p and q
are very large, even with a very fast computer it will take an extremely long time to
compute them from the information provided.
3/27/2016
11
MATH 224 – Discrete Mathematics
Public Key Encryption Using RSA
Now with the values of n and e, a message may be encrypted by converting the message
to integers M, perhaps using ASCII. The integers are modified by means of the
following formula.
C = Me mod n
Note that there are algorithms for doing modular exponentiation quickly. After the
conversion the integers corresponding to C are sent.
The receiver decrypts the message using the formula
M = Cd mod n
The value of d is the multiplicative inverse of e mod (p−1)(q−1). The value of d is not
difficult to calculate if p and q are know, but the values of p−1 and q−1 are needed to
find d.
See the text for a proof that this actually works and an example of how these
formulas are used.
3/27/2016
12