\documentclass[12pt,ifthen]{article} \usepackage{comment} \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 9 CMSC 456. Morally DUE Nov 11}} {\textbf{NOTE- THE HW IS THREE 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 FINAL? {\bf READ THE MIDTERM SOLUTIONS. EVEN FOR PROBLEMS YOU GOT RIGHT.} \item (30 points) We want to factor 81072007. We will do a Quadratic Sieve modified so you can do it by hand (also the number is not that large). We outline what you will do AND give you a shortcut! \begin{itemize} \item Note that $\ceil{\sqrt{81072007}}=9004$. \item Normally we would $B$-factor $(9004+x)^2$ for $0\le x\le M$. Instead we will factor some of these number entirely. \item Shortcut: We would like $(9004+x)^2 - 81072007$ to have small factors. Hence we will only pick $x$ such that $(9004+x)^2 - 81072007\equiv 0 \pmod 6$. \end{itemize} An NOW finally for the problem you are to solve: \begin{enumerate} \item (10 points) Fill in the set $X$ in the following sentence. Note that $X\subseteq \{0,1,2,3,4,5\}$. {\it $((9004+x)^2 - 81072007\equiv 0 \pmod 6)$ IFF $(x \bmod 6 \in X)$.} (No proof required.) \item (10 points) For $x\ge 0$ with $x\bmod 6 \in X$, factor $(9004+x)^2 - 81072007$ until you get what you need for the For $x\ge 0$, $x\in X$, factor $(9004+x)^2 - 81072007$ until you get what you need for the Quadratic Sieve Algorithm to proceed. (You can use a factor program you find online.) \item (10 points) Use what you got to find a factor of 81072007. You will need to compute a GCD--- for this you DO NOT need to show you work. {\it Very Very Very Good Advice:} When you get what you think is a factor of 81072007, divide 81072007 by the alleged factor to make sure it divides---this will be a good check on your answer. \end{enumerate} \vspace{5mm} \centerline{\textbf{GOTO NEXT PAGE}} \newpage \newpage \item (30 points) Eve wants to factor $G=139,323,391$ (a product of two primes) using the method Golomb used to factor the Jevons number. This problem will guide you through it. You may use a calculator while doing it, but you must {\bf show your work} as we did on the slides. Throughout this problem $x,y$ are such that $G=x^2-y^2$. During this problem we reduce the number of options for $(x,y)$. \begin{enumerate} \item (6 points) Find a $0\le d\le 99$ such that the following holds: $$y^2 \equiv x^2 + d \pmod {100}$$ \item (6 points) List all possibilities for $(x^2 \bmod {100}, y^2 \bmod {100})$. \item (6 points) Find all $x$ (mod 100) such that $x^2\equiv 0 \pmod {100}$ OR $x^2\equiv 16 \pmod {100}$. Put the union of the two sets into numeric order. You may use \url{https://www.alpertron.com.ar/QUADMOD.HTM} Note that at the end you will have a small set $A$ such that $$x \bmod {100} \in A.$$ (Small means size $\le 20$.) \item (6 points) Show that $x\ge \sqrt{G}$ \item (6 points) Complete the algorithm and factor $G$. \end{enumerate} \vspace{5mm} \centerline{\textbf{GOTO NEXT PAGE}} \newpage \item (40 points) This is a programming assignment. You will implement Pollard rho's algorithm and use it to find factors of numbers. Begin by inputting three lines from standard input. On the first line, an integer $N > 1$ will be given. On the second line, an integer $x$ satisfying $0 \le x < N$ will be given. On the third line, an integer $c$ satisfying $0 \le c < N$ will be given. Your goal is to use Pollard rho's algorithm (described in the lecture slides) to find a nontrivial factor of $N$ (i.e., a positive factor of $N$ other than $1$ and $N$). You will print two lines to standard output. On the first line, you will print out the nontrivial factor the algorithm returns when supplied with the given inputs. Then on the next line, you will print out how many loop iterations the algorithm took before it returned; this value should be on the order of $N^{1/4}$. You may assume each test input used by the autograder will not cause Pollard's rho algorithm to get stuck in an infinite loop. So for instance, $N$ will never be prime. You may use C, C++, Java, Python2/3, and Ruby for this problem. You will be submitting a zip file containing all code files you used to complete this problem to the Gradescope assignment called \centerline{``hw09 - problem 4''.} Upon submission, your code will be automatically run on a Linux machine and tested against various test cases to ensure correctness. You are allowed to submit your code as many times as you want. As with previous programming assignments, upload a bash script called \texttt{run} and (if necessary) another bash script called \texttt{build}. These files must begin with the shebang \texttt{\#!/usr/bin/env bash} on the very first line. If you have any questions or confusions, or if you encounter any technical difficulties, feel free to ask for help on Piazza. \end{enumerate} \end{document}