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

cs1001.py , Tel Aviv University, Spring 2019

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Recitation 8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We reviewed some properties of prime numbers and used them for primality testing. We reviewed the Diffie-Hellman protocol for finding a shared secret key and also tried to crack it. \n", "Then, we discussed Linked lists.\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", "\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", " \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. \n", " \n", "- Important properties of Linked lists: \n", " - Not stored continuously in memory.\n", " - Allows for deletion and insertion after a __given__ element in $O(1)$ time.\n", " - Accessing the $i$'th element takes $O(i)$ time.\n", " - Search takes $O(n)$ time (no random access $\\implies$ no $O(\\log{n})$ search)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 14, "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": [ "#### Fermat's little theorem\n", "Fermat's little theorem states that if $p$ is prime and $1 < a < p$, then $a^{p-1} (\\textrm{mod}\\ p) \\equiv 1$\n", "\n", "\n", "\n", "#### Compositeness witnesses\n", "A witness is a piece of evidence that can be produced in order to prove a claim. In our case, the problem we are tackling is deciding whether a given number $m$ is prime or composite. We now describe three types of witnesses for compositeness:\n", "\n", "* A clear witness for compositeness can be a (not necessarily prime) factor of $m$. That is, a number $1 < b < m$ such that $b ~|~ m$ ($b$ divides $m$). Since $b$ is a non-trivial factor of $m$, $m$ is clearly composite.\n", "* Another, less trivial witness of compositeness is a GCD witness, that is a number $1 < b < m$ such that $\\mathrm{gcd}(m,b) > 1$. Think, why is $b$ a witness of compositeness? Let $\\mathrm{gcd}(m,b) = r$, then by definition $r ~|~ n$. As $r \\leq b < m$ we get that $r$ is a factor of $m$ and thus $m$ is composite.\n", "* Fermat's primality test defines another set of witness of compositeness - a number $1 < a < m$ is a Fermat witness if $a^{m-1} (\\textrm{mod}\\ m) \\not\\equiv 1$\n", "\n", "Why go through all of this work? Our tactic would be to randomly draw a number $b \\in {1,\\ldots, m - 1}$ and hope that $b$ is some witness of compositeness. Clearly, we'd like our witness pool to be as large as possible. \n", "\n", "Now, if $m$ is a composite number, let $\\mathrm{FACT}_m, \\mathrm{GCD}_m, \\mathrm{FERM}_m$ be the set of prime factors, GCD witnesses and Fermat witnesses for $m$'s compositeness. It is not hard to show that $$\\mathrm{FACT}_m \\subseteq \\mathrm{GCD}_m \\subseteq \\mathrm{FERM}_m$$ \n", "\n", "But the real strength of Fermat's primality test comes from the fact that if $m$ is composite, then apart from very rare cases (where $n$ is a Carmichael number) it holds that $|\\mathrm{FERM}_m| \\geq m/2$. That is - a random number is a Fermat witness w.p. at least $1/2$.\n", "\n", "A side note (for reference only) - Carmichael numbers are exactly the composite numbers $m$ where $\\mathrm{GCD}_m = \\mathrm{FERM}_m$\n", "\n", "#### Every factor of a composite number is a Fermat's witness\n", "Let $m$ be a composite number and write $m = ab$ for some $a,b>1$. We claim that $a$ is a Fermat witness. To see this, assume towards contradiction that $a^{m-1} (\\textrm{mod}\\ m) \\equiv 1$, i.e. $a^{m-1} = c\\cdot m + 1= c \\cdot a \\cdot b + 1$ for some $c \\geq 1$.\n", "\n", "Rearrange the above to get $a(a^{m-2} - c\\cdot b) = 1$. However, $a > 1$ and $(a^{m-2} - c\\cdot b) \\in \\mathbb{Z}$, a contradiction.\n", "\n", "\n", "#### Primality test using Fermat's witness\n", "\n", "We can use Fermat's little theorem in order test whether a given number $m$ is prime. That is, we can test whether we find a Fermat's witness $a\\in\\mathrm{FERM}_m$ for compositeness. 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 Fermat's witness." ] }, { "cell_type": "code", "execution_count": 24, "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\n" ] }, { "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": 16, "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": [ "#### Runtime analysis:\n", "\n", "* The main loop runs over $b$, dividing $b \\to b/2$ at each iteration, so it runs $O(n)$ times.\n", "* In each iteration we do: \n", " * One operation of $b~\\%~2$ in $O(1)$ time (check least significant bit of $b$)\n", " * One operation of $b~//~2$ in $O(1)$ time (snip $b$'s least significant bit)\n", " * At most two multiplication and two modulu operations\n", " * Multiplication of two $n$ bit numbers runs in time $O(n^2)$\n", " * Modulu can be implemented by addition, division and multiplication: $a \\textrm{ mod } b = a - (a // b) b$ and division runs in time $O(n^2)$ same as multiplication\n", " * Finally, the modulu operation keeps all numbers at most $n$ bits, thus the running time does not increase with each iteration\n", "* In total - $O(n^3)$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The probability of error:\n", "First, notice that if the function says that an input number $m$ is not prime, then it is true. Stated the other way around, if $m$ is prime, the function is always right.\n", "\n", "The function can make a mistake only in the case where a number $m$ is not prime, and is accidentally categorized by the function as prime. This can happen if all $100$ $a$'s that the function had drawn were not witnesses. \n", "\n", "A quick computation shows that if $m$ is **not** a Charmichael number then at least $\\frac{1}{2}$ of all possible $a$s are witnesses, so in almost all cases the probability for error is $(\\frac{1}{2})^{100}$ (which is negligible)." ] }, { "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": 15, "metadata": {}, "outputs": [], "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" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "0.5057" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob_prime(2, 10**4)\n", "prob_prime(3, 10**4)\n" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0148" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob_prime(100, 10**4)" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0081" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "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": 23, "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": 21, "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": 98, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "557\n" ] }, { "data": { "text/plain": [ "(247, 88, 353, 367, 2, 206)" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import random\n", "p = find_prime(10)\n", "print(p)\n", "g, a, b, x, y, key = DH_exchange(p)\n", "g, a, b, x, y, key" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "367\n", "206\n" ] } ], "source": [ "print(pow(g, a, p))\n", "print(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": 17, "metadata": {}, "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": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "88\n" ] }, { "data": { "text/plain": [ "88" ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#g, a, b, x, y, key = DH_exchange(p)\n", "print(a)\n", "crack_DH(p, g, x)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Cracking DH with different values of $a$ (different private keys)\n", "\n", "The algorithm crack_DH can return a different private key ($a$) than the one chosen by Alice, i.e. - $crack\\_DH(p,g,x) = a' \\neq a$, however, in this case we have, by definition of the cracking algorithm: $g^{a'} \\textrm{ mod } p = g^{a} \\textrm{ mod } p$, thus:\n", "\n", "$$y^{a'} \\textrm{ mod } p = \\left(g^{b}\\right)^{a'} \\textrm{ mod } p = \\left(g^{a'}\\right)^{b} \\textrm{ mod } p = \\left(g^{a} \\textrm{ mod } p \\right)^{b} \\textrm{ mod } p = g^{ab} \\textrm{ mod } p$$\n", "\n", "I.e. - we can still compute the shared secret!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Trying to crack the protocol with a 100 bit prime" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "870752849128025769690613494727\n", "556076925348494470910111020503 563975178376164531572554628719 591095820882694542257093278496 683629518338524578223612745129 622210352872361792591098681438 318844905364032174750094749602\n", "100000\n", "200000\n", "300000\n", "400000\n", "500000\n", "600000\n" ] }, { "ename": "KeyboardInterrupt", "evalue": "", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m\u001b[0m\n\u001b[0;32m 5\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0my\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m \u001b[0mcrack_DH\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m\u001b[0m in \u001b[0;36mcrack_DH\u001b[1;34m(p, g, x)\u001b[0m\n\u001b[0;32m 3\u001b[0m Not feasible for large p '''\n\u001b[0;32m 4\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0ma\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m-\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m \u001b[1;33m%\u001b[0m \u001b[1;36m100000\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 6\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m#just to estimate running time\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 7\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mpow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mKeyboardInterrupt\u001b[0m: " ] } ], "source": [ "import random\n", "p = find_prime(100)\n", "print(p)\n", "g, a, b, x, y, key = DH_exchange(p)\n", "print(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": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "563975178376164531572554628719" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1.7883535590314707e+17" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a//100000/60/60/24/365\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Linked Lists\n", "\n", "A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a \"pointer\" to the next node in the list.\n", "\n", "Linked lists support operations such as insertion, deletion, search and many more." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "class Node():\n", " def __init__(self, val):\n", " self.value = val\n", " self.next = None\n", " \n", " def __repr__(self):\n", " #return str(self.value)\n", " \n", " #for today's recitation, we print the id of self as well\n", " return str(self.value) + \"(\" + str(id(self))+ \")\"\n", "\n", "\n", "\n", "class Linked_list():\n", "\n", " def __init__(self, seq=None):\n", " self.next = None\n", " self.len = 0\n", " if seq != None:\n", " for x in seq[::-1]:\n", " self.add_at_start(x)\n", " \n", "\n", " def __repr__(self):\n", " out = \"\"\n", " p = self.next\n", " while p != None :\n", " out += str(p) + \", \" # str(p) envokes __repr__ of class Node\n", " p = p.next\n", " return \"[\" + out[:-2] + \"]\"\n", "\n", " \n", " def __len__(self):\n", " ''' called when using Python's len() '''\n", " return self.len\n", " \n", " \n", " def add_at_start(self, val):\n", " ''' add node with value val at the list head '''\n", " p = self\n", " tmp = p.next\n", " p.next = Node(val)\n", " p.next.next = tmp\n", " self.len += 1\n", " \n", " def add_at_end(self, val):\n", " ''' add node with value val at the list tail '''\n", " p = self\n", " while (p.next != None):\n", " p = p.next\n", " p.next = Node(val)\n", " self.len += 1\n", " \n", " \n", " def insert(self, loc, val):\n", " ''' add node with value val after location 0<=loc" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Adding elements one by one. Try using Python tutor. " ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[b(2165819893856), a(2165819894528)]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l = Linked_list()\n", "l.add_at_start(\"a\")\n", "l.add_at_start(\"b\")\n", "l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### A short summary of methods complexity of Linked lists vs. lists:\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Method List Linked list
init $O(1)$ $O(1)$
init with $k$ items $O(k)$ $O(k)$
for the rest of the methods we assume that the structure contains $n$ items
add at start $O(n)$ $O(1)$
add at end $O(1)$ $O(n)$
$lst[k]$ (get the $k$th item) $O(1)$ $O(k)$
delete $lst[k]$ $O(n-k)$ $O(k)$
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reversing a linked list in $O(1)$ additional memory. \n", "See the code and demo here" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[a(2165820113248), b(2165820113192), c(2165820113136)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[c(2165820113136), b(2165820113192), a(2165820113248)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Node():\n", " def __init__(self, val):\n", " self.value = val\n", " self.next = None\n", " \n", " def __repr__(self):\n", " #return str(self.value)\n", " \n", " #for today's recitation, we print the id of self as well\n", " return str(self.value) + \"(\" + str(id(self))+ \")\"\n", "\n", "\n", "class Linked_list():\n", "\n", " def __init__(self, seq=None):\n", " self.next = None\n", " self.len = 0\n", " if seq != None:\n", " for x in seq[::-1]:\n", " self.add_at_start(x)\n", " \n", "\n", " def __repr__(self):\n", " out = \"\"\n", " p = self.next\n", " while p != None :\n", " out += str(p) + \", \" # str(p) envokes __repr__ of class Node\n", " p = p.next\n", " return \"[\" + out[:-2] + \"]\"\n", "\n", " \n", " def __len__(self):\n", " ''' called when using Python's len() '''\n", " return self.len\n", " \n", " \n", " def add_at_start(self, val):\n", " ''' add node with value val at the list head '''\n", " p = self\n", " tmp = p.next\n", " p.next = Node(val)\n", " p.next.next = tmp\n", " self.len += 1\n", " \n", " def add_at_end(self, val):\n", " ''' add node with value val at the list tail '''\n", " p = self\n", " while (p.next != None):\n", " p = p.next\n", " p.next = Node(val)\n", " self.len += 1\n", " \n", " \n", " def insert(self, loc, val):\n", " ''' add node with value val after location 0<=loc