{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Fall 2017-2018

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recitation 8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We have reviewed some properties of prime numbers and used them for primality testing. We revied the Diffie-Hellman protocol for finding a shared secret key and also tried to crack it. At the second part of the recitation, we discussed OOP and special methods that allow us to define operators in Python.\n", "\n", "#### Takeaways:\n", "- The probabilistic function is_prime, that uses Fermat's primality test, can be used to detect primes quickly and efficiently, but has a (very small) probability of error. Its time complexity is $O(n^3)$, where $n$ is the number of bits of the input.\n", "- The DH protocol relies on two main principles: the following equality $(g^{a}\\mod p)^b \\mod p = g^{ab} \\mod p $ and the (believed) hardness of the discrete log problem (given $g,p$, and $x = g^{a} \\mod p$ finding $a$ is hard). Make sure you understand the details of the protocol.\n", "- OOP allows us to create classes at will and to define complex objects. Remember that the most important thing is to find a good inner representation of the object so that you will have an easy time working with it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Primes and Diffie-Hellman" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Primality test using Ferma's witness\n", "\n", "Fermat's little theorem: if $p$ is prime and $1 < a < p$, then $a^{p-1} (\\textrm{mod}\\ p) \\equiv 1$\n", "\n", "Equivalently: if $m$ is not a prime then there exists $1 < a < m$ such that $a^{m-1} (\\textrm{mod}\\ m) \\not\\equiv 1$. Such a number $a$ is called a witness to the fact that $m$ is not prime.\n", "\n", "We can use Fermat's little theorem in order test whether a given number is prime. Note that if the number has $n$ bits than testing all possible $a$-s will require $O(2^n)$ iterations (a lot!).\n", "\n", "Instead, we will try 100 random $a$-s in the range and see if one works as a witness." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "def is_prime(m, show_witness=False):\n", "\n", " \"\"\" probabilistic test for m's compositeness \"\"\"\n", "\n", " for i in range(0,100):\n", " a = random.randint(1,m-1) # a is a random integer in [1..m-1]\n", " if pow(a,m-1,m) != 1:\n", " if show_witness: # caller wishes to see a witness\n", " print(m,\"is composite\",\"\\n\",a,\"is a witness, i=\",i+1)\n", " return False\n", "\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For $a,b,c$ of at most $n$ bits each, time complexity of modpower is $O(n^3)$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def modpower(a, b, c):\n", " \"\"\" computes a**b modulo c, using iterated squaring \"\"\"\n", " result = 1\n", " while b>0: # while b is nonzero\n", " if b%2 == 1: # b is odd\n", " result = (result * a) % c\n", " a = (a*a) % c\n", " b = b//2\n", " return result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The probability for error:\n", "First, notice that if the function says that an imput number $m$ is not prime, then it is true. \n", "The function can make a mistake only is the case where a number $m$ is not prime, and is excidentally categorized by the function as prime. This can happen if all $100$ $a$'s that the function tried were not witnesses. According to the Miller-Rabin theorem $\\frac{3}{4}$ of all possible $a$s are witnesses, so the probability for error is $(\\frac{1}{4})^{100}$ (this is extremely low)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Testing the prime number theorem: For a large n, a number of n bits is prime with a prob. of O(1/n)\n", "We decide on the size of the sample (to avoid testing all possible $2^{n-1}$ numbers of $n$ bits) and test whether each number we sample is prime. Then we divide the number of primes with the size of the sample. " ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0075" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def prob_prime (n, sample):\n", " cnt = 0\n", " for i in range(sample):\n", " m = random.randint(2**(n-1), 2**n-1)\n", " cnt += is_prime(m)\n", " return cnt/sample\n", "\n", "# prob_prime(2, 10**5)\n", "prob_prime(200, 10**4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Diffie Hellman from lecture" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The protocol as code" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def DH_exchange(p):\n", " \"\"\" generates a shared DH key \"\"\"\n", " g=random.randint(1,p-1)\n", " a=random.randint(1,p-1)# Alice's secret\n", " b=random.randint(1,p-1)# Bob's secret\n", " x=pow(g,a,p)\n", " y=pow(g,b,p)\n", " key_A=pow(y,a,p)\n", " key_B=pow(x,b,p)\n", " #the next line is different from lecture\n", " return g, a, b, x, y, key_A #key_A=key_B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Find a prime number" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def find_prime(n):\n", " \"\"\" find random n-bit long prime \"\"\"\n", " while(True):\n", " candidate = random.randrange(2**(n-1),2**n)\n", " if is_prime(candidate):\n", " return candidate" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Demostration:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "883" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(196, 96, 702, 747, 46, 386)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import random\n", "p = find_prime(10)\n", "p\n", "g,a,b,x,y,key = DH_exchange(p)\n", "g,a,b,x,y,key" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "747" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "386" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pow(g, a, p)\n", "pow(x, b, p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Crack the Diffie Hellman code\n", "There is no known way to find $a$ efficiently, so we try the naive one: iterating over all $a$-s and cheking whether the equation $g^a \\mod p = x$ holds for them. \n", "\n", "If we found $a'$ that satisfies the condition but is not the original $a$, does it matter?\n", "\n", "The time complexity of crack_DH is $O(2^nn^3)$" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def crack_DH(p, g, x):\n", " ''' find secret \"a\" that satisfies g**a%p == x\n", " Not feasible for large p '''\n", " for a in range(1,p-1):\n", " if a%100000==0:\n", " print(a) #just to estimate running time\n", " if pow(g,a,p) == x:\n", " return a\n", " return None #should never get here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Trying to crack the protocol with a 100 bit prime" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(585908982447390826849189842691,\n", " 541120442351353498570334017705,\n", " 1930761781644675344995819292,\n", " 70659930174800164907189704268,\n", " 779461075719798735415516947073,\n", " 1045758344420625426709522664848)" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import random\n", "p = find_prime(100)\n", "# p\n", "g,a,b,x,y,key = DH_exchange(p)\n", "g,a,b,x,y,key\n", "\n", "# crack_DH(p,g,x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Analyzing the nubmer of years it will take to crack the protocol if $a$ is found at the end (assuming iterating over 100000 $a$s takes a second)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "171588166651240962" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "541120442351353498570334017705//100000//60//60//24//365" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OOP" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A link to special method names in python: http://getpython3.com/diveintopython3/special-method-names.html" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Basic polynomial class\n", "\n", "We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1*x^0) + (1*x^1)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(2*x^0) + (3*x^1) + (4*x^2)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", "f = Polynomial([1,1])\n", "g = Polynomial([2,3,4])\n", "\n", "f\n", "g" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add degree and evaluate functions (these are special to class polynomial and are not part of Python's recognized functions)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "6" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", "f = Polynomial([1,1])\n", "f.degree()\n", "f.evaluate(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add \\__eq\\__ function for the '==' operator\n", "Without it, Python compares memory adderesses" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", "f = Polynomial([1,1])\n", "f2 = Polynomial([1,1])\n", "g = Polynomial([2,3,4])\n", "\n", "f == g\n", "f == f2\n", "f.__eq__(f2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add the \\__add\\__ function for the '+' operator" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3*x^0) + (4*x^1) + (4*x^2)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, (Polynomial, int)) \n", " if isinstance(other, int):\n", " terms = [c for c in self.coeffs]\n", " terms[0] += other\n", " return Polynomial(terms)\n", " #else, other is a polynomial\n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms)-1\n", " while last>0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", "f = Polynomial([1,1])\n", "g = Polynomial([2,3,4])\n", "\n", "f+g" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add \\__radd\\__ function for right addition with int\n", "Since there is no support for addition with a Polynomial in the class int, python needs a definition of right addition for int in class Polynomial\n", "\n", "When executing the command $f + 3$, python will first search for an \\__add\\__ method in class int that can support a second operand of type polynomial (self = int, other = polynomial).\n", "If such method does not exist, python will then search for an \\__radd\\__ method in class polynomial that can support a second operand of type int (self= polynomial, other = int).\n", "If such method does not exist, an exception is thrown.\n", "\n", "Since + is commutative, then we set \\__radd\\__ to be identical to \\__add\\__\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2*x^0) + (1*x^1)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, (Polynomial, int)) \n", " if isinstance(other, int):\n", " terms = [c for c in self.coeffs]\n", " terms[0] += other\n", " return Polynomial(terms)\n", " #else, other is a polynomial\n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms)-1\n", " while last>0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " __radd__ = __add__ #to allow int+Polynomial\n", "\n", "f = Polynomial([1,1])\n", "1 + f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add \\__neg\\__ function for unary minus (placing a '-' before a polynomial object)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-1*x^0) + (-1*x^1)" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, (Polynomial, int)) \n", " if isinstance(other, int):\n", " terms = [c for c in self.coeffs]\n", " terms[0] += other\n", " return Polynomial(terms)\n", " #else, other is a polynomial\n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms)-1\n", " while last>0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " __radd__ = __add__ #to allow int+Polynomial\n", " \n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", "\n", "f = Polynomial([1,1])\n", "-f" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add \\__sub\\__ function to subtract one poly form another or an int from a poly\n", "Using the fact we already have \\__neg\\__ and \\__add\\__ we define $f-g = f + (-g)$" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1*x^0) + (2*x^1) + (4*x^2)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(1*x^0) + (3*x^1) + (4*x^2)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, (Polynomial, int)) \n", " if isinstance(other, int):\n", " terms = [c for c in self.coeffs]\n", " terms[0] += other\n", " return Polynomial(terms)\n", " #else, other is a polynomial\n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms)-1\n", " while last>0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " __radd__ = __add__ #to allow int+Polynomial\n", " \n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", " \n", " def __sub__(self, other):\n", " assert isinstance(other, (int,Polynomial)) \n", " return (self + (-other))\n", " \n", "f = Polynomial([1,1])\n", "g = Polynomial([2,3,4])\n", "\n", "g - f\n", "g - 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add \\__rsub\\__ function for right subtraction\n", "Using the fact we already have \\__neg\\__ and \\__sub\\__ we define $f-g = -(g-f)$\n", "\n", "since oprator \\- is not commutative, then we cannot set \\__rsub\\__ to be identical to \\__sub\\__\n", "\n", "Note that the following implementation of \\__rsub\\__ is promlematic, because it will keep calling itself (infinitely)\n", "\n", " def __rsub__(self, other):\n", " return other-self #PROBLEMATIC!\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-1*x^1)" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(-1*x^0) + (-3*x^1) + (-4*x^2)" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\"+str(self.coeffs[k])+\"*x^\" + \\\n", " str(k)+\")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k]!=0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i, c in enumerate(self.coeffs):\n", " result += c * pow(x, i)\n", " return result\n", "\n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, (Polynomial, int)) \n", " if isinstance(other, int):\n", " terms = [c for c in self.coeffs]\n", " terms[0] += other\n", " return Polynomial(terms)\n", " #else, other is a polynomial\n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms)-1\n", " while last>0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " __radd__ = __add__ #to allow int+Polynomial\n", "\n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", "\n", " def __sub__(self, other):\n", " assert isinstance(other, (int,Polynomial)) \n", " return (self + (-other))\n", "\n", " #__rsub__ = __sub__ #not what we want...\n", "\n", " def __rsub__(self, other):\n", " return -(self - other) #why not just other-self ?\n", "\n", "f = Polynomial([1,1])\n", "g = Polynomial([2,3,4])\n", "\n", "1 - f\n", "1 - g" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.2" } }, "nbformat": 4, "nbformat_minor": 1 }