[SOLVED] Homework 2 – csci 181

1. (10 pts)
(a) We use a multiplication algorithm that takes time O(log2
(N)) to multiply N1 ·N2
if N1 ≈ N2 ≈ N. If it takes 3 nanoseconds to multiply two 1000 bit numbers then
how long would it take to multiply two 5000 bit numbers?
(b) Let N be a large positive integer. The time it takes to factor N using trial
division is O(
√
N). Assume that N′
is a large positive integer and that the
binary representation of N′ has ten more bits than that of N. Assume that it
takes 11 nanoseconds to factor N using trial division. Approximately how long
would it take to factor N′ using trial division?
2. (10 pts) Let’s say we switch from 1024-bit RSA to 4096-bit RSA. How much longer
does decryption take?
3. (10 pts)
(a) Suppose a programmer wants to compute the sum of integers from 1 to N. The
programmer writes a program by adding 1 and 2 first and then getting the result
and adding it by 3, and so on: (((1 + 2) + 3) + . . . + N). Find the running time
this will take in terms of N.
(b) The sum of integers from 1 to N is N(N + 1)/2. Find the running time in terms
of N that it would take you to compute the sum using the formula N(N + 1)/2
instead.
4. (10 pts) Find the running time required to compute 6N in terms of N. The computer
program would compute ((((6 · 6) · 6)· · ·) · 6).
5. (10 pts) Let Fn denote the nth Fibonacci number. We have F1 = F2 = 1 and for i ≥ 3,
Fi = Fi−1 + Fi−2 (so F3 = 2, F4 = 3, F5 = 5, F6 = 8, . . .). Recall Fn ≈ α
n
, where
α = (1 + √
5)/2. Find the running time of an algorithm that exactly finds the integer
Qn
i=1 Fi using (((F1 ·F2)·F3). . .·Fn). Your answer should be O() of a function of n and
not have an F in it. Explain your answer. For simplicity, assume that you already have
F1, . . . , Fn in storage, so you don’t have to worry about the time to compute them.