\documentclass[12pt,ifthen]{article} \usepackage{url} \newif{\ifshowsoln} \showsolntrue \newcommand{\und}{\_\_\_\_\_\_\_\_\_} \newcommand{\Z}{\mathbb{Z}} \usepackage{amsmath} \usepackage{amssymb} % for \nmid \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\st}{\mathrel{:}} \newcommand{\es}{\emptyset} \newcommand{\bits}[1]{\{0,1\}^{{#1}}} \begin{document} \centerline{\textbf{HW 5 CMSC 456. Morally DUE Oct 7}} {\textbf{NOTE- THE HW IS FOUR PAGES LONG}} \begin{enumerate} \item (0 points) READ the syllabus- Content and Policy. What is your name? What is the day and time of the midterm? \item (20 points) \begin{enumerate} \item (20 points) Alice wants to find safe primes. She will, as usual, pick a random string of bits and test. She wants to make sure that if she tests $p$, then $p$ is NOT even but ALSO $\frac{p-1}{2}$ is NOT even. How can she do this? Give pseudocode that will, given $L$, generate an arbitrary $L$ bit number (it can be off by 1) such that if the number is $p$ then both $p$ and $\frac{p-1}{2}$ are odd. \item (0 points) Think about how Alice can also make sure that $p$ and $\frac{p-1}{2}$ are not divisible by 3. \end{enumerate} \item (20 points) \begin{enumerate} \item (20 points) A {\it Saadiq Prime} is a prime $p$ such that either $p-1=2q$ where $q$ is a prime OR $p-1=6q$ where $q$ is a prime. Give psuedocode for an EFFICIENT algorithm for the following: given a prime that you are promised is a Saadiq prime, find a generator for $\Z_p^*$. \item (0 points) Think about: Usually we look for a safe prime, and once we have it, we look for a generator. What is a PRO of instead looking for a Saadiq prime and then looking for a generator? What is a CON of doing so? \item (0 points) Think about how we may generalize the notion of Saadiq prime and how useful that would be. \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE FOR NEXT PROBLEM } \newpage \item (20 points) For each $x \ge 1$, \begin{itemize} \item Let $f(x)$ denote the number of primes $\le x$ \item Let $g(x)$ denote the number of safe primes $\le x$. \item Let $h(x)$ denote the number of Saadiq primes $\le x$. \end{itemize} And now for the actual problem \begin{enumerate} \item (5 points) Give a table of the values $f(x)$, $g(x)$, and $h(x)$ for \\ $x=1000,2000,\ldots,10000$. Your data does not need to be 100\% correct, but should be very close. (\textit{Hint}: consider modifying your code from the previous programming assignment.) \item (5 points) Find $A,B$ so that $f(x) \approx \frac{Ax}{\ln x} + B$ fits the data pretty well. Sample $x$ at every multiple of $100$ up to $10000$. (Recall that $\ln{x}$ is the natural log of $x$.) \item (5 points) Find $A,B$ so that $g(x) \approx \frac{Ax}{\ln x} + B$ fits the data pretty well. Sample $x$ at every multiple of $100$ up to $10000$. \item (5 points) Find $A,B$ so that $h(x) \approx \frac{Ax}{\ln x} + B$ fits the data pretty well. Sample $x$ at every multiple of $100$ up to $10000$. \end{enumerate} \centerline{\bf GOTO NEXT PAGE} \newpage \item (25 points) Alice and Bob are going to do El Gamal with $p=89$ and $g=30$. \begin{enumerate} \item (5 points) Alice picks $a=3$ and Bob picks $b=6$. What is the shared secret key $s$ that they need to begin doing El Gamal? \item (5 points) Alice wants to send the message 43. What does she send? We will call what she sends $c_{43}$ for later. \item (5 points) Alice wants to send the message 26. What does she send? We will call what she sends $c_{26}$ for later. \item (5 points) Alice wants to send the message 69. What does she send? We will call what she sends $c_{69}$ for later. \item (5 points) If you did the problems above correctly then you will note that $c_{43}+c_{26}\equiv c_{69} \pmod {89}$. Also note that $43+26=69$. Is this a coincidence? Explain. \end{enumerate} \bigskip \centerline{\bf GOTO NEXT PAGE} \newpage \item (15 points) Compute the following and show your work. (You may use a calculator for simple operations such as multiplication.) \begin{enumerate} \item (5 points) $7^{999,999,999,999,999} \pmod {100}$ \item (5 points) $7^{999,999,999,999,999} \pmod {101}$ \item (5 points) $7^{999,999,999,999,999} \pmod {102}$ \end{enumerate} \end{enumerate} \end{document}