aboutsummaryrefslogtreecommitdiff
path: root/src/Homework3
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano.tronto@gmail.com>2021-05-25 17:10:49 +0200
committerSebastiano Tronto <sebastiano.tronto@gmail.com>2021-05-25 17:10:49 +0200
commitd6c61d988bfa4255baf9cdae42db59ebee38363f (patch)
tree118ff3c2424e735149c145524965a4a337e50beb /src/Homework3
parent46eef66b1e1571c77dc828d7e950b129b4c8bfd0 (diff)
downloadmathsoftware-d6c61d988bfa4255baf9cdae42db59ebee38363f.tar.gz
mathsoftware-d6c61d988bfa4255baf9cdae42db59ebee38363f.zip
Added files
Diffstat (limited to 'src/Homework3')
-rw-r--r--src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb179
-rw-r--r--src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb166
-rw-r--r--src/Homework3/Homework3.aux20
-rw-r--r--src/Homework3/Homework3.ipynb179
-rw-r--r--src/Homework3/Homework3.log962
-rw-r--r--src/Homework3/Homework3.out0
-rw-r--r--src/Homework3/Homework3.pdfbin0 -> 146471 bytes
-rw-r--r--src/Homework3/Homework3.tex552
8 files changed, 2058 insertions, 0 deletions
diff --git a/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb b/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb
new file mode 100644
index 0000000..13bad44
--- /dev/null
+++ b/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb
@@ -0,0 +1,179 @@
1{
2 "cells": [
3 {
4 "cell_type": "markdown",
5 "metadata": {},
6 "source": [
7 "*For this exercise you should have received this text in .ipynb format. Complete the exercises by modifying this file, and submit the modified version*"
8 ]
9 },
10 {
11 "cell_type": "markdown",
12 "metadata": {},
13 "source": [
14 "**Exercise 1**\n",
15 "\n",
16 "Use SageMath to solve the following problems:\n",
17 "\n",
18 "(a) Find the roots of the following polynomial over $\\mathbb Q$:\n",
19 "\\begin{align*}\n",
20 " 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]\n",
21 "\\end{align*}\n",
22 "\n",
23 "(b) Find the roots of the same polynomial $p$ over $\\mathbb R$ and over $\\mathbb C$.\n",
24 "\n",
25 "(c) Find the determinant, the trace and the characteristic polynomial of the following matrix:\n",
26 "\\begin{align*}\n",
27 "A=\\left(\\begin{array}{rrrr}\n",
28 "-1 & 1 & -1 & 0 \\\\\n",
29 "1 & \\frac{1}{2} & 1 & 0 \\\\\n",
30 "\\frac{1}{2} & -\\frac{1}{2} & -2 & 1 \\\\\n",
31 "0 & 0 & 1 & 1\n",
32 "\\end{array}\\right)\n",
33 "\\end{align*}\n",
34 "\n",
35 "(d) Find a solution to the linear system $A\\mathbf x =\\mathbf v$, where $A$ is the matrix above and $\\mathbf v=(1, 2, 3, 4)$.\n",
36 "\n",
37 "Write your code in the cell below."
38 ]
39 },
40 {
41 "cell_type": "code",
42 "execution_count": null,
43 "metadata": {},
44 "outputs": [],
45 "source": []
46 },
47 {
48 "cell_type": "markdown",
49 "metadata": {},
50 "source": [
51 "**Exercise 2**\n",
52 "\n",
53 "After exchanging messages with the RSA protocol seen in class, Alice and Bob decide to meet and play their favorite game: flip a coin. They like this game very much because it does not take long to set it up and they have exactly the same chances of winning.\n",
54 "\n",
55 "Unfortunately, due to the COVID-19 pandemic they cannot meet in person, and despite being good friends they don't trust each other enough to play this game via Webex call. Luckily, Alice is an expert in cryptography and she knows how to play this game using the Chinese remainder theorem.\n",
56 "\n",
57 "The game plays out as follows:\n",
58 "\n",
59 "(A1) Alice picks two large prime numbers $p$ and $q$, she computes $n=pq$ and sends $n$ to Bob, keeping $p$ and $q$ secret.\n",
60 "\n",
61 "(B1) Bob picks a random number $a$ with $1<a<n$ and $\\gcd(a,n)=1$, computes $b=a^2\\mod n$ and sends $b$ to Alice, keeping $a$ secret.\n",
62 "\n",
63 "(A2) Alice computes two numbers $x$ and $y$ such that $x^2\\equiv b\\pmod p$ and $y^2\\equiv b\\pmod q$ and she uses the Chinese remainder theorem to compute a number $z$ such that $z\\equiv x\\pmod p$ and $z\\equiv y\\pmod q$, so that $z^2\\equiv b\\pmod n$. Then she sends $z$ to Bob.\n",
64 "\n",
65 "Since $n$ is the product of two primes, there are $4$ possible square roots of $b$ modulo $n$, corresponding to the solutions of the four systems of congruences (one for each possible combination of $\\pm$)\n",
66 "\\begin{align*}\\begin{cases}\n",
67 "z\\equiv \\pm x\\pmod p\\\\\n",
68 "z \\equiv \\pm y\\pmod q\n",
69 "\\end{cases}\\end{align*}\n",
70 "\n",
71 "One of those solutions is $a$ and another is $-a$, and Bob knows them. Alice is picking one of the $4$ possible roots at random (she chooses between $x$ and $-x$ and between $y$ and $-y$), so she has $50\\%$ chance of picking one that Bob already knows. This corresponds to Alice flipping a coin, and she wins if she picks $\\pm a$:\n",
72 "\n",
73 "(B2) If $z\\equiv\\pm a\\pmod n$, Bob declares to have lost. Otherwise, Bob claims to have won, and as proof he produces one prime factor of $n$ by computing $g=\\gcd(n,a+z)$. *(One can prove that in this situation $g$ is always one of the two prime factors of $n$.)*\n",
74 "\n",
75 "Since factoring a number without extra information is very hard, Alice will be convinced that she must have given Bob one of the square roots that he did not know, so she admits the loss.\n",
76 "\n",
77 "Now to the actual exercise:\n",
78 "\n",
79 "(a) Write the code for the functions A1, B1 and B2 as indicated in the cell below. The function A2 is already written.\n",
80 "\n",
81 "(b) Modify the functions B1, A2 and B2 to check that the opponent is not cheating. More precisely:\n",
82 "* In B1, Bob should check that $n$ is not a prime power. *(This is the only way Alice can try to cheat: if she sends Bob a number $n$ that is the product of more than two primes, than she has less than $50\\%$ chance of winning!)*\n",
83 "* In A2, Alice should check that $b$ is a square modulo $n$.\n",
84 "* In B2, Bob should check that $z^2\\equiv a^2\\pmod n$.\n",
85 "\n",
86 "In case cheating is detected, a message should be printed saying that the person is cheating."
87 ]
88 },
89 {
90 "cell_type": "code",
91 "execution_count": 1,
92 "metadata": {
93 "collapsed": true
94 },
95 "outputs": [
96 {
97 "ename": "IndentationError",
98 "evalue": "expected an indented block (<ipython-input-1-60f510bf175f>, line 7)",
99 "output_type": "error",
100 "traceback": [
101 "\u001b[1;36m File \u001b[1;32m\"<ipython-input-1-60f510bf175f>\"\u001b[1;36m, line \u001b[1;32m7\u001b[0m\n\u001b[1;33m def B1(n):\u001b[0m\n\u001b[1;37m ^\u001b[0m\n\u001b[1;31mIndentationError\u001b[0m\u001b[1;31m:\u001b[0m expected an indented block\n"
102 ]
103 }
104 ],
105 "source": [
106 "# Alice needs this to compute the square roots\n",
107 "from sage.rings.finite_rings.integer_mod import square_root_mod_prime\n",
108 "\n",
109 "def A1():\n",
110 " # This function must return two distinct primes and their product.\n",
111 " \n",
112 "def B1(n):\n",
113 " # This function must return a random integer a\n",
114 " # with 1<a<n and gcd(a,n)=1.\n",
115 "\n",
116 "def A2(b, p, q):\n",
117 " x = ZZ(square_root_mod_prime(Integers(p)(b), p))\n",
118 " y = ZZ(square_root_mod_prime(Integers(q)(b), q))\n",
119 " return crt(x, y, p, q)\n",
120 "\n",
121 "def B2(a, z, n):\n",
122 " # This function must print out one of two messages:\n",
123 " # \"Bob has lost\" if z is congruent to a or -a modulo n.\n",
124 " # \"Bob has won, proof: \" followed by a prime factor of n otherwise.\n",
125 " # In this case the prime must be calculated as explained above.\n",
126 "\n",
127 "\n",
128 "# This is how the game plays out:\n",
129 "p, q, n = A1()\n",
130 "print(\"Alice picked n =\", n)\n",
131 "print(\"[[ Alice's secret:\", p, q, \"]]\")\n",
132 "a = B1(n)\n",
133 "b = a^2 % n\n",
134 "print(\"Bob picked b =\", b)\n",
135 "print(\"[[ Bob's secret:\", a, \"]]\")\n",
136 "z = A2(b, p, q)\n",
137 "print(\"Alice picked z =\", z)\n",
138 "B2(a, z, n)"
139 ]
140 },
141 {
142 "cell_type": "markdown",
143 "metadata": {},
144 "source": [
145 "**Grading**\n",
146 "\n",
147 "This homework assignment is worth $20\\%$ of your final grade. Exercise 1 is worth 4 points (one for each part) and Exercise 2 is worth 12 points (8 points for part (a) and 4 points for part (b)), for a total of **16 points**."
148 ]
149 },
150 {
151 "cell_type": "code",
152 "execution_count": null,
153 "metadata": {},
154 "outputs": [],
155 "source": []
156 }
157 ],
158 "metadata": {
159 "kernelspec": {
160 "display_name": "SageMath 9.2",
161 "language": "sage",
162 "name": "sagemath"
163 },
164 "language_info": {
165 "codemirror_mode": {
166 "name": "ipython",
167 "version": 3
168 },
169 "file_extension": ".py",
170 "mimetype": "text/x-python",
171 "name": "python",
172 "nbconvert_exporter": "python",
173 "pygments_lexer": "ipython3",
174 "version": "3.8.5"
175 }
176 },
177 "nbformat": 4,
178 "nbformat_minor": 4
179}
diff --git a/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb b/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb
new file mode 100644
index 0000000..41ee2ea
--- /dev/null
+++ b/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb
@@ -0,0 +1,166 @@
1{
2 "cells": [
3 {
4 "cell_type": "markdown",
5 "metadata": {},
6 "source": [
7 "**Exercise 1**\n",
8 "\n",
9 "Use SageMath to solve the following problems:\n",
10 "\n",
11 "(a) Find the roots of the following polynomial over $\\mathbb Q$:\n",
12 "\\begin{align*}\n",
13 " 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]\n",
14 "\\end{align*}\n",
15 "\n",
16 "(b) Find the roots of the same polynomial $p$ over $\\mathbb R$ and over $\\mathbb C$.\n",
17 "\n",
18 "(c) Find the determinant, the trace and the characteristic polynomial of the following matrix:\n",
19 "\\begin{align*}\n",
20 "A=\\left(\\begin{array}{rrrr}\n",
21 "-1 & 1 & -1 & 0 \\\\\n",
22 "1 & \\frac{1}{2} & 1 & 0 \\\\\n",
23 "\\frac{1}{2} & -\\frac{1}{2} & -2 & 1 \\\\\n",
24 "0 & 0 & 1 & 1\n",
25 "\\end{array}\\right)\n",
26 "\\end{align*}\n",
27 "\n",
28 "(d) Find a solution to the linear system $A\\mathbf x =\\mathbf v$, where $A$ is the matrix above and $\\mathbf v=(1, 2, 3, 4)$.\n",
29 "\n",
30 "Write your code in the cell below."
31 ]
32 },
33 {
34 "cell_type": "code",
35 "execution_count": null,
36 "metadata": {},
37 "outputs": [],
38 "source": []
39 },
40 {
41 "cell_type": "markdown",
42 "metadata": {},
43 "source": [
44 "**Exercise 2**\n",
45 "\n",
46 "*(Yes, I know that the exercise is long to read, but it will not be so long to solve. It is a cool application of cryptography which, similarly to RSA, is based on the fact that factoring a number is hard.)*\n",
47 "\n",
48 "After exchanging messages with the RSA protocol seen in class, Alice and Bob decide to meet and play their favorite game: flip a coin. They like this game very much because it does not take much time to set it up and they have exactly the same chances of winning.\n",
49 "\n",
50 "Unfortunately, due to the COVID-19 pandemic they cannot meet in person, and they despite being good friends they don't trust each other enough to play this game via videocall. Luckily, Alice is an expert in cryptography and she knows how to play this game using the Chinese remainder theorem.\n",
51 "\n",
52 "The game plays as follows:\n",
53 "\n",
54 "(A1) Alice picks two large prime numbers $p$ and $q$, she computes $n=pq$ and sends $n$ to Bob, keeping $p$ and $q$ secret.\n",
55 "\n",
56 "(B1) Bob picks a random number $a$ with $1<a<n$ and $\\gcd(a,n)=1$, computes $b=a^2\\mod n$ and sends $b$ to Alice, keeping $a$ secret.\n",
57 "\n",
58 "(A2) Alice computes two numbers $x$ and $y$ such that $x^2\\equiv b\\pmod p$ and $y^2\\equiv b\\pmod q$ and she uses the Chinese remainder theorem to compute a number $z$ such that $z\\equiv x\\pmod p$ and $z\\equiv y\\pmod q$. Then she sends $z$ to Bob.\n",
59 "\n",
60 "Since $n$ is the product of two primes, there are $4$ possible square roots of $b$ modulo $n$, corresponding to the solutions of the four systems of congruences (one for each possible combination of $\\pm$)\n",
61 "\\begin{align*}\\begin{cases}\n",
62 "z\\equiv \\pm x\\pmod p\\\\\n",
63 "z \\equiv \\pm y\\pmod q\n",
64 "\\end{cases}\\end{align*}\n",
65 "\n",
66 "One of those solutions is $a$ and another is $-a$, and Bob knows them. Since Alice is picking one of the $4$ possible roots at random (she chooses between $x$ and $-x$ and between $y$ and $-y$), so she has $50\\%$ chance of picking one that Bob already knows. She will win if she picks $\\pm a$:\n",
67 "\n",
68 "(B2) If $z\\equiv\\pm a\\pmod n$, Bob declares to have lost. Otherwise, Bob claims to have won, and as proof he produces one prime factor of $n$ by computing $g=\\gcd(n,a+z)$. *(One can prove that in this situation $g$ is always one of the two prime factors of $n$)*\n",
69 "\n",
70 "Since factoring a number without extra information is very hard, Alice will be convinced that she must have given Bob one of the square roots that he did not know, so she admits the loss.\n",
71 "\n"
72 ]
73 },
74 {
75 "cell_type": "code",
76 "execution_count": 12,
77 "metadata": {},
78 "outputs": [
79 {
80 "name": "stdout",
81 "output_type": "stream",
82 "text": [
83 "Alice picked n = 239880868500983\n",
84 "(Alice's secret: 15489269 15486907 )\n",
85 "Bob picked b = 19945704365802\n",
86 "(Bob's secret: 3040890259756 )\n",
87 "Alice picked z = 3040890259756\n",
88 "Bob has lost\n"
89 ]
90 }
91 ],
92 "source": [
93 "# Alice needs this to compute the square roots\n",
94 "from sage.rings.finite_rings.integer_mod import square_root_mod_prime\n",
95 "\n",
96 "def A1():\n",
97 " # This function must return two distinct primes and their product\n",
98 " p, q = 0, 0\n",
99 " while p == q:\n",
100 " p = Primes()[10^6+randint(1,1000)]\n",
101 " q = Primes()[10^6+randint(1,1000)]\n",
102 " return p, q, p*q\n",
103 " \n",
104 "def B1(n):\n",
105 " a = 0\n",
106 " while gcd(a,n) != 1:\n",
107 " a = randint(2,n-1)\n",
108 " return a\n",
109 "\n",
110 "def A2(b, p, q):\n",
111 " x = ZZ(square_root_mod_prime(Integers(p)(b), p))\n",
112 " y = ZZ(square_root_mod_prime(Integers(q)(b), q))\n",
113 " return crt(x, y, p, q)\n",
114 "\n",
115 "def B2(a, z, n):\n",
116 " # This function must print out one of two messages:\n",
117 " # \"Bob has lost\" if z is congruent to a or -a modulo n\n",
118 " # \"Bob has won, proof: \" followed by a prime factor of n otherwise\n",
119 " if a%n == z%n or a%n == (-z)%n:\n",
120 " print(\"Bob has lost\")\n",
121 " else:\n",
122 " print(\"Bob has won, proof:\", gcd(n, a+z))\n",
123 "\n",
124 "# This is how the game plays:\n",
125 "p, q, n = A1() # p and q are secret to Alice\n",
126 "print(\"Alice picked n =\", n)\n",
127 "print(\"(Alice's secret:\", p, q, \")\")\n",
128 "a = B1(n) # a is secret to Bob\n",
129 "b = a^2 % n\n",
130 "print(\"Bob picked b =\", b)\n",
131 "print(\"(Bob's secret:\", a, \")\")\n",
132 "z = A2(b, p, q)\n",
133 "print(\"Alice picked z =\", z)\n",
134 "B2(a, z, n)"
135 ]
136 },
137 {
138 "cell_type": "code",
139 "execution_count": null,
140 "metadata": {},
141 "outputs": [],
142 "source": []
143 }
144 ],
145 "metadata": {
146 "kernelspec": {
147 "display_name": "SageMath 9.2",
148 "language": "sage",
149 "name": "sagemath"
150 },
151 "language_info": {
152 "codemirror_mode": {
153 "name": "ipython",
154 "version": 3
155 },
156 "file_extension": ".py",
157 "mimetype": "text/x-python",
158 "name": "python",
159 "nbconvert_exporter": "python",
160 "pygments_lexer": "ipython3",
161 "version": "3.8.5"
162 }
163 },
164 "nbformat": 4,
165 "nbformat_minor": 4
166}
diff --git a/src/Homework3/Homework3.aux b/src/Homework3/Homework3.aux
new file mode 100644
index 0000000..e781ffd
--- /dev/null
+++ b/src/Homework3/Homework3.aux
@@ -0,0 +1,20 @@
1\relax
2\providecommand\hyper@newdestlabel[2]{}
3\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
4\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
5\global\let\oldcontentsline\contentsline
6\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
7\global\let\oldnewlabel\newlabel
8\gdef\newlabel#1#2{\newlabelxx{#1}#2}
9\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
10\AtEndDocument{\ifx\hyper@anchor\@undefined
11\let\contentsline\oldcontentsline
12\let\newlabel\oldnewlabel
13\fi}
14\fi}
15\global\let\hyper@last\relax
16\gdef\HyperFirstAtBeginDocument#1{#1}
17\providecommand\HyField@AuxAddToFields[1]{}
18\providecommand\HyField@AuxAddToCoFields[2]{}
19\providecommand \oddpage@label [2]{}
20\gdef \@abspage@last{3}
diff --git a/src/Homework3/Homework3.ipynb b/src/Homework3/Homework3.ipynb
new file mode 100644
index 0000000..13bad44
--- /dev/null
+++ b/src/Homework3/Homework3.ipynb
@@ -0,0 +1,179 @@
1{
2 "cells": [
3 {
4 "cell_type": "markdown",
5 "metadata": {},
6 "source": [
7 "*For this exercise you should have received this text in .ipynb format. Complete the exercises by modifying this file, and submit the modified version*"
8 ]
9 },
10 {
11 "cell_type": "markdown",
12 "metadata": {},
13 "source": [
14 "**Exercise 1**\n",
15 "\n",
16 "Use SageMath to solve the following problems:\n",
17 "\n",
18 "(a) Find the roots of the following polynomial over $\\mathbb Q$:\n",
19 "\\begin{align*}\n",
20 " 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]\n",
21 "\\end{align*}\n",
22 "\n",
23 "(b) Find the roots of the same polynomial $p$ over $\\mathbb R$ and over $\\mathbb C$.\n",
24 "\n",
25 "(c) Find the determinant, the trace and the characteristic polynomial of the following matrix:\n",
26 "\\begin{align*}\n",
27 "A=\\left(\\begin{array}{rrrr}\n",
28 "-1 & 1 & -1 & 0 \\\\\n",
29 "1 & \\frac{1}{2} & 1 & 0 \\\\\n",
30 "\\frac{1}{2} & -\\frac{1}{2} & -2 & 1 \\\\\n",
31 "0 & 0 & 1 & 1\n",
32 "\\end{array}\\right)\n",
33 "\\end{align*}\n",
34 "\n",
35 "(d) Find a solution to the linear system $A\\mathbf x =\\mathbf v$, where $A$ is the matrix above and $\\mathbf v=(1, 2, 3, 4)$.\n",
36 "\n",
37 "Write your code in the cell below."
38 ]
39 },
40 {
41 "cell_type": "code",
42 "execution_count": null,
43 "metadata": {},
44 "outputs": [],
45 "source": []
46 },
47 {
48 "cell_type": "markdown",
49 "metadata": {},
50 "source": [
51 "**Exercise 2**\n",
52 "\n",
53 "After exchanging messages with the RSA protocol seen in class, Alice and Bob decide to meet and play their favorite game: flip a coin. They like this game very much because it does not take long to set it up and they have exactly the same chances of winning.\n",
54 "\n",
55 "Unfortunately, due to the COVID-19 pandemic they cannot meet in person, and despite being good friends they don't trust each other enough to play this game via Webex call. Luckily, Alice is an expert in cryptography and she knows how to play this game using the Chinese remainder theorem.\n",
56 "\n",
57 "The game plays out as follows:\n",
58 "\n",
59 "(A1) Alice picks two large prime numbers $p$ and $q$, she computes $n=pq$ and sends $n$ to Bob, keeping $p$ and $q$ secret.\n",
60 "\n",
61 "(B1) Bob picks a random number $a$ with $1<a<n$ and $\\gcd(a,n)=1$, computes $b=a^2\\mod n$ and sends $b$ to Alice, keeping $a$ secret.\n",
62 "\n",
63 "(A2) Alice computes two numbers $x$ and $y$ such that $x^2\\equiv b\\pmod p$ and $y^2\\equiv b\\pmod q$ and she uses the Chinese remainder theorem to compute a number $z$ such that $z\\equiv x\\pmod p$ and $z\\equiv y\\pmod q$, so that $z^2\\equiv b\\pmod n$. Then she sends $z$ to Bob.\n",
64 "\n",
65 "Since $n$ is the product of two primes, there are $4$ possible square roots of $b$ modulo $n$, corresponding to the solutions of the four systems of congruences (one for each possible combination of $\\pm$)\n",
66 "\\begin{align*}\\begin{cases}\n",
67 "z\\equiv \\pm x\\pmod p\\\\\n",
68 "z \\equiv \\pm y\\pmod q\n",
69 "\\end{cases}\\end{align*}\n",
70 "\n",
71 "One of those solutions is $a$ and another is $-a$, and Bob knows them. Alice is picking one of the $4$ possible roots at random (she chooses between $x$ and $-x$ and between $y$ and $-y$), so she has $50\\%$ chance of picking one that Bob already knows. This corresponds to Alice flipping a coin, and she wins if she picks $\\pm a$:\n",
72 "\n",
73 "(B2) If $z\\equiv\\pm a\\pmod n$, Bob declares to have lost. Otherwise, Bob claims to have won, and as proof he produces one prime factor of $n$ by computing $g=\\gcd(n,a+z)$. *(One can prove that in this situation $g$ is always one of the two prime factors of $n$.)*\n",
74 "\n",
75 "Since factoring a number without extra information is very hard, Alice will be convinced that she must have given Bob one of the square roots that he did not know, so she admits the loss.\n",
76 "\n",
77 "Now to the actual exercise:\n",
78 "\n",
79 "(a) Write the code for the functions A1, B1 and B2 as indicated in the cell below. The function A2 is already written.\n",
80 "\n",
81 "(b) Modify the functions B1, A2 and B2 to check that the opponent is not cheating. More precisely:\n",
82 "* In B1, Bob should check that $n$ is not a prime power. *(This is the only way Alice can try to cheat: if she sends Bob a number $n$ that is the product of more than two primes, than she has less than $50\\%$ chance of winning!)*\n",
83 "* In A2, Alice should check that $b$ is a square modulo $n$.\n",
84 "* In B2, Bob should check that $z^2\\equiv a^2\\pmod n$.\n",
85 "\n",
86 "In case cheating is detected, a message should be printed saying that the person is cheating."
87 ]
88 },
89 {
90 "cell_type": "code",
91 "execution_count": 1,
92 "metadata": {
93 "collapsed": true
94 },
95 "outputs": [
96 {
97 "ename": "IndentationError",
98 "evalue": "expected an indented block (<ipython-input-1-60f510bf175f>, line 7)",
99 "output_type": "error",
100 "traceback": [
101 "\u001b[1;36m File \u001b[1;32m\"<ipython-input-1-60f510bf175f>\"\u001b[1;36m, line \u001b[1;32m7\u001b[0m\n\u001b[1;33m def B1(n):\u001b[0m\n\u001b[1;37m ^\u001b[0m\n\u001b[1;31mIndentationError\u001b[0m\u001b[1;31m:\u001b[0m expected an indented block\n"
102 ]
103 }
104 ],
105 "source": [
106 "# Alice needs this to compute the square roots\n",
107 "from sage.rings.finite_rings.integer_mod import square_root_mod_prime\n",
108 "\n",
109 "def A1():\n",
110 " # This function must return two distinct primes and their product.\n",
111 " \n",
112 "def B1(n):\n",
113 " # This function must return a random integer a\n",
114 " # with 1<a<n and gcd(a,n)=1.\n",
115 "\n",
116 "def A2(b, p, q):\n",
117 " x = ZZ(square_root_mod_prime(Integers(p)(b), p))\n",
118 " y = ZZ(square_root_mod_prime(Integers(q)(b), q))\n",
119 " return crt(x, y, p, q)\n",
120 "\n",
121 "def B2(a, z, n):\n",
122 " # This function must print out one of two messages:\n",
123 " # \"Bob has lost\" if z is congruent to a or -a modulo n.\n",
124 " # \"Bob has won, proof: \" followed by a prime factor of n otherwise.\n",
125 " # In this case the prime must be calculated as explained above.\n",
126 "\n",
127 "\n",
128 "# This is how the game plays out:\n",
129 "p, q, n = A1()\n",
130 "print(\"Alice picked n =\", n)\n",
131 "print(\"[[ Alice's secret:\", p, q, \"]]\")\n",
132 "a = B1(n)\n",
133 "b = a^2 % n\n",
134 "print(\"Bob picked b =\", b)\n",
135 "print(\"[[ Bob's secret:\", a, \"]]\")\n",
136 "z = A2(b, p, q)\n",
137 "print(\"Alice picked z =\", z)\n",
138 "B2(a, z, n)"
139 ]
140 },
141 {
142 "cell_type": "markdown",
143 "metadata": {},
144 "source": [
145 "**Grading**\n",
146 "\n",
147 "This homework assignment is worth $20\\%$ of your final grade. Exercise 1 is worth 4 points (one for each part) and Exercise 2 is worth 12 points (8 points for part (a) and 4 points for part (b)), for a total of **16 points**."
148 ]
149 },
150 {
151 "cell_type": "code",
152 "execution_count": null,
153 "metadata": {},
154 "outputs": [],
155 "source": []
156 }
157 ],
158 "metadata": {
159 "kernelspec": {
160 "display_name": "SageMath 9.2",
161 "language": "sage",
162 "name": "sagemath"
163 },
164 "language_info": {
165 "codemirror_mode": {
166 "name": "ipython",
167 "version": 3
168 },
169 "file_extension": ".py",
170 "mimetype": "text/x-python",
171 "name": "python",
172 "nbconvert_exporter": "python",
173 "pygments_lexer": "ipython3",
174 "version": "3.8.5"
175 }
176 },
177 "nbformat": 4,
178 "nbformat_minor": 4
179}
diff --git a/src/Homework3/Homework3.log b/src/Homework3/Homework3.log
new file mode 100644
index 0000000..78a76b4
--- /dev/null
+++ b/src/Homework3/Homework3.log
@@ -0,0 +1,962 @@
1This is pdfTeX, Version 3.14159265-2.6-1.40.21 (TeX Live 2020/VoidLinux) (preloaded format=pdflatex 2021.4.20) 22 APR 2021 12:53
2entering extended mode
3 \write18 enabled.
4 %&-line parsing enabled.
5**Homework3.tex
6(./Homework3.tex
7LaTeX2e <2020-10-01> patch level 2
8L3 programming layer <2020-12-03> xparse <2020-03-03>
9(/usr/share/texmf-dist/tex/latex/base/article.cls
10Document Class: article 2020/04/10 v1.4m Standard LaTeX document class
11(/usr/share/texmf-dist/tex/latex/base/size11.clo
12File: size11.clo 2020/04/10 v1.4m Standard LaTeX file (size option)
13)
14\c@part=\count177
15\c@section=\count178
16\c@subsection=\count179
17\c@subsubsection=\count180
18\c@paragraph=\count181
19\c@subparagraph=\count182
20\c@figure=\count183
21\c@table=\count184
22\abovecaptionskip=\skip47
23\belowcaptionskip=\skip48
24\bibindent=\dimen138
25)
26(/usr/share/texmf-dist/tex/latex/tcolorbox/tcolorbox.sty
27Package: tcolorbox 2020/10/09 version 4.42 text color boxes
28
29(/usr/share/texmf-dist/tex/latex/pgf/basiclayer/pgf.sty
30(/usr/share/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty
31(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.tex
32\pgfutil@everybye=\toks15
33\pgfutil@tempdima=\dimen139
34\pgfutil@tempdimb=\dimen140
35
36(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfutil-common-lists.tex))
37(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def
38\pgfutil@abb=\box47
39)
40(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex
41(/usr/share/texmf-dist/tex/generic/pgf/pgf.revision.tex)
42Package: pgfrcs 2020/12/01 v3.1.7a (3.1.7a)
43))
44Package: pgf 2020/12/01 v3.1.7a (3.1.7a)
45
46(/usr/share/texmf-dist/tex/latex/pgf/basiclayer/pgfcore.sty
47(/usr/share/texmf-dist/tex/latex/graphics/graphicx.sty
48Package: graphicx 2020/09/09 v1.2b Enhanced LaTeX Graphics (DPC,SPQR)
49
50(/usr/share/texmf-dist/tex/latex/graphics/keyval.sty
51Package: keyval 2014/10/28 v1.15 key=value parser (DPC)
52\KV@toks@=\toks16
53)
54(/usr/share/texmf-dist/tex/latex/graphics/graphics.sty
55Package: graphics 2020/08/30 v1.4c Standard LaTeX Graphics (DPC,SPQR)
56
57(/usr/share/texmf-dist/tex/latex/graphics/trig.sty
58Package: trig 2016/01/03 v1.10 sin cos tan (DPC)
59)
60(/usr/share/texmf-dist/tex/latex/graphics-cfg/graphics.cfg
61File: graphics.cfg 2016/06/04 v1.11 sample graphics configuration
62)
63Package graphics Info: Driver file: pdftex.def on input line 105.
64
65(/usr/share/texmf-dist/tex/latex/graphics-def/pdftex.def
66File: pdftex.def 2020/10/05 v1.2a Graphics/color driver for pdftex
67))
68\Gin@req@height=\dimen141
69\Gin@req@width=\dimen142
70)
71(/usr/share/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty
72(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex
73Package: pgfsys 2020/12/01 v3.1.7a (3.1.7a)
74
75(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex
76\pgfkeys@pathtoks=\toks17
77\pgfkeys@temptoks=\toks18
78
79(/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfkeysfiltered.code.tex
80\pgfkeys@tmptoks=\toks19
81))
82\pgf@x=\dimen143
83\pgf@y=\dimen144
84\pgf@xa=\dimen145
85\pgf@ya=\dimen146
86\pgf@xb=\dimen147
87\pgf@yb=\dimen148
88\pgf@xc=\dimen149
89\pgf@yc=\dimen150
90\pgf@xd=\dimen151
91\pgf@yd=\dimen152
92\w@pgf@writea=\write3
93\r@pgf@reada=\read2
94\c@pgf@counta=\count185
95\c@pgf@countb=\count186
96\c@pgf@countc=\count187
97\c@pgf@countd=\count188
98\t@pgf@toka=\toks20
99\t@pgf@tokb=\toks21
100\t@pgf@tokc=\toks22
101\pgf@sys@id@count=\count189
102
103(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgf.cfg
104File: pgf.cfg 2020/12/01 v3.1.7a (3.1.7a)
105)
106Driver file for pgf: pgfsys-pdftex.def
107
108(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-pdftex.def
109File: pgfsys-pdftex.def 2020/12/01 v3.1.7a (3.1.7a)
110
111(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-common-pdf.def
112File: pgfsys-common-pdf.def 2020/12/01 v3.1.7a (3.1.7a)
113)))
114(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsyssoftpath.code.tex
115File: pgfsyssoftpath.code.tex 2020/12/01 v3.1.7a (3.1.7a)
116\pgfsyssoftpath@smallbuffer@items=\count190
117\pgfsyssoftpath@bigbuffer@items=\count191
118)
119(/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsysprotocol.code.tex
120File: pgfsysprotocol.code.tex 2020/12/01 v3.1.7a (3.1.7a)
121))
122(/usr/share/texmf-dist/tex/latex/xcolor/xcolor.sty
123Package: xcolor 2016/05/11 v2.12 LaTeX color extensions (UK)
124
125(/usr/share/texmf-dist/tex/latex/graphics-cfg/color.cfg
126File: color.cfg 2016/01/02 v1.6 sample color configuration
127)
128Package xcolor Info: Driver file: pdftex.def on input line 225.
129Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1348.
130Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1352.
131Package xcolor Info: Model `RGB' extended on input line 1364.
132Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1366.
133Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1367.
134Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1368.
135Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1369.
136Package xcolor Info: Model `Gray' substituted by `gray' on input line 1370.
137Package xcolor Info: Model `wave' substituted by `hsb' on input line 1371.
138)
139(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex
140Package: pgfcore 2020/12/01 v3.1.7a (3.1.7a)
141
142(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex
143(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex
144(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex)
145(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex
146\pgfmath@dimen=\dimen153
147\pgfmath@count=\count192
148\pgfmath@box=\box48
149\pgfmath@toks=\toks23
150\pgfmath@stack@operand=\toks24
151\pgfmath@stack@operation=\toks25
152)
153(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.tex
154(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic.code.tex)
155(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.trigonometric.code
156.tex)
157(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.random.code.tex)
158(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.comparison.code.te
159x) (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.code.tex)
160(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.round.code.tex)
161(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.misc.code.tex)
162(/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integerarithmetics
163.code.tex))) (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex
164\c@pgfmathroundto@lastzeros=\count193
165)) (/usr/share/texmf-dist/tex/generic/pgf/math/pgfint.code.tex)
166(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.code.tex
167File: pgfcorepoints.code.tex 2020/12/01 v3.1.7a (3.1.7a)
168\pgf@picminx=\dimen154
169\pgf@picmaxx=\dimen155
170\pgf@picminy=\dimen156
171\pgf@picmaxy=\dimen157
172\pgf@pathminx=\dimen158
173\pgf@pathmaxx=\dimen159
174\pgf@pathminy=\dimen160
175\pgf@pathmaxy=\dimen161
176\pgf@xx=\dimen162
177\pgf@xy=\dimen163
178\pgf@yx=\dimen164
179\pgf@yy=\dimen165
180\pgf@zx=\dimen166
181\pgf@zy=\dimen167
182)
183(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathconstruct.code.tex
184File: pgfcorepathconstruct.code.tex 2020/12/01 v3.1.7a (3.1.7a)
185\pgf@path@lastx=\dimen168
186\pgf@path@lasty=\dimen169
187) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage.code.tex
188File: pgfcorepathusage.code.tex 2020/12/01 v3.1.7a (3.1.7a)
189\pgf@shorten@end@additional=\dimen170
190\pgf@shorten@start@additional=\dimen171
191)
192(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.code.tex
193File: pgfcorescopes.code.tex 2020/12/01 v3.1.7a (3.1.7a)
194\pgfpic=\box49
195\pgf@hbox=\box50
196\pgf@layerbox@main=\box51
197\pgf@picture@serial@count=\count194
198)
199(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicstate.code.tex
200File: pgfcoregraphicstate.code.tex 2020/12/01 v3.1.7a (3.1.7a)
201\pgflinewidth=\dimen172
202)
203(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransformations.code.t
204ex
205File: pgfcoretransformations.code.tex 2020/12/01 v3.1.7a (3.1.7a)
206\pgf@pt@x=\dimen173
207\pgf@pt@y=\dimen174
208\pgf@pt@temp=\dimen175
209) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.code.tex
210File: pgfcorequick.code.tex 2020/12/01 v3.1.7a (3.1.7a)
211)
212(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreobjects.code.tex
213File: pgfcoreobjects.code.tex 2020/12/01 v3.1.7a (3.1.7a)
214)
215(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathprocessing.code.te
216x
217File: pgfcorepathprocessing.code.tex 2020/12/01 v3.1.7a (3.1.7a)
218) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.code.tex
219File: pgfcorearrows.code.tex 2020/12/01 v3.1.7a (3.1.7a)
220\pgfarrowsep=\dimen176
221)
222(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex
223File: pgfcoreshade.code.tex 2020/12/01 v3.1.7a (3.1.7a)
224\pgf@max=\dimen177
225\pgf@sys@shading@range@num=\count195
226\pgf@shadingcount=\count196
227)
228(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex
229File: pgfcoreimage.code.tex 2020/12/01 v3.1.7a (3.1.7a)
230
231(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.code.tex
232File: pgfcoreexternal.code.tex 2020/12/01 v3.1.7a (3.1.7a)
233\pgfexternal@startupbox=\box52
234))
235(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.code.tex
236File: pgfcorelayers.code.tex 2020/12/01 v3.1.7a (3.1.7a)
237)
238(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransparency.code.tex
239File: pgfcoretransparency.code.tex 2020/12/01 v3.1.7a (3.1.7a)
240) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepatterns.code.tex
241File: pgfcorepatterns.code.tex 2020/12/01 v3.1.7a (3.1.7a)
242)
243(/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorerdf.code.tex
244File: pgfcorerdf.code.tex 2020/12/01 v3.1.7a (3.1.7a)
245)))
246(/usr/share/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.code.tex
247File: pgfmoduleshapes.code.tex 2020/12/01 v3.1.7a (3.1.7a)
248\pgfnodeparttextbox=\box53
249)
250(/usr/share/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.tex
251File: pgfmoduleplot.code.tex 2020/12/01 v3.1.7a (3.1.7a)
252)
253(/usr/share/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-0-65.sty
254Package: pgfcomp-version-0-65 2020/12/01 v3.1.7a (3.1.7a)
255\pgf@nodesepstart=\dimen178
256\pgf@nodesepend=\dimen179
257)
258(/usr/share/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-1-18.sty
259Package: pgfcomp-version-1-18 2020/12/01 v3.1.7a (3.1.7a)
260))
261(/usr/share/texmf-dist/tex/latex/tools/verbatim.sty
262Package: verbatim 2020-07-07 v1.5u LaTeX2e package for verbatim enhancements
263\every@verbatim=\toks26
264\verbatim@line=\toks27
265\verbatim@in@stream=\read3
266)
267(/usr/share/texmf-dist/tex/latex/environ/environ.sty
268Package: environ 2014/05/04 v0.3 A new way to define environments
269
270(/usr/share/texmf-dist/tex/latex/trimspaces/trimspaces.sty
271Package: trimspaces 2009/09/17 v1.1 Trim spaces around a token list
272)
273\@envbody=\toks28
274)
275(/usr/share/texmf-dist/tex/latex/etoolbox/etoolbox.sty
276Package: etoolbox 2020/10/05 v2.5k e-TeX tools for LaTeX (JAW)
277\etb@tempcnta=\count197
278)
279\tcb@titlebox=\box54
280\tcb@upperbox=\box55
281\tcb@lowerbox=\box56
282\tcb@phantombox=\box57
283\c@tcbbreakpart=\count198
284\c@tcblayer=\count199
285\c@tcolorbox@number=\count266
286\tcb@temp=\box58
287\tcb@temp=\box59
288\tcb@temp=\box60
289\tcb@temp=\box61
290\tcb@out=\write4
291\tcb@record@out=\write5
292
293(/usr/share/texmf-dist/tex/latex/tcolorbox/tcbbreakable.code.tex
294Library (tcolorbox): 'tcbbreakable.code.tex' version '4.42'
295(/usr/share/texmf-dist/tex/generic/oberdiek/pdfcol.sty
296Package: pdfcol 2019/12/29 v1.6 Handle new color stacks for pdfTeX (HO)
297
298(/usr/share/texmf-dist/tex/generic/ltxcmds/ltxcmds.sty
299Package: ltxcmds 2020-05-10 v1.25 LaTeX kernel commands for general use (HO)
300)
301(/usr/share/texmf-dist/tex/generic/infwarerr/infwarerr.sty
302Package: infwarerr 2019/12/03 v1.5 Providing info/warning/error messages (HO)
303)
304(/usr/share/texmf-dist/tex/generic/iftex/iftex.sty
305Package: iftex 2020/03/06 v1.0d TeX engine tests
306))
307Package pdfcol Info: New color stack `tcb@breakable' = 1 on input line 23.
308\tcb@testbox=\box62
309\tcb@totalupperbox=\box63
310\tcb@totallowerbox=\box64
311))
312(/usr/share/texmf-dist/tex/latex/parskip/parskip.sty
313Package: parskip 2020-06-15 v2.0f non-zero parskip adjustments
314
315(/usr/share/texmf-dist/tex/latex/kvoptions/kvoptions.sty
316Package: kvoptions 2020-10-07 v3.14 Key value format for package options (HO)
317
318(/usr/share/texmf-dist/tex/generic/kvsetkeys/kvsetkeys.sty
319Package: kvsetkeys 2019/12/15 v1.18 Key value parser (HO)
320)))
321(/usr/share/texmf-dist/tex/latex/base/fontenc.sty
322Package: fontenc 2020/08/10 v2.0s Standard LaTeX package
323)
324(/usr/share/texmf-dist/tex/latex/psnfss/mathpazo.sty
325Package: mathpazo 2020/03/25 PSNFSS-v9.3 Palatino w/ Pazo Math (D.Puga, WaS)
326\symupright=\mathgroup4
327)
328(/usr/share/texmf-dist/tex/latex/caption/caption.sty
329Package: caption 2020/10/26 v3.5g Customizing captions (AR)
330
331(/usr/share/texmf-dist/tex/latex/caption/caption3.sty
332Package: caption3 2020/10/21 v2.2e caption3 kernel (AR)
333\captionmargin=\dimen180
334\captionmargin@=\dimen181
335\captionwidth=\dimen182
336\caption@tempdima=\dimen183
337\caption@indent=\dimen184
338\caption@parindent=\dimen185
339\caption@hangindent=\dimen186
340Package caption Info: Standard document class detected.
341)
342\c@caption@flags=\count267
343\c@continuedfloat=\count268
344)
345(/usr/share/texmf-dist/tex/latex/adjustbox/adjustbox.sty
346Package: adjustbox 2020/08/19 v1.3 Adjusting TeX boxes (trim, clip, ...)
347
348(/usr/share/texmf-dist/tex/latex/xkeyval/xkeyval.sty
349Package: xkeyval 2020/11/20 v2.8 package option processing (HA)
350
351(/usr/share/texmf-dist/tex/generic/xkeyval/xkeyval.tex
352(/usr/share/texmf-dist/tex/generic/xkeyval/xkvutils.tex
353\XKV@toks=\toks29
354\XKV@tempa@toks=\toks30
355)
356\XKV@depth=\count269
357File: xkeyval.tex 2014/12/03 v2.7a key=value parser (HA)
358))
359(/usr/share/texmf-dist/tex/latex/adjustbox/adjcalc.sty
360Package: adjcalc 2012/05/16 v1.1 Provides advanced setlength with multiple back
361-ends (calc, etex, pgfmath)
362)
363(/usr/share/texmf-dist/tex/latex/adjustbox/trimclip.sty
364Package: trimclip 2020/08/19 v1.2 Trim and clip general TeX material
365
366(/usr/share/texmf-dist/tex/latex/collectbox/collectbox.sty
367Package: collectbox 2012/05/17 v0.4b Collect macro arguments as boxes
368\collectedbox=\box65
369)
370\tc@llx=\dimen187
371\tc@lly=\dimen188
372\tc@urx=\dimen189
373\tc@ury=\dimen190
374Package trimclip Info: Using driver 'tc-pdftex.def'.
375
376(/usr/share/texmf-dist/tex/latex/adjustbox/tc-pdftex.def
377File: tc-pdftex.def 2019/01/04 v2.2 Clipping driver for pdftex
378))
379\adjbox@Width=\dimen191
380\adjbox@Height=\dimen192
381\adjbox@Depth=\dimen193
382\adjbox@Totalheight=\dimen194
383\adjbox@pwidth=\dimen195
384\adjbox@pheight=\dimen196
385\adjbox@pdepth=\dimen197
386\adjbox@ptotalheight=\dimen198
387
388(/usr/share/texmf-dist/tex/latex/ifoddpage/ifoddpage.sty
389Package: ifoddpage 2016/04/23 v1.1 Conditionals for odd/even page detection
390\c@checkoddpage=\count270
391)
392(/usr/share/texmf-dist/tex/latex/varwidth/varwidth.sty
393Package: varwidth 2009/03/30 ver 0.92; Variable-width minipages
394\@vwid@box=\box66
395\sift@deathcycles=\count271
396\@vwid@loff=\dimen199
397\@vwid@roff=\dimen256
398))
399(/usr/share/texmf-dist/tex/latex/float/float.sty
400Package: float 2001/11/08 v1.3d Float enhancements (AL)
401\c@float@type=\count272
402\float@exts=\toks31
403\float@box=\box67
404\@float@everytoks=\toks32
405\@floatcapt=\box68
406)
407(/usr/share/texmf-dist/tex/latex/tools/enumerate.sty
408Package: enumerate 2015/07/23 v3.00 enumerate extensions (DPC)
409\@enLab=\toks33
410)
411(/usr/share/texmf-dist/tex/latex/geometry/geometry.sty
412Package: geometry 2020/01/02 v5.9 Page Geometry
413
414(/usr/share/texmf-dist/tex/generic/iftex/ifvtex.sty
415Package: ifvtex 2019/10/25 v1.7 ifvtex legacy package. Use iftex instead.
416)
417\Gm@cnth=\count273
418\Gm@cntv=\count274
419\c@Gm@tempcnt=\count275
420\Gm@bindingoffset=\dimen257
421\Gm@wd@mp=\dimen258
422\Gm@odd@mp=\dimen259
423\Gm@even@mp=\dimen260
424\Gm@layoutwidth=\dimen261
425\Gm@layoutheight=\dimen262
426\Gm@layouthoffset=\dimen263
427\Gm@layoutvoffset=\dimen264
428\Gm@dimlist=\toks34
429)
430(/usr/share/texmf-dist/tex/latex/amsmath/amsmath.sty
431Package: amsmath 2020/09/23 v2.17i AMS math features
432\@mathmargin=\skip49
433
434For additional information on amsmath, use the `?' option.
435(/usr/share/texmf-dist/tex/latex/amsmath/amstext.sty
436Package: amstext 2000/06/29 v2.01 AMS text
437
438(/usr/share/texmf-dist/tex/latex/amsmath/amsgen.sty
439File: amsgen.sty 1999/11/30 v2.0 generic functions
440\@emptytoks=\toks35
441\ex@=\dimen265
442))
443(/usr/share/texmf-dist/tex/latex/amsmath/amsbsy.sty
444Package: amsbsy 1999/11/29 v1.2d Bold Symbols
445\pmbraise@=\dimen266
446)
447(/usr/share/texmf-dist/tex/latex/amsmath/amsopn.sty
448Package: amsopn 2016/03/08 v2.02 operator names
449)
450\inf@bad=\count276
451LaTeX Info: Redefining \frac on input line 234.
452\uproot@=\count277
453\leftroot@=\count278
454LaTeX Info: Redefining \overline on input line 399.
455\classnum@=\count279
456\DOTSCASE@=\count280
457LaTeX Info: Redefining \ldots on input line 496.
458LaTeX Info: Redefining \dots on input line 499.
459LaTeX Info: Redefining \cdots on input line 620.
460\Mathstrutbox@=\box69
461\strutbox@=\box70
462\big@size=\dimen267
463LaTeX Font Info: Redeclaring font encoding OML on input line 743.
464LaTeX Font Info: Redeclaring font encoding OMS on input line 744.
465\macc@depth=\count281
466\c@MaxMatrixCols=\count282
467\dotsspace@=\muskip16
468\c@parentequation=\count283
469\dspbrk@lvl=\count284
470\tag@help=\toks36
471\row@=\count285
472\column@=\count286
473\maxfields@=\count287
474\andhelp@=\toks37
475\eqnshift@=\dimen268
476\alignsep@=\dimen269
477\tagshift@=\dimen270
478\tagwidth@=\dimen271
479\totwidth@=\dimen272
480\lineht@=\dimen273
481\@envbody=\toks38
482\multlinegap=\skip50
483\multlinetaggap=\skip51
484\mathdisplay@stack=\toks39
485LaTeX Info: Redefining \[ on input line 2923.
486LaTeX Info: Redefining \] on input line 2924.
487)
488(/usr/share/texmf-dist/tex/latex/amsfonts/amssymb.sty
489Package: amssymb 2013/01/14 v3.01 AMS font symbols
490
491(/usr/share/texmf-dist/tex/latex/amsfonts/amsfonts.sty
492Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support
493\symAMSa=\mathgroup5
494\symAMSb=\mathgroup6
495LaTeX Font Info: Redeclaring math symbol \hbar on input line 98.
496LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold'
497(Font) U/euf/m/n --> U/euf/b/n on input line 106.
498))
499(/usr/share/texmf-dist/tex/latex/base/textcomp.sty
500Package: textcomp 2020/02/02 v2.0n Standard LaTeX package
501)
502(/usr/share/texmf-dist/tex/latex/upquote/upquote.sty
503Package: upquote 2012/04/19 v1.3 upright-quote and grave-accent glyphs in verba
504tim
505)
506(/usr/share/texmf-dist/tex/latex/eurosym/eurosym.sty
507Package: eurosym 1998/08/06 v1.1 European currency symbol ``Euro''
508\@eurobox=\box71
509)
510(/usr/share/texmf-dist/tex/latex/ucs/ucs.sty
511Package: ucs 2013/05/11 v2.2 UCS: Unicode input support
512
513(/usr/share/texmf-dist/tex/latex/ucs/data/uni-global.def
514File: uni-global.def 2013/05/13 UCS: Unicode global data
515)
516\uc@secondtry=\count288
517\uc@combtoks=\toks40
518\uc@combtoksb=\toks41
519\uc@temptokena=\toks42
520)
521(/usr/share/texmf-dist/tex/latex/fancyvrb/fancyvrb.sty
522Package: fancyvrb 2020/05/03 v3.6 verbatim text (tvz,hv)
523\FV@CodeLineNo=\count289
524\FV@InFile=\read4
525\FV@TabBox=\box72
526\c@FancyVerbLine=\count290
527\FV@StepNumber=\count291
528\FV@OutFile=\write6
529)
530(/usr/share/texmf-dist/tex/latex/grffile/grffile.sty
531Package: grffile 2019/11/11 v2.1 Extended file name support for graphics (legac
532y)
533Package grffile Info: This package is an empty stub for compatibility on input
534line 40.
535)
536(/usr/share/texmf-dist/tex/latex/hyperref/hyperref.sty
537Package: hyperref 2020-05-15 v7.00e Hypertext links for LaTeX
538
539(/usr/share/texmf-dist/tex/generic/pdftexcmds/pdftexcmds.sty
540Package: pdftexcmds 2020-06-27 v0.33 Utility functions of pdfTeX for LuaTeX (HO
541)
542Package pdftexcmds Info: \pdf@primitive is available.
543Package pdftexcmds Info: \pdf@ifprimitive is available.
544Package pdftexcmds Info: \pdfdraftmode found.
545)
546(/usr/share/texmf-dist/tex/generic/kvdefinekeys/kvdefinekeys.sty
547Package: kvdefinekeys 2019-12-19 v1.6 Define keys (HO)
548)
549(/usr/share/texmf-dist/tex/generic/pdfescape/pdfescape.sty
550Package: pdfescape 2019/12/09 v1.15 Implements pdfTeX's escape features (HO)
551)
552(/usr/share/texmf-dist/tex/latex/hycolor/hycolor.sty
553Package: hycolor 2020-01-27 v1.10 Color options for hyperref/bookmark (HO)
554)
555(/usr/share/texmf-dist/tex/latex/letltxmacro/letltxmacro.sty
556Package: letltxmacro 2019/12/03 v1.6 Let assignment for LaTeX macros (HO)
557)
558(/usr/share/texmf-dist/tex/latex/auxhook/auxhook.sty
559Package: auxhook 2019-12-17 v1.6 Hooks for auxiliary files (HO)
560)
561\@linkdim=\dimen274
562\Hy@linkcounter=\count292
563\Hy@pagecounter=\count293
564
565(/usr/share/texmf-dist/tex/latex/hyperref/pd1enc.def
566File: pd1enc.def 2020-05-15 v7.00e Hyperref: PDFDocEncoding definition (HO)
567Now handling font encoding PD1 ...
568... no UTF-8 mapping file for font encoding PD1
569)
570(/usr/share/texmf-dist/tex/generic/intcalc/intcalc.sty
571Package: intcalc 2019/12/15 v1.3 Expandable calculations with integers (HO)
572)
573(/usr/share/texmf-dist/tex/generic/etexcmds/etexcmds.sty
574Package: etexcmds 2019/12/15 v1.7 Avoid name clashes with e-TeX commands (HO)
575)
576\Hy@SavedSpaceFactor=\count294
577Package hyperref Info: Hyper figures OFF on input line 4464.
578Package hyperref Info: Link nesting OFF on input line 4469.
579Package hyperref Info: Hyper index ON on input line 4472.
580Package hyperref Info: Plain pages OFF on input line 4479.
581Package hyperref Info: Backreferencing OFF on input line 4484.
582Package hyperref Info: Implicit mode ON; LaTeX internals redefined.
583Package hyperref Info: Bookmarks ON on input line 4717.
584\c@Hy@tempcnt=\count295
585
586(/usr/share/texmf-dist/tex/latex/url/url.sty
587\Urlmuskip=\muskip17
588Package: url 2013/09/16 ver 3.4 Verb mode for urls, etc.
589)
590LaTeX Info: Redefining \url on input line 5076.
591\XeTeXLinkMargin=\dimen275
592
593(/usr/share/texmf-dist/tex/generic/bitset/bitset.sty
594Package: bitset 2019/12/09 v1.3 Handle bit-vector datatype (HO)
595
596(/usr/share/texmf-dist/tex/generic/bigintcalc/bigintcalc.sty
597Package: bigintcalc 2019/12/15 v1.5 Expandable calculations on big integers (HO
598)
599))
600\Fld@menulength=\count296
601\Field@Width=\dimen276
602\Fld@charsize=\dimen277
603Package hyperref Info: Hyper figures OFF on input line 6347.
604Package hyperref Info: Link nesting OFF on input line 6352.
605Package hyperref Info: Hyper index ON on input line 6355.
606Package hyperref Info: backreferencing OFF on input line 6362.
607Package hyperref Info: Link coloring OFF on input line 6367.
608Package hyperref Info: Link coloring with OCG OFF on input line 6372.
609Package hyperref Info: PDF/A mode OFF on input line 6377.
610LaTeX Info: Redefining \ref on input line 6417.
611LaTeX Info: Redefining \pageref on input line 6421.
612
613(/usr/share/texmf-dist/tex/latex/base/atbegshi-ltx.sty
614Package: atbegshi-ltx 2020/08/17 v1.0a Emulation of the original atbegshi packa
615ge
616with kernel methods
617)
618\Hy@abspage=\count297
619\c@Item=\count298
620\c@Hfootnote=\count299
621)
622Package hyperref Info: Driver (autodetected): hpdftex.
623
624(/usr/share/texmf-dist/tex/latex/hyperref/hpdftex.def
625File: hpdftex.def 2020-05-15 v7.00e Hyperref driver for pdfTeX
626
627(/usr/share/texmf-dist/tex/latex/base/atveryend-ltx.sty
628Package: atveryend-ltx 2020/08/19 v1.0a Emulation of the original atvery packag
629e
630with kernel methods
631)
632\Fld@listcount=\count300
633\c@bookmark@seq@number=\count301
634
635(/usr/share/texmf-dist/tex/latex/rerunfilecheck/rerunfilecheck.sty
636Package: rerunfilecheck 2019/12/05 v1.9 Rerun checks for auxiliary files (HO)
637
638(/usr/share/texmf-dist/tex/generic/uniquecounter/uniquecounter.sty
639Package: uniquecounter 2019/12/15 v1.4 Provide unlimited unique counter (HO)
640)
641Package uniquecounter Info: New unique counter `rerunfilecheck' on input line 2
64286.
643)
644\Hy@SectionHShift=\skip52
645)
646(/usr/share/texmf-dist/tex/latex/titling/titling.sty
647Package: titling 2009/09/04 v2.1d maketitle typesetting
648\thanksmarkwidth=\skip53
649\thanksmargin=\skip54
650\droptitle=\skip55
651)
652(/usr/share/texmf-dist/tex/latex/tools/longtable.sty
653Package: longtable 2020/01/07 v4.13 Multi-page Table package (DPC)
654\LTleft=\skip56
655\LTright=\skip57
656\LTpre=\skip58
657\LTpost=\skip59
658\LTchunksize=\count302
659\LTcapwidth=\dimen278
660\LT@head=\box73
661\LT@firsthead=\box74
662\LT@foot=\box75
663\LT@lastfoot=\box76
664\LT@cols=\count303
665\LT@rows=\count304
666\c@LT@tables=\count305
667\c@LT@chunks=\count306
668\LT@p@ftn=\toks43
669)
670(/usr/share/texmf-dist/tex/latex/booktabs/booktabs.sty
671Package: booktabs 2020/01/12 v1.61803398 Publication quality tables
672\heavyrulewidth=\dimen279
673\lightrulewidth=\dimen280
674\cmidrulewidth=\dimen281
675\belowrulesep=\dimen282
676\belowbottomsep=\dimen283
677\aboverulesep=\dimen284
678\abovetopsep=\dimen285
679\cmidrulesep=\dimen286
680\cmidrulekern=\dimen287
681\defaultaddspace=\dimen288
682\@cmidla=\count307
683\@cmidlb=\count308
684\@aboverulesep=\dimen289
685\@belowrulesep=\dimen290
686\@thisruleclass=\count309
687\@lastruleclass=\count310
688\@thisrulewidth=\dimen291
689)
690(/usr/share/texmf-dist/tex/latex/enumitem/enumitem.sty
691Package: enumitem 2019/06/20 v3.9 Customized lists
692\labelindent=\skip60
693\enit@outerparindent=\dimen292
694\enit@toks=\toks44
695\enit@inbox=\box77
696\enit@count@id=\count311
697\enitdp@description=\count312
698)
699(/usr/share/texmf-dist/tex/generic/ulem/ulem.sty
700\UL@box=\box78
701\UL@hyphenbox=\box79
702\UL@skip=\skip61
703\UL@hook=\toks45
704\UL@height=\dimen293
705\UL@pe=\count313
706\UL@pixel=\dimen294
707\ULC@box=\box80
708Package: ulem 2019/11/18
709\ULdepth=\dimen295
710)
711(/usr/share/texmf-dist/tex/latex/jknapltx/mathrsfs.sty
712Package: mathrsfs 1996/01/01 Math RSFS package v1.0 (jk)
713\symrsfs=\mathgroup7
714)
715\Wrappedcontinuationbox=\box81
716\Wrappedvisiblespacebox=\box82
717Package hyperref Info: Option `breaklinks' set `true' on input line 360.
718Package hyperref Info: Option `colorlinks' set `true' on input line 360.
719LaTeX Font Info: Trying to load font information for T1+ppl on input line 36
7207.
721
722(/usr/share/texmf-dist/tex/latex/psnfss/t1ppl.fd
723File: t1ppl.fd 2001/06/04 font definitions for T1/ppl.
724)
725(/usr/share/texmf-dist/tex/latex/l3backend/l3backend-pdftex.def
726File: l3backend-pdftex.def 2020-09-24 L3 backend support: PDF output (pdfTeX)
727\l__kernel_color_stack_int=\count314
728\l__pdf_internal_box=\box83
729)
730(./Homework3.aux)
731\openout1 = `Homework3.aux'.
732
733LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 367.
734LaTeX Font Info: ... okay on input line 367.
735LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 367.
736LaTeX Font Info: ... okay on input line 367.
737LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 367.
738LaTeX Font Info: ... okay on input line 367.
739LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 367.
740LaTeX Font Info: ... okay on input line 367.
741LaTeX Font Info: Checking defaults for TS1/cmr/m/n on input line 367.
742LaTeX Font Info: ... okay on input line 367.
743LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 367.
744LaTeX Font Info: ... okay on input line 367.
745LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 367.
746LaTeX Font Info: ... okay on input line 367.
747LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 367.
748LaTeX Font Info: ... okay on input line 367.
749 (/usr/share/texmf-dist/tex/context/base/mkii/supp-pdf.mkii
750[Loading MPS to PDF converter (version 2006.09.02).]
751\scratchcounter=\count315
752\scratchdimen=\dimen296
753\scratchbox=\box84
754\nofMPsegments=\count316
755\nofMParguments=\count317
756\everyMPshowfont=\toks46
757\MPscratchCnt=\count318
758\MPscratchDim=\dimen297
759\MPnumerator=\count319
760\makeMPintoPDFobject=\count320
761\everyMPtoPDFconversion=\toks47
762) (/usr/share/texmf-dist/tex/latex/epstopdf-pkg/epstopdf-base.sty
763Package: epstopdf-base 2020-01-24 v2.11 Base part for package epstopdf
764Package epstopdf-base Info: Redefining graphics rule for `.eps' on input line 4
76585.
766
767(/usr/share/texmf-dist/tex/latex/latexconfig/epstopdf-sys.cfg
768File: epstopdf-sys.cfg 2010/07/13 v1.3 Configuration of (r)epstopdf for TeX Liv
769e
770))
771Package caption Info: Begin \AtBeginDocument code.
772Package caption Info: float package is loaded.
773Package caption Info: hyperref package is loaded.
774Package caption Info: longtable package is loaded.
775
776(/usr/share/texmf-dist/tex/latex/caption/ltcaption.sty
777Package: ltcaption 2020/05/30 v1.4b longtable captions (AR)
778)
779Package caption Info: End \AtBeginDocument code.
780
781*geometry* driver: auto-detecting
782*geometry* detected driver: pdftex
783*geometry* verbose mode - [ preamble ] result:
784* driver: pdftex
785* paper: <default>
786* layout: <same size as paper>
787* layoutoffset:(h,v)=(0.0pt,0.0pt)
788* modes:
789* h-part:(L,W,R)=(72.26999pt, 469.75502pt, 72.26999pt)
790* v-part:(T,H,B)=(72.26999pt, 650.43001pt, 72.26999pt)
791* \paperwidth=614.295pt
792* \paperheight=794.96999pt
793* \textwidth=469.75502pt
794* \textheight=650.43001pt
795* \oddsidemargin=0.0pt
796* \evensidemargin=0.0pt
797* \topmargin=-37.0pt
798* \headheight=12.0pt
799* \headsep=25.0pt
800* \topskip=11.0pt
801* \footskip=30.0pt
802* \marginparwidth=59.0pt
803* \marginparsep=10.0pt
804* \columnsep=10.0pt
805* \skip\footins=10.0pt plus 4.0pt minus 2.0pt
806* \hoffset=0.0pt
807* \voffset=0.0pt
808* \mag=1000
809* \@twocolumnfalse
810* \@twosidefalse
811* \@mparswitchfalse
812* \@reversemarginfalse
813* (1in=72.27pt=25.4mm, 1cm=28.453pt)
814
815(/usr/share/texmf-dist/tex/latex/ucs/ucsencs.def
816File: ucsencs.def 2011/01/21 Fixes to fontencodings LGR, T3
817)
818Package hyperref Info: Link coloring ON on input line 367.
819
820(/usr/share/texmf-dist/tex/latex/hyperref/nameref.sty
821Package: nameref 2019/09/16 v2.46 Cross-referencing by name of section
822
823(/usr/share/texmf-dist/tex/latex/refcount/refcount.sty
824Package: refcount 2019/12/15 v3.6 Data extraction from label references (HO)
825)
826(/usr/share/texmf-dist/tex/generic/gettitlestring/gettitlestring.sty
827Package: gettitlestring 2019/12/15 v1.6 Cleanup title references (HO)
828)
829\c@section@level=\count321
830)
831LaTeX Info: Redefining \ref on input line 367.
832LaTeX Info: Redefining \pageref on input line 367.
833LaTeX Info: Redefining \nameref on input line 367.
834
835(./Homework3.out) (./Homework3.out)
836\@outlinefile=\write7
837\openout7 = `Homework3.out'.
838
839LaTeX Font Info: Trying to load font information for OT1+ppl on input line 3
84069.
841
842(/usr/share/texmf-dist/tex/latex/psnfss/ot1ppl.fd
843File: ot1ppl.fd 2001/06/04 font definitions for OT1/ppl.
844)
845LaTeX Font Info: Trying to load font information for OML+zplm on input line
846369.
847
848(/usr/share/texmf-dist/tex/latex/psnfss/omlzplm.fd
849File: omlzplm.fd 2002/09/08 Fontinst v1.914 font definitions for OML/zplm.
850)
851LaTeX Font Info: Trying to load font information for OMS+zplm on input line
852369.
853
854(/usr/share/texmf-dist/tex/latex/psnfss/omszplm.fd
855File: omszplm.fd 2002/09/08 Fontinst v1.914 font definitions for OMS/zplm.
856)
857LaTeX Font Info: Trying to load font information for OMX+zplm on input line
858369.
859
860(/usr/share/texmf-dist/tex/latex/psnfss/omxzplm.fd
861File: omxzplm.fd 2002/09/08 Fontinst v1.914 font definitions for OMX/zplm.
862)
863LaTeX Font Info: Trying to load font information for OT1+zplm on input line
864369.
865
866(/usr/share/texmf-dist/tex/latex/psnfss/ot1zplm.fd
867File: ot1zplm.fd 2002/09/08 Fontinst v1.914 font definitions for OT1/zplm.
868)
869LaTeX Font Info: Font shape `U/msa/m/n' will be
870(Font) scaled to size 12.50409pt on input line 369.
871LaTeX Font Info: Font shape `U/msa/m/n' will be
872(Font) scaled to size 9.37807pt on input line 369.
873LaTeX Font Info: Font shape `U/msa/m/n' will be
874(Font) scaled to size 7.29405pt on input line 369.
875LaTeX Font Info: Font shape `U/msb/m/n' will be
876(Font) scaled to size 12.50409pt on input line 369.
877LaTeX Font Info: Font shape `U/msb/m/n' will be
878(Font) scaled to size 9.37807pt on input line 369.
879LaTeX Font Info: Font shape `U/msb/m/n' will be
880(Font) scaled to size 7.29405pt on input line 369.
881LaTeX Font Info: Trying to load font information for U+rsfs on input line 36
8829.
883
884(/usr/share/texmf-dist/tex/latex/jknapltx/ursfs.fd
885File: ursfs.fd 1998/03/24 rsfs font definition file (jk)
886)
887
888LaTeX Warning: No \author given.
889
890LaTeX Font Info: Font shape `U/msa/m/n' will be
891(Font) scaled to size 11.40997pt on input line 387.
892LaTeX Font Info: Font shape `U/msa/m/n' will be
893(Font) scaled to size 8.33606pt on input line 387.
894LaTeX Font Info: Font shape `U/msa/m/n' will be
895(Font) scaled to size 6.25204pt on input line 387.
896LaTeX Font Info: Font shape `U/msb/m/n' will be
897(Font) scaled to size 11.40997pt on input line 387.
898LaTeX Font Info: Font shape `U/msb/m/n' will be
899(Font) scaled to size 8.33606pt on input line 387.
900LaTeX Font Info: Font shape `U/msb/m/n' will be
901(Font) scaled to size 6.25204pt on input line 387.
902LaTeX Font Info: Trying to load font information for U+fplmbb on input line
903387.
904(/usr/share/texmf-dist/tex/latex/psnfss/ufplmbb.fd
905File: ufplmbb.fd 2003/10/30 Fontinst v1.914 font definitions for U/fplmbb.
906)
907LaTeX Font Info: Trying to load font information for T1+cmtt on input line 4
90812.
909
910(/usr/share/texmf-dist/tex/latex/base/t1cmtt.fd
911File: t1cmtt.fd 2019/12/16 v2.5j Standard LaTeX font definitions
912)
913LaTeX Font Info: Font shape `U/msa/m/n' will be
914(Font) scaled to size 5.21004pt on input line 413.
915LaTeX Font Info: Font shape `U/msb/m/n' will be
916(Font) scaled to size 5.21004pt on input line 413.
917 [1
918
919{/usr/share/texmf-var/fonts/map/pdftex/updmap/pdftex.map}]
920LaTeX Font Info: Trying to load font information for TS1+ppl on input line 4
92187.
922
923(/usr/share/texmf-dist/tex/latex/psnfss/ts1ppl.fd
924File: ts1ppl.fd 2001/06/04 font definitions for TS1/ppl.
925) [2]
926LaTeX Font Info: Font shape `T1/cmtt/bx/n' in size <10.95> not available
927(Font) Font shape `T1/cmtt/m/n' tried instead on input line 507.
928LaTeX Font Info: Trying to load font information for TS1+cmtt on input line
929531.
930
931(/usr/share/texmf-dist/tex/latex/base/ts1cmtt.fd
932File: ts1cmtt.fd 2019/12/16 v2.5j Standard LaTeX font definitions
933) [3] (./Homework3.aux)
934Package rerunfilecheck Info: File `Homework3.out' has not changed.
935(rerunfilecheck) Checksum: D41D8CD98F00B204E9800998ECF8427E;0.
936 )
937Here is how much of TeX's memory you used:
938 21220 strings out of 479383
939 386765 string characters out of 5875798
940 724227 words of memory out of 5000000
941 37854 multiletter control sequences out of 15000+600000
942 436783 words of font info for 121 fonts, out of 8000000 for 9000
943 1141 hyphenation exceptions out of 8191
944 107i,14n,111p,502b,594s stack positions out of 5000i,500n,10000p,200000b,80000s
945{/usr/share/texmf-dist/fonts/enc/dvips/cm-super/cm-super-ts1.enc}{/usr/share/
946texmf-dist/fonts/enc/dvips/cm-super/cm-super-t1.enc}{/usr/share/texmf-dist/font
947s/enc/dvips/base/8r.enc}</usr/share/texmf-dist/fonts/type1/public/amsfonts/cm/c
948mex10.pfb></usr/share/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi10.pfb></us
949r/share/texmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb></usr/share/texmf-d
950ist/fonts/type1/public/amsfonts/cm/cmsy10.pfb></usr/share/texmf-dist/fonts/type
9511/public/mathpazo/fplmbb.pfb></usr/share/texmf-dist/fonts/type1/public/cm-super
952/sfit1095.pfb></usr/share/texmf-dist/fonts/type1/public/cm-super/sftt1095.pfb><
953/usr/share/texmf-dist/fonts/type1/urw/palatino/uplb8a.pfb></usr/share/texmf-dis
954t/fonts/type1/urw/palatino/uplr8a.pfb></usr/share/texmf-dist/fonts/type1/urw/pa
955latino/uplri8a.pfb>
956Output written on Homework3.pdf (3 pages, 146471 bytes).
957PDF statistics:
958 77 PDF objects out of 1000 (max. 8388607)
959 61 compressed objects within 1 object stream
960 10 named destinations out of 1000 (max. 500000)
961 13 words of extra memory for PDF output out of 10000 (max. 10000000)
962
diff --git a/src/Homework3/Homework3.out b/src/Homework3/Homework3.out
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/Homework3/Homework3.out
diff --git a/src/Homework3/Homework3.pdf b/src/Homework3/Homework3.pdf
new file mode 100644
index 0000000..13d55cf
--- /dev/null
+++ b/src/Homework3/Homework3.pdf
Binary files differ
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