Transcript Slides

Based on Lecture Slides
from Steven Rudich, CMU
15
15
a
Even very
simple
computation
al problems
can be
surprisingly
subtle.
Compiler Translation
A compiler must translate a high
level language (e.g., C) with complex
operations (e.g., exponentiation)
into a lower level language (e.g.,
assembly) that can only support
simpler operations (e.g.,
multiplication).
8
b:=a
b:=a*a
b:=b*a
b:=b*a
b:=b*a
b:=b*a
b:=b*a
b:=b*a
b:=a*a
b:=b*b
b:=b*b
This method costs only 3
multiplications. The
savings are significant if
b:=a8 is executed often.
General Version
Given a constant k, how
k
do we implement b:=a
with the fewest
number of
multiplications?
Powering By Repeated
Multiplication
Input:
a,n
Output:
A sequence starting with
a, ending with an, and such
that each entry other
than the first is the
product of previous
entries.
Example
Input:
Output:
Output:
Output:
a,5
a, a2, a3, a4, a5
or
a, a2, a3, a5
or
a, a2, a4, a5
Definition of M(n)
M(n) = The minimum number of
multiplications
n
required to produce a
by repeated
multiplication
What is M(n)? Can we calculate it
exactly? Can we approximate it?
Exemplification:
Try out a problem or
solution on small examples.
Some Very Small Examples
• What is M(0)?
– M(0) does not really make sense
• What is M(1)?
– M(1) = 0
[a]
• What is M(2)?
– M(2) = 1
[a, a2]
M(8) = ?
a, a2, a4, a8 is a way to make a8 in 3
multiplications. What does this tell
us about the value of M(8)?
M(8) = ?
a, a2, a4, a8 is a way to make a8 in 3
multiplications. What does this tell
us about the value of M(8)?
M(8)  3
Upper Bound
?  M(8)  3
Lower Bound
?  M(8)  3
Lower Bound
3  M(8)
Exhaustive Search. There are only two
sequences with 2 multiplications.
Neither of them make 8:
a, a2, a3 & a, a2, a4
3  M(8)  3
Lower
Bound
Upper
Bound
M(8) = 3
Applying Two Ideas
Abstraction:
Abstract away the inessential
features of a problem or solution
=
Representation:
Understand the relationship between
different representations of the same
information or idea
1
2
3
The a is a red herring.
x
a
times
y
a
is
x+y
a
Everything besides the
exponent is inessential. This
should be viewed as a problem
of repeated addition, rather
than repeated multiplication.
Addition Chains
M(n) = Number of stages required
to make n, where we start
at 1 and in each subsequent
stage we add two
previously constructed
numbers.
Examples
Addition Chain for 8:
12358
Minimal Addition Chain for 8:
1248
M(30) =
?
15
15
a
Some Addition Chains For 30
1
2
4
8
16
24
28
1
2
4
5
10
20
30
1
2
3
5
10
15
30
1
2
4
8
10
20
30
30
? < M(30) < 6
? < M (n) < ?
Take 5
minutes to
think like a
computer
scientist
Binary Representation
Let Bn be the number of 1s in the binary
representation of n. Ex: B5 = 2 since 101 is
the binary representation of 5
Proposition: Bn ≤
┕
log2 (n)
┙
+1
The length of the binary representation of
n is bounded by this quantity.
Binary Method
Repeated Squaring Method
Repeated Doubling Method
Phase I
(Repeated Doubling)
For log2 n stages:
Add largest so far to itself
(1, 2, 4, 8, 16, . . . )
Phase II
(Make n from bits and pieces)
Expand n in binary to see how n is the sum
of Bn powers of 2. Use Bn-1 stages to make
from the powers of 2 created in phase I
Total Cost:
n
log2 n  Bn  1
Binary Method Applied To 30
30
Phase I
1
2
4
8
16
Phase II: 6 14 30
Binary
11110
1
10
100
1000
10000
(Cost: 7 additions)
M(n)  log2 n  Bn  1  2 log2 n
Abstraction:
Abstract away the inessential
features of a problem or solution
=
The repeated
squaring method
works for modular
arithmetic and for
raising a matrix to
a power.
Abstraction:
Abstract away the inessential
features of a problem or solution
=
The repeated
squaring method
works for any
notion of
“multiplication”
that is associative.
(a*b)*c = a*(b*c)
A Lower Bound Idea
You can’t make any number bigger than
2n in n steps.
1 2 4 8 16 32 64 . . .
Failure of
Imagination?
Induction Proof
Theorem: For all n 0, no n stage
addition chain will contain a number
greater than 2n
Let Sk be the statement that no k stage
addition chain will contain a number
greater than 2k
Base case: k=0. S0 is true since no chain can
exceed 20 after 0 stages.
Let k > 0,
S k ⇒ Sk + 1
At stage k+1 we add two numbers from the
previous stage. From Sk we know that they
both are bounded by 2k. Hence, their sum is
bounded by 2k+1. No number greater than 2k+1
can be present by stage k+1.
Change Of Variable
All numbers obtainable in m stages are
bounded by 2m. Let m = log2(n).
Thus, All numbers obtainable in log2(n)
stages are bounded by n.
M(n)  log2 (n)
In fact, M(n)  log2 (n)
Theorem: The only way to make 2i in
i stages is by repeated doubling
Assumption: Let 2i+1 be the first counter-example to
the theorem.
To make 2i+1 at stage i+1 requires that some number
of size at least 2i be present at stage i. By previous
result such a number could not be larger than 2i, and
thus equals 2i.
By the assumption, 2i can only be constructed by
repeated doubling. The only possible final move was
to double 2i. Thus 2i+1 must result from repeated
doubling, contradicting the assumption.
5 < M(30)
Suppose that M(30)=5. At the last stage, we
added two numbers x1 and x2 to get 30.
Without loss of generality (WLOG), we
assume that x1 x2.
Thus, x1  15
By doubling bound, x1  16
But x1 can’t be 16 since there is only one way
to make 16 in 4 stages and it does not make
14 along the way.
Thus, x1 = 15 and M(15)=4
Suppose M(15) = 4
At stage 3, a number bigger than 7.5, but not
more than 8 must have existed. There is only
one sequence that gets 8 in 3 additions: 1 2 4
8
That sequence does not make 7 along the way
and hence there is nothing to add to 8 to
make 15 at the next stage.
Thus, M(15) > 4.
CONTRADICTION.
M(30)=6
Factoring Bound
M(ab) M(a)+M(b)
Factoring Bound
M(ab) M(a)+M(b)
Proof:
• Construct a in M(a) additions
• Using a as a unit follow a construction
method for b using M(b) additions. In
other words, every time the
construction of b refers to a number x,
use the number a times x.
Example
45 = 5 * 9
M(5)=3
M(9)=4
M(45)  3+4
[1 2 4 5]
[1 2 4 8 9 ]
[1 2 4 5 10 20 40 45]
Corollary (Using Induction)
M(a1a2a3…an) M(a1)+M(a2)+…+M(an)
Proof: For n=1 the bound clearly holds.
Assume it has been shown for up to
n-1. Apply theorem using a= a1a2a3…an-1 and
b=an to obtain:
M(a1a2a3…an) M(a1a2a3…an-1)+M(an)
By inductive assumption,
M(a1a2a3…an-1) M(a1)+M(a2)+…+M(an-1)
More Corollaries
Corollary: M(ak) kM(a)
Corollary:
1
2
3
n
M(p1 p2 p3  pn )
 1M(p1 ) +  2M(p2 ) +  nM(pn )
