CS 161 Homework 4

CS161

R-11.2

Use the divide-and-conquer algorithm, from Section 11.2, to compute 10110011·10111010 in binary. Show your work.

Use Karatsuba multiplication.
$x = 10110011$
$y = 10111010$
$x_l=1011$
$x_r = 0011$
$y_l=1011$
$y_r = 1010$
$x_ly_l=1011×1011 = 1111001$
$x_ry_r=0011×1010 = 11110$
$(x_l+x_r)(y_l+y_r)=01110×10101 = 100100110$
(calculate from the same way, divide-and-conquer)
$x_ly_r+x_ry_l = (x_l+x_r)(y_l+y_r)-x_ly_l-x_ry_r=10001111$
$xy=x_ly_l*2^{8}+(x_ly_r+x_ry_l)*2^{4}+x_ry_r=1000001000001110$

R-24.5

Show the execution of method FastExponentiation(5, 12, 13) by constructing a table similar to Table 24.6.

R-24.6

Write a nonrecursive version of Algorithm ExtendedEuclidGCD.

def ExtendedEuclidGCD(a,b):
    if b == 0:
        return (a, 1, 0)
    x1 = 0
    x2 = 1
    y1 = 1
    y2 = 0
    while b > 0:
        q = a // b
        r = a - q * b
        x = x2 - q * x1
        y = y2 - q * y1
        a = b
        b = r
        x2 = x1
        x1 = x
        y2 = y1
        y1 = y
    d = a
    x = x2
    y = y2
    return (d,x,y)

Output:

print(ExtendedEuclidGCD(175,20))
> (5, -1, 9)

C-24.8

Suppose the primes p and q used in the RSA cryptosystem, to define $n = pq$, are in the range [ $\sqrt{n} − \log n, \sqrt{n} + \log n$]. Explain how you can efficiently factor $n$ using this information.

The size of the range is $\sqrt{n} + \log n - (\sqrt{n} − \log n)=2 \log n$. For each composite number n, there is a range of $2 \log n$ to be checked. For each n, we calculate $\sqrt{n} − \log n$ and $\sqrt{n} + \log n$, and then look for prime numbers in the range. Once we have the list of possible prime numbers we multiply them pair by pair to see if the product is n.

As n becomes larger and larger (especially RSA mostly uses very large integers), the range to be searched in ($2 \log n$)will become quite large. And determining prime numbers in this range one by one can be difficult too. For a number as large as a normal RSA, I don't think it will be possible to use such range information to factor the number.