\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 10 CMSC 456. Morally DUE Nov 18}}


{\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 MIDTERM SOLUTIONS}


\item
(30 points)
We want to factor 91. We will do a QS modified so you can do it by hand
(also the number is not that large).
We are curious for which $B$ this will work.
Note that $\ceil{\sqrt{91}}=10$.

\begin{enumerate}
\item
(10 points)
In this problem we use $B=1$ (so can only use the prime 2).
Compute and try to 1-factor:

$(10+0)^2 \pmod {91}$

$(10+1)^2 \pmod {91}$

$\vdots$

until you get a set of 1-fact numbers whose product is a square.
Then use that information to factor 91.
ALSO- note how many numbers are in the above list (that is, the $(10+i)^2 \pmod {91}$'s).
SHOW work, for example the first line is

$(10+0)^2 = 100 \equiv 9$ NOT 1-fact.

\item
(10 points)
In this problem we use $B=2$ (so can only use the primes 2,3).
Compute and try to 2-factor:

$(10+0)^2 \pmod {91}$

$(10+1)^2 \pmod {91}$

$\vdots$

until you get a set of 2-fact numbers whose product is a square.
Then use that information to factor 91.
ALSO- note how many numbers are in the above list (that is, the $(10+i)^2 \pmod {91}$'s).
SHOW work.

\item
(10 points)
Recall that the trivial algorithm is to just divide $2,3,4,\ldots,\floor{\sqrt{N}}$ into $N$ until
one works. How many divisions would this take? Is it more or less time then QS with $B=1$? $B=2$?
(We count time on the quad sieve, for this problem, as just the length of the list.)

\end{enumerate}

%\vspace{5mm}
\centerline{\textbf{GOTO NEXT PAGE}}
\newpage


\item
(30 points)
We are going to use the log-trick to detect ahead of time if a number
is probably $B$-fact. We will use $\log_{10}$.
We look at the attempt
to factor $N= 53044897$ via QS. Note
$\ceil{\sqrt{N}}=7284$.
We will use $B=14$ so the primes are $2,3,5,7,11$, $13,17,19,23,29$, $31,37,41,43$.

Below we have many of the first 20 numbers you will come across while trying
to do the QS ($\equiv$ is mod $N$.) 
We also tell you which of the first 14 primes divides the number.
\begin{enumerate}
\item
For each number $y$ you will do the following.
\begin{enumerate}
\item
Compute $\ceil{\log_{10}(y)} - \sum_{p \hbox{ div $y$}} \ceil{\log_{10}(p)}$.

You may assume that, for all $z$,  $\ceil{\log_{10}(z)}$ is the number of digits in $z$.
(Sum is over first 14 primes that divide $y$.)

\item
Try to $B$-factor $y$ and note if it is $B$-fact.
\end{enumerate}
\item
Find a number $s$ such that, for all numbers $y$ on the list, 

\begin{itemize}
\item
$y$ is $B$-fact implies $\ceil{\log_{10}(y)} - \sum_{p \hbox{ div $y$}} \ceil{\log_{10}(p)}\le s$.
\item
$y$ is not $B$-fact implies $\ceil{\log_{10}(y)} - \sum_{p \hbox{ div $y$}} \ceil{\log_{10}(p)}\ge s+1$.
\end{itemize}
\end{enumerate}


We now present the list with a caveat: we omitted all of them that had either 0 or 1
prime factor within the first 14 primes.


\begin{itemize}
\item
$(7284+1)^2 \equiv  26328$.   primes that divide this number: 2,3.

\item
$(7284+4)^2 \equiv   70047$.    primes that divide this number: 3, 43.

\item
$(7284+5)^2 \equiv   84624$.   primes that divide this number: 2,3,41,43.

\item
$(7284+7)^2 \equiv  113784$.    primes that divide this number: 2,3,11.

\item
$(7284+8)^2 \equiv  128367$.    primes that divide this number: 3,17.

\item
$(7284+10)^2 \equiv  157539$.    primes that divide this number: 3,17. 

\item
$(7284+11)^2 \equiv  172128$.    primes that divide this number: 2,3,11.

\item
$(7284+13)^2 \equiv  201312$.   primes that divide this number: 2,3.

\item
$(7284+17)^2 \equiv  259704$.  primes that divide this number: 2,3.

\item
$(7284+19)^2 \equiv  288912$. primes that divide this number: 2,3,13.

\end{itemize}


\centerline{\textbf{GOTO NEXT PAGE}}

\newpage

\item
(40 points)
This is a programming assignment.
You will write a program that counts the number of $B$-fact numbers in a given range.

Begin by inputting three lines from standard input.
On the first line, a positive integer $B$ will be given.
On the second line, a positive integer $x$ will be given, and on the third line, a positive integer $y$ will be given.
You can assume $x < y$.
You will print only one value to standard output, namely the number of $B$-fact numbers in the closed interval $[x,y]$.
How you choose to compute this number is entirely up to you.

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{``hw10 - 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.

\begin{enumerate}
\item
(30 points)
Submit your code files to Gradescope as described above to be tested by the autograder.

\item
(10 points)
Using the program you wrote, create a scatter plot displaying the number of $B$-fact numbers in the range $1$ to $10^5$, where $B$ takes on all integers in the range $1$ to $100$.
Submit the plot with the rest of your homework.
\end{enumerate}

\end{enumerate}


\end{document}