Does equality hold?
M(33) < M(3) + M(11)
M(3) = 2
M(11)= 5
M(3) + M(11) = 7
M(33) = 6
[1 2 3]
[1 2 3 5 10 11]
[1 2 4 8 16 32 33]
The conjecture of equality fails. There have
been many nice conjectures. . . .
Conjecture: M(2n) = M(n) +1
(A. Goulard)
A fastest way to an even number is to make
half that number and then double it.
Proof given in 1895 by E. de Jonquieres in
L’Intermediere Des Mathematiques, volume
2, pages 125-126
FALSE! M(191)=M(382)=11
Furthermore, there are
infinitely many such
examples.
Open Problem
Is there an n such that:
M(2n) < M(n)
Conjecture
Each stage might as well consist of
adding the largest number so far to one
of the other numbers.
First Counter-example: 12,509
[1 2 4 8 16 17 32 64 128 256 512
1024 1041 2082 4164 8328 8345
12509]
Open Problem
Prove or disprove the ScholzBrauer Conjecture:
M(2n-1)  n - 1 + Bn
(The bound that follows from this
lecture is too weak: M(2n-1)  2n - 1)
The RSA Cryptosystem
Rivest, Shamir, and Adelman (1978)
RSA is one of the most used
cryptographic protocols on the net.
Your browser uses it to establish a
secure session with a site.
Preview: Instructions For RSA use.
Public key: e, n
Anyone wishing to send you a message
m  Zn*, should send you me mod n.
Private key: d, f(n)
When you get an encrypted message
me mod n, do the following:
(me)d mod n = med mod n
= med mod f(n) mod n
= m mod n
Addition And Multiplication Mod n
a + b mod n = [(a mod n) + (b mod n)] mod n
ab mod n = [ (a mod n)(b mod n) ] mod n
This is saying that we can just keep track of
remainders mod n as we multiply and add.
(S,●) is called a group if it has these properties:
closure: a, b  S  a  b  S
associativity: a, b, c  S  ( a  b)  c  a  (b  c )
identity: e  S s.t. a  S e  a  a  e  a
inverse: a  S
a 1  S s.t. a  a 1  a 1  a  e
Z*n = the set of naturals between 1 and n
that are relatively prime to n
Theorem:
Z*n
with multiplication modulo n is a group.
Computing Inverses In Zn*
Suppose we want the inverse of a. In other
words, b such that ab = 1 mod n.
Using an Extended GCD algorithm
Compute GCD(a,n).
Of course the answer is 1, but
also get r, s such that ra+sn = GCD(a,n) = 1.
Taking both sides mod n, we get ra=1 mod n.
Thus r is the inverse of a in the group Zn*
The Euler Phi Function
f(n) = size of Zn*
f(p) = p-1
f(pk) = pk – pk-1
f(pq) = f(p) f(q) p,q distinct primes,
actually even if GCD(p,q)=1.
f(pq) = (p-1)(q-1)
if p,q distinct primes
pq = # of numbers from 1 to pq
p = # of multiples of q up to pq
q = # of multiples of p up to pq
1 = # of multiple of both p and q up to pq
f(pq) = pq – p – q + 1 = (p-1)(q-1)
af(n) = 1 mod n, if GCD(a,n)=1
Lagrange: The size of any subgroup divides
the size of the group.
Note: In a finite group, the powers of an
element x form a subgroup.
Euler’s Corollary: Let G be any finite group of
size s: x  G implies Xs = 1
Euler’s Corollary for Zn*:
af(n) = 1 mod
n
Addition And Multiplication Mod n
a + b mod n = [(a mod n) + (b mod n)] mod n
ab mod n = [ (a mod n)(b mod n) ] mod n
This is saying that we can just keep track of
remainders mod n as we multiply and divide.
Law Of Exponents mod n
Could it be as simple as:
ae mod n = [(a mod n)(e mod n)] mod n
216  2 mod 15
?
Mental Arithmetic Test
890
7
= ? Mod 15
Mental Arithmetic Test
7890 = 7890 mod 4
Mod 15
= 72 mod 15 = 4
Powers of 7:
1, 7, 4, 13, 1, 7, 4, 13, …
Mental Arithmetic Test
890
3
= ? Mod 14
Mental Arithmetic Test
3890 = 3890 mod 6
= 32 = 9
Powers of 3
1, 3, 9, 13, 11, 5, 1
Mod 14
Law Of Exponents mod n
(Correct)
ae mod n = [(a mod n)(e mod f(n))] mod n
The exponent must be taken mod f(n)
Law Of Exponents mod n
ae mod n = [(a mod n)(e mod f(n))] mod n
Proof: e = a f(n) + b
(b < f(n) )
Xe = Xaf(n) Xb = (Xf(n))a Xb = Xb = Xe mod f(n)
Instructions For RSA setup
1. Pick 2 random k-bit primes: p and q.
Let n = pq.
2. Compute f(n). Pick random e
relatively prime to f(n). Compute d =
inverse of e mod f(n). d is called
your private-key.
3. Publish n and e. These are called
your public-key.
Instructions For RSA use.
Anyone wishing to send you a message
m  Zn*, should send you me mod n.
When you get an encrypted message
me mod n, do the following:
(me)d = med mod n
= med mod f(n) mod n
= m mod n
How Can Eve Break The System?
If Eve can quickly compute f(n), then
she can compute d from e and read all
the messages. This might be easier
than factoring.
No one knows how to break RSA
quickly.
Does this mean it is secure?
RSA has an *amazing* feature.
Two people who have never met and
have no prior shared secrets can use
the system. Without this property,
commerce on the net would be
impossible.
REFERENCES
Coxeter, H. S. M. ``The Golden Section,
Phyllotaxis, and Wythoff's Game.'' Scripta
Mathematica 19, 135-143, 1953.
"Recounting Fibonacci and Lucas
Identities" by Arthur T. Benjamin and
Jennifer J. Quinn, The CollegeMathematics
Journal, Vol. 30, No. 5, 1999, pp. 359--366.