Homework3.tex (28535B)
1 \documentclass[11pt]{article} 2 3 \usepackage[breakable]{tcolorbox} 4 \usepackage{parskip} % Stop auto-indenting (to mimic markdown behaviour) 5 6 \usepackage{iftex} 7 \ifPDFTeX 8 \usepackage[T1]{fontenc} 9 \usepackage{mathpazo} 10 \else 11 \usepackage{fontspec} 12 \fi 13 14 % Basic figure setup, for now with no caption control since it's done 15 % automatically by Pandoc (which extracts  syntax from Markdown). 16 \usepackage{graphicx} 17 % Maintain compatibility with old templates. Remove in nbconvert 6.0 18 \let\Oldincludegraphics\includegraphics 19 % Ensure that by default, figures have no caption (until we provide a 20 % proper Figure object with a Caption API and a way to capture that 21 % in the conversion process - todo). 22 \usepackage{caption} 23 \DeclareCaptionFormat{nocaption}{} 24 \captionsetup{format=nocaption,aboveskip=0pt,belowskip=0pt} 25 26 \usepackage[Export]{adjustbox} % Used to constrain images to a maximum size 27 \adjustboxset{max size={0.9\linewidth}{0.9\paperheight}} 28 \usepackage{float} 29 \floatplacement{figure}{H} % forces figures to be placed at the correct location 30 \usepackage{xcolor} % Allow colors to be defined 31 \usepackage{enumerate} % Needed for markdown enumerations to work 32 \usepackage{geometry} % Used to adjust the document margins 33 \usepackage{amsmath} % Equations 34 \usepackage{amssymb} % Equations 35 \usepackage{textcomp} % defines textquotesingle 36 % Hack from http://tex.stackexchange.com/a/47451/13684: 37 \AtBeginDocument{% 38 \def\PYZsq{\textquotesingle}% Upright quotes in Pygmentized code 39 } 40 \usepackage{upquote} % Upright quotes for verbatim code 41 \usepackage{eurosym} % defines \euro 42 \usepackage[mathletters]{ucs} % Extended unicode (utf-8) support 43 \usepackage{fancyvrb} % verbatim replacement that allows latex 44 \usepackage{grffile} % extends the file name processing of package graphics 45 % to support a larger range 46 \makeatletter % fix for grffile with XeLaTeX 47 \def\Gread@@xetex#1{% 48 \IfFileExists{"\Gin@base".bb}% 49 {\Gread@eps{\Gin@base.bb}}% 50 {\Gread@@xetex@aux#1}% 51 } 52 \makeatother 53 54 % The hyperref package gives us a pdf with properly built 55 % internal navigation ('pdf bookmarks' for the table of contents, 56 % internal cross-reference links, web links for URLs, etc.) 57 \usepackage{hyperref} 58 % The default LaTeX title has an obnoxious amount of whitespace. By default, 59 % titling removes some of it. It also provides customization options. 60 \usepackage{titling} 61 \usepackage{longtable} % longtable support required by pandoc >1.10 62 \usepackage{booktabs} % table support for pandoc > 1.12.2 63 \usepackage[inline]{enumitem} % IRkernel/repr support (it uses the enumerate* environment) 64 \usepackage[normalem]{ulem} % ulem is needed to support strikethroughs (\sout) 65 % normalem makes italics be italics, not underlines 66 \usepackage{mathrsfs} 67 68 69 70 % Colors for the hyperref package 71 \definecolor{urlcolor}{rgb}{0,.145,.698} 72 \definecolor{linkcolor}{rgb}{.71,0.21,0.01} 73 \definecolor{citecolor}{rgb}{.12,.54,.11} 74 75 % ANSI colors 76 \definecolor{ansi-black}{HTML}{3E424D} 77 \definecolor{ansi-black-intense}{HTML}{282C36} 78 \definecolor{ansi-red}{HTML}{E75C58} 79 \definecolor{ansi-red-intense}{HTML}{B22B31} 80 \definecolor{ansi-green}{HTML}{00A250} 81 \definecolor{ansi-green-intense}{HTML}{007427} 82 \definecolor{ansi-yellow}{HTML}{DDB62B} 83 \definecolor{ansi-yellow-intense}{HTML}{B27D12} 84 \definecolor{ansi-blue}{HTML}{208FFB} 85 \definecolor{ansi-blue-intense}{HTML}{0065CA} 86 \definecolor{ansi-magenta}{HTML}{D160C4} 87 \definecolor{ansi-magenta-intense}{HTML}{A03196} 88 \definecolor{ansi-cyan}{HTML}{60C6C8} 89 \definecolor{ansi-cyan-intense}{HTML}{258F8F} 90 \definecolor{ansi-white}{HTML}{C5C1B4} 91 \definecolor{ansi-white-intense}{HTML}{A1A6B2} 92 \definecolor{ansi-default-inverse-fg}{HTML}{FFFFFF} 93 \definecolor{ansi-default-inverse-bg}{HTML}{000000} 94 95 % commands and environments needed by pandoc snippets 96 % extracted from the output of `pandoc -s` 97 \providecommand{\tightlist}{% 98 \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} 99 \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}} 100 % Add ',fontsize=\small' for more characters per line 101 \newenvironment{Shaded}{}{} 102 \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{{#1}}}} 103 \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{{#1}}} 104 \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} 105 \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} 106 \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}} 107 \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} 108 \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} 109 \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{{#1}}}} 110 \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{{#1}}} 111 \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}} 112 \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{{#1}}} 113 \newcommand{\RegionMarkerTok}[1]{{#1}} 114 \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}} 115 \newcommand{\NormalTok}[1]{{#1}} 116 117 % Additional commands for more recent versions of Pandoc 118 \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{{#1}}} 119 \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} 120 \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}} 121 \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{{#1}}} 122 \newcommand{\ImportTok}[1]{{#1}} 123 \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{{#1}}}} 124 \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}} 125 \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}} 126 \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{{#1}}} 127 \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{{#1}}}} 128 \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{{#1}}} 129 \newcommand{\BuiltInTok}[1]{{#1}} 130 \newcommand{\ExtensionTok}[1]{{#1}} 131 \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{{#1}}} 132 \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{{#1}}} 133 \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}} 134 \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}} 135 136 137 % Define a nice break command that doesn't care if a line doesn't already 138 % exist. 139 \def\br{\hspace*{\fill} \\* } 140 % Math Jax compatibility definitions 141 \def\gt{>} 142 \def\lt{<} 143 \let\Oldtex\TeX 144 \let\Oldlatex\LaTeX 145 \renewcommand{\TeX}{\textrm{\Oldtex}} 146 \renewcommand{\LaTeX}{\textrm{\Oldlatex}} 147 % Document parameters 148 % Document title 149 \title{Mathematical Software - Homework 3} 150 \date{Deadline: Sunday, May 9th} 151 152 153 154 155 156 % Pygments definitions 157 \makeatletter 158 \def\PY@reset{\let\PY@it=\relax \let\PY@bf=\relax% 159 \let\PY@ul=\relax \let\PY@tc=\relax% 160 \let\PY@bc=\relax \let\PY@ff=\relax} 161 \def\PY@tok#1{\csname PY@tok@#1\endcsname} 162 \def\PY@toks#1+{\ifx\relax#1\empty\else% 163 \PY@tok{#1}\expandafter\PY@toks\fi} 164 \def\PY@do#1{\PY@bc{\PY@tc{\PY@ul{% 165 \PY@it{\PY@bf{\PY@ff{#1}}}}}}} 166 \def\PY#1#2{\PY@reset\PY@toks#1+\relax+\PY@do{#2}} 167 168 \expandafter\def\csname PY@tok@w\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.73,0.73}{##1}}} 169 \expandafter\def\csname PY@tok@c\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 170 \expandafter\def\csname PY@tok@cp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.74,0.48,0.00}{##1}}} 171 \expandafter\def\csname PY@tok@k\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 172 \expandafter\def\csname PY@tok@kp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 173 \expandafter\def\csname PY@tok@kt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.69,0.00,0.25}{##1}}} 174 \expandafter\def\csname PY@tok@o\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 175 \expandafter\def\csname PY@tok@ow\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}} 176 \expandafter\def\csname PY@tok@nb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 177 \expandafter\def\csname PY@tok@nf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} 178 \expandafter\def\csname PY@tok@nc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} 179 \expandafter\def\csname PY@tok@nn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} 180 \expandafter\def\csname PY@tok@ne\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.82,0.25,0.23}{##1}}} 181 \expandafter\def\csname PY@tok@nv\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 182 \expandafter\def\csname PY@tok@no\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.00,0.00}{##1}}} 183 \expandafter\def\csname PY@tok@nl\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.63,0.00}{##1}}} 184 \expandafter\def\csname PY@tok@ni\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,0.60}{##1}}} 185 \expandafter\def\csname PY@tok@na\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.49,0.56,0.16}{##1}}} 186 \expandafter\def\csname PY@tok@nt\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 187 \expandafter\def\csname PY@tok@nd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}} 188 \expandafter\def\csname PY@tok@s\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 189 \expandafter\def\csname PY@tok@sd\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 190 \expandafter\def\csname PY@tok@si\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}} 191 \expandafter\def\csname PY@tok@se\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.13}{##1}}} 192 \expandafter\def\csname PY@tok@sr\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}} 193 \expandafter\def\csname PY@tok@ss\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 194 \expandafter\def\csname PY@tok@sx\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 195 \expandafter\def\csname PY@tok@m\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 196 \expandafter\def\csname PY@tok@gh\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}} 197 \expandafter\def\csname PY@tok@gu\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.50,0.00,0.50}{##1}}} 198 \expandafter\def\csname PY@tok@gd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.00,0.00}{##1}}} 199 \expandafter\def\csname PY@tok@gi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.63,0.00}{##1}}} 200 \expandafter\def\csname PY@tok@gr\endcsname{\def\PY@tc##1{\textcolor[rgb]{1.00,0.00,0.00}{##1}}} 201 \expandafter\def\csname PY@tok@ge\endcsname{\let\PY@it=\textit} 202 \expandafter\def\csname PY@tok@gs\endcsname{\let\PY@bf=\textbf} 203 \expandafter\def\csname PY@tok@gp\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}} 204 \expandafter\def\csname PY@tok@go\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.53,0.53}{##1}}} 205 \expandafter\def\csname PY@tok@gt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.27,0.87}{##1}}} 206 \expandafter\def\csname PY@tok@err\endcsname{\def\PY@bc##1{\setlength{\fboxsep}{0pt}\fcolorbox[rgb]{1.00,0.00,0.00}{1,1,1}{\strut ##1}}} 207 \expandafter\def\csname PY@tok@kc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 208 \expandafter\def\csname PY@tok@kd\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 209 \expandafter\def\csname PY@tok@kn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 210 \expandafter\def\csname PY@tok@kr\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 211 \expandafter\def\csname PY@tok@bp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}} 212 \expandafter\def\csname PY@tok@fm\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}} 213 \expandafter\def\csname PY@tok@vc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 214 \expandafter\def\csname PY@tok@vg\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 215 \expandafter\def\csname PY@tok@vi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 216 \expandafter\def\csname PY@tok@vm\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}} 217 \expandafter\def\csname PY@tok@sa\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 218 \expandafter\def\csname PY@tok@sb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 219 \expandafter\def\csname PY@tok@sc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 220 \expandafter\def\csname PY@tok@dl\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 221 \expandafter\def\csname PY@tok@s2\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 222 \expandafter\def\csname PY@tok@sh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 223 \expandafter\def\csname PY@tok@s1\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}} 224 \expandafter\def\csname PY@tok@mb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 225 \expandafter\def\csname PY@tok@mf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 226 \expandafter\def\csname PY@tok@mh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 227 \expandafter\def\csname PY@tok@mi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 228 \expandafter\def\csname PY@tok@il\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 229 \expandafter\def\csname PY@tok@mo\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}} 230 \expandafter\def\csname PY@tok@ch\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 231 \expandafter\def\csname PY@tok@cm\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 232 \expandafter\def\csname PY@tok@cpf\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 233 \expandafter\def\csname PY@tok@c1\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 234 \expandafter\def\csname PY@tok@cs\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}} 235 236 \def\PYZbs{\char`\\} 237 \def\PYZus{\char`\_} 238 \def\PYZob{\char`\{} 239 \def\PYZcb{\char`\}} 240 \def\PYZca{\char`\^} 241 \def\PYZam{\char`\&} 242 \def\PYZlt{\char`\<} 243 \def\PYZgt{\char`\>} 244 \def\PYZsh{\char`\#} 245 \def\PYZpc{\char`\%} 246 \def\PYZdl{\char`\$} 247 \def\PYZhy{\char`\-} 248 \def\PYZsq{\char`\'} 249 \def\PYZdq{\char`\"} 250 \def\PYZti{\char`\~} 251 % for compatibility with earlier versions 252 \def\PYZat{@} 253 \def\PYZlb{[} 254 \def\PYZrb{]} 255 \makeatother 256 257 258 % For linebreaks inside Verbatim environment from package fancyvrb. 259 \makeatletter 260 \newbox\Wrappedcontinuationbox 261 \newbox\Wrappedvisiblespacebox 262 \newcommand*\Wrappedvisiblespace {\textcolor{red}{\textvisiblespace}} 263 \newcommand*\Wrappedcontinuationsymbol {\textcolor{red}{\llap{\tiny$\m@th\hookrightarrow$}}} 264 \newcommand*\Wrappedcontinuationindent {3ex } 265 \newcommand*\Wrappedafterbreak {\kern\Wrappedcontinuationindent\copy\Wrappedcontinuationbox} 266 % Take advantage of the already applied Pygments mark-up to insert 267 % potential linebreaks for TeX processing. 268 % {, <, #, %, $, ' and ": go to next line. 269 % _, }, ^, &, >, - and ~: stay at end of broken line. 270 % Use of \textquotesingle for straight quote. 271 \newcommand*\Wrappedbreaksatspecials {% 272 \def\PYGZus{\discretionary{\char`\_}{\Wrappedafterbreak}{\char`\_}}% 273 \def\PYGZob{\discretionary{}{\Wrappedafterbreak\char`\{}{\char`\{}}% 274 \def\PYGZcb{\discretionary{\char`\}}{\Wrappedafterbreak}{\char`\}}}% 275 \def\PYGZca{\discretionary{\char`\^}{\Wrappedafterbreak}{\char`\^}}% 276 \def\PYGZam{\discretionary{\char`\&}{\Wrappedafterbreak}{\char`\&}}% 277 \def\PYGZlt{\discretionary{}{\Wrappedafterbreak\char`\<}{\char`\<}}% 278 \def\PYGZgt{\discretionary{\char`\>}{\Wrappedafterbreak}{\char`\>}}% 279 \def\PYGZsh{\discretionary{}{\Wrappedafterbreak\char`\#}{\char`\#}}% 280 \def\PYGZpc{\discretionary{}{\Wrappedafterbreak\char`\%}{\char`\%}}% 281 \def\PYGZdl{\discretionary{}{\Wrappedafterbreak\char`\$}{\char`\$}}% 282 \def\PYGZhy{\discretionary{\char`\-}{\Wrappedafterbreak}{\char`\-}}% 283 \def\PYGZsq{\discretionary{}{\Wrappedafterbreak\textquotesingle}{\textquotesingle}}% 284 \def\PYGZdq{\discretionary{}{\Wrappedafterbreak\char`\"}{\char`\"}}% 285 \def\PYGZti{\discretionary{\char`\~}{\Wrappedafterbreak}{\char`\~}}% 286 } 287 % Some characters . , ; ? ! / are not pygmentized. 288 % This macro makes them "active" and they will insert potential linebreaks 289 \newcommand*\Wrappedbreaksatpunct {% 290 \lccode`\~`\.\lowercase{\def~}{\discretionary{\hbox{\char`\.}}{\Wrappedafterbreak}{\hbox{\char`\.}}}% 291 \lccode`\~`\,\lowercase{\def~}{\discretionary{\hbox{\char`\,}}{\Wrappedafterbreak}{\hbox{\char`\,}}}% 292 \lccode`\~`\;\lowercase{\def~}{\discretionary{\hbox{\char`\;}}{\Wrappedafterbreak}{\hbox{\char`\;}}}% 293 \lccode`\~`\:\lowercase{\def~}{\discretionary{\hbox{\char`\:}}{\Wrappedafterbreak}{\hbox{\char`\:}}}% 294 \lccode`\~`\?\lowercase{\def~}{\discretionary{\hbox{\char`\?}}{\Wrappedafterbreak}{\hbox{\char`\?}}}% 295 \lccode`\~`\!\lowercase{\def~}{\discretionary{\hbox{\char`\!}}{\Wrappedafterbreak}{\hbox{\char`\!}}}% 296 \lccode`\~`\/\lowercase{\def~}{\discretionary{\hbox{\char`\/}}{\Wrappedafterbreak}{\hbox{\char`\/}}}% 297 \catcode`\.\active 298 \catcode`\,\active 299 \catcode`\;\active 300 \catcode`\:\active 301 \catcode`\?\active 302 \catcode`\!\active 303 \catcode`\/\active 304 \lccode`\~`\~ 305 } 306 \makeatother 307 308 \let\OriginalVerbatim=\Verbatim 309 \makeatletter 310 \renewcommand{\Verbatim}[1][1]{% 311 %\parskip\z@skip 312 \sbox\Wrappedcontinuationbox {\Wrappedcontinuationsymbol}% 313 \sbox\Wrappedvisiblespacebox {\FV@SetupFont\Wrappedvisiblespace}% 314 \def\FancyVerbFormatLine ##1{\hsize\linewidth 315 \vtop{\raggedright\hyphenpenalty\z@\exhyphenpenalty\z@ 316 \doublehyphendemerits\z@\finalhyphendemerits\z@ 317 \strut ##1\strut}% 318 }% 319 % If the linebreak is at a space, the latter will be displayed as visible 320 % space at end of first line, and a continuation symbol starts next line. 321 % Stretch/shrink are however usually zero for typewriter font. 322 \def\FV@Space {% 323 \nobreak\hskip\z@ plus\fontdimen3\font minus\fontdimen4\font 324 \discretionary{\copy\Wrappedvisiblespacebox}{\Wrappedafterbreak} 325 {\kern\fontdimen2\font}% 326 }% 327 328 % Allow breaks at special characters using \PYG... macros. 329 \Wrappedbreaksatspecials 330 % Breaks at punctuation characters . , ; ? ! and / need catcode=\active 331 \OriginalVerbatim[#1,codes*=\Wrappedbreaksatpunct]% 332 } 333 \makeatother 334 335 % Exact colors from NB 336 \definecolor{incolor}{HTML}{303F9F} 337 \definecolor{outcolor}{HTML}{D84315} 338 \definecolor{cellborder}{HTML}{CFCFCF} 339 \definecolor{cellbackground}{HTML}{F7F7F7} 340 341 % prompt 342 \makeatletter 343 \newcommand{\boxspacing}{\kern\kvtcb@left@rule\kern\kvtcb@boxsep} 344 \makeatother 345 \newcommand{\prompt}[4]{ 346 \ttfamily\llap{{\color{#2}[#3]:\hspace{3pt}#4}}\vspace{-\baselineskip} 347 } 348 349 350 351 % Prevent overflowing lines due to hard-to-break entities 352 \sloppy 353 % Setup hyperref package 354 \hypersetup{ 355 breaklinks=true, % so long urls are correctly broken across lines 356 colorlinks=true, 357 urlcolor=urlcolor, 358 linkcolor=linkcolor, 359 citecolor=citecolor, 360 } 361 % Slightly bigger margins than the latex defaults 362 363 \geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in} 364 365 366 367 \begin{document} 368 369 \maketitle 370 371 372 373 \begin{center} 374 \emph{For this exercise you should have received this text in .ipynb 375 format. Complete the exercises by modifying this file, and submit the 376 modified version} 377 \end{center} 378 379 \vspace{1cm} 380 \textbf{Exercise 1} 381 382 Use SageMath to solve the following problems: 383 384 \begin{enumerate} 385 \def\labelenumi{(\alph{enumi})} 386 \item 387 Find the roots of the following polynomial over \(\mathbb Q\): 388 \begin{align*} 389 p = 4 x^{7} + 4 x^{6} + 3 x^{5} - 13 x^{4} - 13 x^{3} - 9 x^{2} + 3 x + 3 \in \mathbb Q[x] 390 \end{align*} 391 \item 392 Find the roots of the same polynomial \(p\) over \(\mathbb R\) and 393 over \(\mathbb C\). 394 \item 395 Find the determinant, the trace and the characteristic polynomial of 396 the following matrix: \begin{align*} 397 A=\left(\begin{array}{rrrr} 398 -1 & 1 & -1 & 0 \\ 399 1 & \frac{1}{2} & 1 & 0 \\ 400 \frac{1}{2} & -\frac{1}{2} & -2 & 1 \\ 401 0 & 0 & 1 & 1 402 \end{array}\right) 403 \end{align*} 404 \item 405 Find a solution to the linear system \(A\mathbf x =\mathbf v\), where 406 \(A\) is the matrix above and \(\mathbf v=(1, 2, 3, 4)\). 407 \end{enumerate} 408 409 Write your code in the cell below. 410 411 \begin{tcolorbox}[breakable, size=fbox, boxrule=1pt, pad at break*=1mm,colback=cellbackground, colframe=cellborder] 412 \prompt{In}{incolor}{ }{\boxspacing} 413 \begin{Verbatim}[commandchars=\\\{\}] 414 415 \end{Verbatim} 416 \end{tcolorbox} 417 418 \vspace{1cm} 419 \textbf{Exercise 2} 420 421 After exchanging messages with the RSA protocol seen in class, Alice and 422 Bob decide to meet and play their favorite game: flip a coin. They like 423 this game very much because it does not take long to set it up and they 424 have exactly the same chances of winning. 425 426 Unfortunately, due to the COVID-19 pandemic they cannot meet in person, 427 and despite being good friends they don't trust each other enough to 428 play this game via Webex call. Luckily, Alice is an expert in 429 cryptography and she knows how to play this game using the Chinese 430 remainder theorem. 431 432 The game plays out as follows: 433 434 \begin{itemize} 435 \item[(A1)] Alice picks two large prime numbers \(p\) and \(q\), she computes 436 \(n=pq\) and sends \(n\) to Bob, keeping \(p\) and \(q\) secret. 437 438 \item[(B1)] Bob picks a random number \(a\) with \(1<a<n\) and \(\gcd(a,n)=1\), 439 computes \(b=a^2\mod n\) and sends \(b\) to Alice, keeping \(a\) secret. 440 441 \item[(A2)] Alice computes two numbers \(x\) and \(y\) such that 442 \(x^2\equiv b\pmod p\) and \(y^2\equiv b\pmod q\) and she uses the 443 Chinese remainder theorem to compute a number \(z\) such that 444 \(z\equiv x\pmod p\) and \(z\equiv y\pmod q\), so that 445 \(z^2\equiv b\pmod n\). Then she sends \(z\) to Bob. 446 447 Since \(n\) is the product of two primes, there are \(4\) possible 448 square roots of \(b\) modulo \(n\), corresponding to the solutions of 449 the four systems of congruences (one for each possible combination of 450 \(\pm\)) \begin{align*}\begin{cases} 451 z\equiv \pm x\pmod p\\ 452 z \equiv \pm y\pmod q 453 \end{cases}\end{align*} 454 455 One of those solutions is \(a\) and another is \(-a\), and Bob knows 456 them. Alice is picking one of the \(4\) possible roots at random (she 457 chooses between \(x\) and \(-x\) and between \(y\) and \(-y\)), so she 458 has \(50\%\) chance of picking one that Bob already knows. This 459 corresponds to Alice flipping a coin, and she wins if she picks 460 \(\pm a\): 461 462 \item[(B2)] If \(z\equiv\pm a\pmod n\), Bob declares to have lost. Otherwise, 463 Bob claims to have won, and as proof he produces one prime factor of 464 \(n\) by computing \(g=\gcd(n,a+z)\). \emph{(One can prove that in this 465 situation \(g\) is always one of the two prime factors of \(n\).)} 466 467 Since factoring a number without extra information is very hard, Alice 468 will be convinced that she must have given Bob one of the square roots 469 that he did not know, so she admits the loss. 470 471 \end{itemize} 472 473 Now to the actual exercise: 474 475 \begin{enumerate} 476 \def\labelenumi{(\alph{enumi})} 477 \item 478 Write the code for the functions A1, B1 and B2 as indicated in the 479 cell below. The function A2 is already written. 480 \item 481 Modify the functions B1, A2 and B2 to check that the opponent is not 482 cheating. More precisely: 483 484 \begin{itemize} 485 \tightlist 486 \item 487 In B1, Bob should check that \(n\) is not a prime power. \emph{(This 488 is the only way Alice can try to cheat: if she sends Bob a number 489 \(n\) that is the product of more than two primes, than she has less 490 than \(50\%\) chance of winning!)} 491 \item 492 In A2, Alice should check that \(b\) is a square modulo \(n\). 493 \item 494 In B2, Bob should check that \(z^2\equiv a^2\pmod n\). 495 \end{itemize} 496 497 In case cheating is detected, a message should be printed saying that 498 the person is cheating. 499 \end{enumerate} 500 501 \newpage 502 503 \begin{tcolorbox}[breakable, size=fbox, boxrule=1pt, pad at break*=1mm,colback=cellbackground, colframe=cellborder] 504 \prompt{In}{incolor}{1}{\boxspacing} 505 \begin{Verbatim}[commandchars=\\\{\}] 506 \PY{c+c1}{\PYZsh{} Alice needs this to compute the square roots} 507 \PY{k+kn}{from} \PY{n+nn}{sage}\PY{n+nn}{.}\PY{n+nn}{rings}\PY{n+nn}{.}\PY{n+nn}{finite\PYZus{}rings}\PY{n+nn}{.}\PY{n+nn}{integer\PYZus{}mod} \PY{k}{import} \PY{n}{square\PYZus{}root\PYZus{}mod\PYZus{}prime} 508 509 \PY{k}{def} \PY{n+nf}{A1}\PY{p}{(}\PY{p}{)}\PY{p}{:} 510 \PY{c+c1}{\PYZsh{} This function must return two distinct primes and their product.} 511 512 \PY{k}{def} \PY{n+nf}{B1}\PY{p}{(}\PY{n}{n}\PY{p}{)}\PY{p}{:} 513 \PY{c+c1}{\PYZsh{} This function must return a random integer a} 514 \PY{c+c1}{\PYZsh{} with 1\PYZlt{}a\PYZlt{}n and gcd(a,n)=1.} 515 516 \PY{k}{def} \PY{n+nf}{A2}\PY{p}{(}\PY{n}{b}\PY{p}{,} \PY{n}{p}\PY{p}{,} \PY{n}{q}\PY{p}{)}\PY{p}{:} 517 \PY{n}{x} \PY{o}{=} \PY{n}{ZZ}\PY{p}{(}\PY{n}{square\PYZus{}root\PYZus{}mod\PYZus{}prime}\PY{p}{(}\PY{n}{Integers}\PY{p}{(}\PY{n}{p}\PY{p}{)}\PY{p}{(}\PY{n}{b}\PY{p}{)}\PY{p}{,} \PY{n}{p}\PY{p}{)}\PY{p}{)} 518 \PY{n}{y} \PY{o}{=} \PY{n}{ZZ}\PY{p}{(}\PY{n}{square\PYZus{}root\PYZus{}mod\PYZus{}prime}\PY{p}{(}\PY{n}{Integers}\PY{p}{(}\PY{n}{q}\PY{p}{)}\PY{p}{(}\PY{n}{b}\PY{p}{)}\PY{p}{,} \PY{n}{q}\PY{p}{)}\PY{p}{)} 519 \PY{k}{return} \PY{n}{crt}\PY{p}{(}\PY{n}{x}\PY{p}{,} \PY{n}{y}\PY{p}{,} \PY{n}{p}\PY{p}{,} \PY{n}{q}\PY{p}{)} 520 521 \PY{k}{def} \PY{n+nf}{B2}\PY{p}{(}\PY{n}{a}\PY{p}{,} \PY{n}{z}\PY{p}{,} \PY{n}{n}\PY{p}{)}\PY{p}{:} 522 \PY{c+c1}{\PYZsh{} This function must print out one of two messages:} 523 \PY{c+c1}{\PYZsh{} \PYZdq{}Bob has lost\PYZdq{} if z is congruent to a or \PYZhy{}a modulo n.} 524 \PY{c+c1}{\PYZsh{} \PYZdq{}Bob has won, proof: \PYZdq{} followed by a prime factor of n otherwise.} 525 \PY{c+c1}{\PYZsh{} In this case the prime must be calculated as explained above.} 526 527 528 \PY{c+c1}{\PYZsh{} This is how the game plays out:} 529 \PY{n}{p}\PY{p}{,} \PY{n}{q}\PY{p}{,} \PY{n}{n} \PY{o}{=} \PY{n}{A1}\PY{p}{(}\PY{p}{)} 530 \PY{n+nb}{print}\PY{p}{(}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Alice picked n =}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{n}\PY{p}{)} 531 \PY{n+nb}{print}\PY{p}{(}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{[[ Alice}\PY{l+s+s2}{\PYZsq{}}\PY{l+s+s2}{s secret:}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{p}\PY{p}{,} \PY{n}{q}\PY{p}{,} \PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{]]}\PY{l+s+s2}{\PYZdq{}}\PY{p}{)} 532 \PY{n}{a} \PY{o}{=} \PY{n}{B1}\PY{p}{(}\PY{n}{n}\PY{p}{)} 533 \PY{n}{b} \PY{o}{=} \PY{n}{a}\PY{o}{\PYZca{}}\PY{l+m+mi}{2} \PY{o}{\PYZpc{}} \PY{n}{n} 534 \PY{n+nb}{print}\PY{p}{(}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Bob picked b =}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{b}\PY{p}{)} 535 \PY{n+nb}{print}\PY{p}{(}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{[[ Bob}\PY{l+s+s2}{\PYZsq{}}\PY{l+s+s2}{s secret:}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{a}\PY{p}{,} \PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{]]}\PY{l+s+s2}{\PYZdq{}}\PY{p}{)} 536 \PY{n}{z} \PY{o}{=} \PY{n}{A2}\PY{p}{(}\PY{n}{b}\PY{p}{,} \PY{n}{p}\PY{p}{,} \PY{n}{q}\PY{p}{)} 537 \PY{n+nb}{print}\PY{p}{(}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Alice picked z =}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{z}\PY{p}{)} 538 \PY{n}{B2}\PY{p}{(}\PY{n}{a}\PY{p}{,} \PY{n}{z}\PY{p}{,} \PY{n}{n}\PY{p}{)} 539 \end{Verbatim} 540 \end{tcolorbox} 541 542 \vspace{1cm} 543 \textbf{Grading} 544 545 This homework assignment is worth \(20\%\) of your final grade. Exercise 546 1 is worth 4 points (one for each part) and Exercise 2 is worth 12 547 points (8 points for part (a) and 4 points for part (b)), for a total of 548 \textbf{16 points}. 549 550 551 552 \end{document}