Transcript Integers and Algorithms - School of Computing Science

AF2
Turn off your
phones
Primes, gcd, some examples, reading
Primes
• p>1 is prime if the only positive factors are 1 and p
• if p is not prime it is composite
The Fundamental Theorem of Arithmetic
Every positive integer can be expressed as a unique
product of primes
k
n p
i 1
ei
i
• How many prime numbers are there?
Is there a largest prime number?
• assume we know all the prime numbers
• let p be the largest prime
• multiply all the primes together
• add 1
• call this n
• n is not divisible by 2, we get remainder 1
• n is not divisible by 3, we get remainder 1
• n is not divisible by 5, we get remainder 1
•…
• n is not divisible by p, we get remainder 1
• But, by the FTA we know n has a prime factorisation
• Therefore n must have a prime divisor > p
• Therefore there is no greatest prime
Due to Euclid
PRIMES
If n is composite n has a prime divisor  n
composite( n)  n  a.b
a  n b  n
(a 
nb 
n)
Therefore, the divisor a or b is either prime or due to the
fundamental theorem of arithmetic, can be expressed as a
product of primes
n has a divisor  n
How big a prime do we want?
for RSA encryption
“The most efficient factorisation methods (1999)
require billions of years to factor 400 digit integers.
Consequently … when 200 digit primes … messages
encrypted … cannot be found in a reasonable time.”
“When new factorisation techniques are found …
it will be necessary to use larger primes to ensure
secrecy/security of messages.”
gcd, a geometric view
152
57
 We have a floor to tile
 The floor is 57 units wide and 152 units long
 What is the largest square tile we can use
to tile the floor
 this will be the least number of square tiles!
gcd, a geometric view
19
19
57
152
 Find gcd(57,152)
 19 is the answer
 we need 24 tiles
Theorem
 when a = b.q + r
 greatest common divisor of a and b
is also
 greatest common divisor of b and r
 i.e. gcd(a,b) = gcd(b,r)
A proof follows
The proof is based on what we already
know about division
RTP: gcd(a,b) = gcd(b,r) where a = b.q + r
Sketch of the proof
Show that common divisors of a and b are also
common divisors of b and r
(1) show that if some d|a and d|b then d|r
(2) show that if some d|b and d|r then d|a
(3) conclude that a common divisor of a and b is
also a common divisor of b and r
(4) consequently gcd(a,b) = gcd(b,r)
RTP: gcd(a,b) = gcd(b,r) where a = b.q + r
(1) show that if some d|a and d|b then d|r
a = b.q + r
a - b.q = r
[( a  bq  r )  (d | a)  (d | b)]  d | r
We have already proved that
• if d|b then d|b.q
• if d|a and d|b.q then d|(a - b.q)
• (a – b.q) = r
•  d|r
Consequently a common divisor of a and b also divides r
RTP: gcd(a,b) = gcd(b,r) where a = b.q + r
(2) show that if some d|b and d|r then d|a
a = b.q + r
[( a  bq  r )  (d | b)  (d | r )]  d | a
We have already proved that
• if d|b then d|b.q
• if d|b.q and d|r then d|(b.q + r)
• (b.q + r) = a
•  d|a
Consequently a common divisor of b and r also divides a
RTP: gcd(a,b) = gcd(b,r) where a = b.q + r
(3) conclude that a common divisor of a and b is
also a common divisor of b and r
From (1) and (2) we have proved that
 a common divisor of a and b is also a divisor of r
 a common divisor of b and r is also a divisor of a
 consequently a common divisor of a and b is also
a common divisor of b and r
RTP: gcd(a,b) = gcd(b,r) where a = b.q + r
(4) consequently gcd(a,b) = gcd(b,r)
From (3) we can conclude that the greatest common
divisor of a and b is also a greatest common divisor
of b and r
This suggests an algorithm
 given a and b
 if a = 0 then b is the gcd
 if b = 0 then a is the gcd
 otherwise
 a b = q remainder r
 we have established that we can substitute
 gcd(a,b) with gcd(b,r)
 now compute gcd(b,r)
 note, r is decreasing!
gcd(a,b)
• gcd(a,b)
• if b = 0
• then a
• else gcd(b,a mod b)
• (0) gcd(a,b)
• (1) if b = 0 goto 6
• (2) let r := a mod b
• (3) a := b
• (4) b := r
• (5) goto (1)
• (6) return(a)
 gcd(a,b)
 while b  0
 do begin
 r := a mod b;
 a := b;
 b := r;
end;
a
[gcd(a:integer,b:integer) : integer
-> if (b = 0) a else gcd(b,a mod b)]
[relativePrime(a:integer,b:integer) : boolean
-> gcd(a,b) = 1]
Try
• gcd(414,662) and then gcd(662,414)
• gcd(120,500) and gcd(500,120)
• list all numbers relative prime to 22
I invented an
algorithm more
than 2200 years
before anyone
build a computer
New topic
Numbers
But I guess you already know this stuff so I will be fast
Numbers
n  ak b  ak 1b
k
k 1
 ...  a1b  a0
• A number to the base b
• it has k+1 terms
• the a’s are all in the range 0 to b-1
• what is
• 10101101 base 2 in base 10
• peter base 26 in base 10
Numbers
n  ak b  ak 1b
k
k 1
 ...  a1b  a0
95610  9.10 2  5.101  6.100
101011012  1.27  0.26  1.25  0.2 4  1.23  1.2 2  0.21  1.20
6
3
2
1
0
101011012 128
1.2700.232
10.25 80.424 
1
.
2

1
.
2

0
.
2

1
.
2
0 1
 173
• what is
• 10101101 base 2 in base 10
• peter base 26 in base 10
Numbers
n  ak b  ak 1b
k
k 1
 ...  a1b  a0
Hexadecimal: to the base 16
Use digits 0 to 9 then A, B, C, D, E, and F
A2 F 30616  10.165  2.16 4  15.163  3.16 2  0.161  6.160
Octal: base 8
Convert from one base to another (b)
n  ak b k  ak 1b k 1  ...  a1b  a0
Given the number n, divide it by b to get a new number and a remainder
n  bq0  a0
0  a0  b
The remainder is the least significant digit. Now repeat the process
q0  bq1  a1
0  a1  b
The remainder is then the second least significant digit
Keep going
Convert from one base to another (b)
n  ak b k  ak 1b k 1  ...  a1b  a0
Find the binary expansion of 2710
27  2.13  1 27  2.13  1 27  2.13  1 27  2.13  1
13  2.6  1 13  2.6  1 13  2.6  1
6  2.3  0
6  2.3  0
3  2.1  1
27  2.13  1
13  2.6  1
6  2.3  0
3  2.1  1
1  2.0  1
2710  110112
Adding numbers
Assume our numbers are held in arrays and the least significant
digit is on the left hand side with index 0
add(a, b)
c : 0
for i : 0 to n - 1
do begin
d : (a i  b i  c)/2 
s i : a i  b i  c  2d
c : d
end
s n : c
NOTE: pseudo code!
This is the “old school” way of doing it
A thought, challenge
How does a computer read in integers?
We assume that characters are read in one by one
If on the input stream we have the
sequence/string “23189” read() will deliver “2”
and the next read() will deliver “3”, and the next “1”
Numbers
Are these fair assumptions?
 Can you do arithmetic in different bases?
 I expect so
 Can you do addition, multiplication, subtraction, division
 in different bases? (I expect so)
 Do you know the algorithm for this?
 Again, I expect so.