\documentclass[11pt,fleqn]{article} \usepackage{latexsym,epsf,epsfig} \usepackage{amsmath,amsthm} \begin{document} \newcommand{\mbf}[1]{\mbox{{\bfseries #1}}} \newcommand{\N}{\mbf{N}} \renewcommand{\O}{\mbf{O}} \newtheorem{thm}{Theorem} \section*{CS 70 homework 8 solutions} Your full name: PUT YOUR NAME HERE \newline Your login name: PUT YOUR LOGIN NAME HERE \newline Homework 8 \newline Your section number: PUT YOUR SECTION NUMBER HERE \newline Your list of partners: LIST YOUR PARTNERS HERE \newline \begin{enumerate} \item The algorithm for computing $a^b\bmod c$ by repeated squaring does not necessarily lead to the minimum number of multiplications. Give an example of $b$ ($b>10$) where the exponentiation can be performed using fewer multiplications, by some other method. YOUR ANSWER GOES HERE. \item Let $p$ and $q$ be primes and let $N = pq$. Show how to determine $p$ and $q$ given $N$ and $(p - 1)(q - 1)$. (In other words, given the public key $(e, N)$, $e$ the encryption exponent and $N$ the RSA modulus, and the value $\varphi(N) = (p - 1)(q - 1)$, it is possible to compute $p$ and $q$ by simple (polynomial time) algebraic operations. This shows that determining $\varphi(N)$ is ``as hard as factoring.'') YOUR ANSWER GOES HERE. \item \begin{enumerate} \item Suppose that the teaching staff of a course involves three professors and two TAs. The solutions to the next homework are encrypted by an encryption key shared by all five. The three professors together should be able to access the solutions, or any one TA with one professor, or both TAs. Suggest a secret-sharing scheme that achieves this. ({\em Hint:} Try weights.) YOUR ANSWER GOES HERE. \item Suppose now that the class is taught by three professors, each with her own two TAs. Any two professors can access the data, as long as one of each professor's TAs (i.e. a total of at least four people) is also present. Now what? YOUR ANSWER GOES HERE. \end{enumerate} \item \begin{enumerate} \item Prove the following: If $p$ is a prime and $y_1,\ldots,y_n\in \N$ are all different from 0 modulo $p$, then $y_1 \times \cdots \times y_n$ is also different from 0 modulo $p$. YOUR ANSWER GOES HERE. \item Prove the following: Given a prime $p$ and two integers $a,b$, it is always possible to find a polynomial $f(x)$ of degree at most 1 such that $f(0)\equiv a \pmod p$ and $f(1) \equiv b \pmod p$. YOUR ANSWER GOES HERE. \item You are given a prime $p$ and a positive number $n