\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