aboutsummaryrefslogtreecommitdiff
path: root/src/Homework3/Homework3.tex
diff options
context:
space:
mode:
Diffstat (limited to 'src/Homework3/Homework3.tex')
-rw-r--r--src/Homework3/Homework3.tex552
1 files changed, 552 insertions, 0 deletions
diff --git a/src/Homework3/Homework3.tex b/src/Homework3/Homework3.tex
new file mode 100644
index 0000000..a2b3d02
--- /dev/null
+++ b/src/Homework3/Homework3.tex
@@ -0,0 +1,552 @@
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 ![](path) 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
375format. Complete the exercises by modifying this file, and submit the
376modified version}
377 \end{center}
378
379 \vspace{1cm}
380 \textbf{Exercise 1}
381
382Use 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
409Write 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
421After exchanging messages with the RSA protocol seen in class, Alice and
422Bob decide to meet and play their favorite game: flip a coin. They like
423this game very much because it does not take long to set it up and they
424have exactly the same chances of winning.
425
426Unfortunately, due to the COVID-19 pandemic they cannot meet in person,
427and despite being good friends they don't trust each other enough to
428play this game via Webex call. Luckily, Alice is an expert in
429cryptography and she knows how to play this game using the Chinese
430remainder theorem.
431
432The 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\),
439computes \(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
443Chinese 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
447Since \(n\) is the product of two primes, there are \(4\) possible
448square roots of \(b\) modulo \(n\), corresponding to the solutions of
449the four systems of congruences (one for each possible combination of
450\(\pm\)) \begin{align*}\begin{cases}
451z\equiv \pm x\pmod p\\
452z \equiv \pm y\pmod q
453\end{cases}\end{align*}
454
455One of those solutions is \(a\) and another is \(-a\), and Bob knows
456them. Alice is picking one of the \(4\) possible roots at random (she
457chooses between \(x\) and \(-x\) and between \(y\) and \(-y\)), so she
458has \(50\%\) chance of picking one that Bob already knows. This
459corresponds 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,
463Bob 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
465situation \(g\) is always one of the two prime factors of \(n\).)}
466
467Since factoring a number without extra information is very hard, Alice
468will be convinced that she must have given Bob one of the square roots
469that he did not know, so she admits the loss.
470
471\end{itemize}
472
473Now 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
497In case cheating is detected, a message should be printed saying that
498the 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
545This homework assignment is worth \(20\%\) of your final grade. Exercise
5461 is worth 4 points (one for each part) and Exercise 2 is worth 12
547points (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}

Generated with cgit - Back to sebastiano.tronto.net