\documentclass[10pt,epsfig]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\parskip 1.5ex

\addtolength{\textwidth}{1in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1in}

\newcommand{\qed}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\reals}{\mbox{\bf R}}
\renewcommand{\baselinestretch}{1.5}
\normalsize

\begin{document}
\textbf{Johnny Chen}

\textbf{Math 124 Problem Set 3}

\textbf{1.}\ In PARI,
$s=(g^n)^{1208}$=lift(Mod$(454,3793)^{1208})=\ $\textbf{2156}.

\textbf{2a.}\ VE RI TAS encodes to
$$22+5\cdot 27+0\cdot 27^2+18\cdot 27^3+9\cdot 27^4+0\cdot 27^5+20\cdot 27^6+1\cdot 27^7+19\cdot 27^8 =
\textbf{5384375093542}.$$ \textbf{2b.}We assume we cannot use
consecutive blank spaces, so the longest sequence would be of the
form $A\ A\ A\ ...A$. We seek the maximal $n$ for which
$1+27^2+...+27^{2N}<10^{20}$; if the remainder is greater than
$27^{N+1}$, we can place another A. Therefore
$(27^{2N+2}-1)/{26}<10^{20}$, so $N=6$.  Now
$10^{20}-(27^{14}-1)/26>27^{13}$, so our longest sequence is
\textbf{14} letters.

\textbf{3.} Write a discrete log program: $f(n) = for(i=1,96;
if(n==lift(Mod(5,97)^i),return(i)));$ Then $f(3)=\ $\textbf{n=70}
and $f(7)=\ $\textbf{m=31}. Therefore $lift(Mod(5,97)^{mn})=\
$\textbf{s=44}.

\textbf{4.} We encrypt $m$ by computing $m^e(mod\ n)$.  In PARI,
lift(Mod$(2005,n)^e)=\ $\textbf{346299873425}.

\textbf{5a.} Since $ed \equiv 1(mod\ \phi(n))$,
$d=lift(Mod(e,eulerphi(n))^{-1})=\ $\textbf{5195621988839}.

\textbf{5b.} To decrypt, $lift(Mod(3539014000459,n)^d)=18464$,
which gives: \textbf{WHY}.

\textbf{6.} No, it's not secure.  An adversary can use Michael's
public key to encrypt each of 0,1,...,26.  Then the adversary can
match each letter that Nikita sends, one by one, and decrypt her
message without having to break the cryptosystem.

\textbf{7a.} Let $m=ed-1$, and try $for(a=2,20,
if(Mod(a,n)^m!=1,print(a)))$; if it prints nothing, set $m=m/2$
and try again, until we have an $m$ such that there are values
for $a$.  We decrease $m$ three times before we find a value
$m=47918...$ with $a$ values $2,3,5,7,8,...$.  If we try
$gcd(lift(Mod(i,n)^m-1,n))$ for these $a$ values, we see that for
$a=7$ we have a $p=gcd(7,n)=37865717$, so $q=n/p=37865693$.

\textbf{7b.} If we know $p$ and $q$ are close, we use the Fermat
factorization method.  We set the precision to $p150$ in PARI,
and then set $t=floor(sqrt(n))+1=37865705$, and find
$sqrt(t^2-n)$, which seems to be 12.  Now $t+s,t-s$ are our
factors: $t+s=37865717$, $t-s=37865693$, as in part a.
\end{document}