Created
January 14, 2020 02:26
-
-
Save LarryRuane/4446193dfe224fda089886574c71eb22 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "code", | |
| "execution_count": 60, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "############## PLEASE RUN THIS CELL FIRST! ###################\n", | |
| "\n", | |
| "# import everything and define a test runner function\n", | |
| "from importlib import reload\n", | |
| "from helper import run\n", | |
| "import ecc\n", | |
| "import helper\n", | |
| "from ecc import FieldElement" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# A finite field of order N has four operations, +, -, *, /,\n", | |
| "# and set of \"elements\", 0 through N-1. We will discuss the\n", | |
| "# special case in which N is prime.\n", | |
| "#\n", | |
| "# A finite field has the following properties:\n", | |
| "# - closure (results of operations are within the set)\n", | |
| "# - a unique additive identity, 0 (e+0 = e)\n", | |
| "# - a unique multiplicitive identity, 1 (e*1 = e)\n", | |
| "# - every e has a unique additive inverse -e (e + (-e) = 0)\n", | |
| "# - every nonzero e has a unique multiplicitive inverse 1/e or e**(-1)\n", | |
| "# (e * (e**(-1)) = 1)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# You could say there are only two operations, addition and multiplication\n", | |
| "# a - b = a + (-b)\n", | |
| "# a / b = a * (b**(-1))\n", | |
| "\n", | |
| "# But it's convenient to implement subtraction and division" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Operations are similar to normal math, but closure complicates things\n", | |
| "# N=13, 8+9 = 17, but 17 is outside the set 0..12\n", | |
| "# Solution: modular arithmetic (\"clock\" arithmetic, wrap-around)\n", | |
| "# Do normal math, but add or subtract N until the result is 0..12\n", | |
| "\n", | |
| "# Division presents a special problem that we'll address later\n", | |
| "# normal math: 1 / 2 = 0.5 but that's not a whole number" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 61, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "7 13\n", | |
| "FieldElement_13(7)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Representation:\n", | |
| "# A finite field FieldElement has two integer values,\n", | |
| "# a prime and a number in the range zero to prime-1\n", | |
| "a = FieldElement(7, 13)\n", | |
| "print(a.num, a.prime)\n", | |
| "print(a)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 62, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "ename": "ValueError", | |
| "evalue": "Num 6 not in field range 0 to 4", | |
| "output_type": "error", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-62-07fe1784e8c7>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# The number must be less than the prime (else exception)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0ma\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mFieldElement\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", | |
| "\u001b[0;32m~/git/programmingbitcoin/code-ch01/ecc.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, num, prime)\u001b[0m\n\u001b[1;32m 9\u001b[0m error = 'Num {} not in field range 0 to {}'.format(\n\u001b[1;32m 10\u001b[0m num, prime - 1)\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merror\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 12\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnum\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnum\u001b[0m \u001b[0;31m# <2>\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprime\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mprime\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mValueError\u001b[0m: Num 6 not in field range 0 to 4" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The number must be less than the prime (else exception)\n", | |
| "a = FieldElement(6, 5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 63, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "ename": "ValueError", | |
| "evalue": "Num -1 not in field range 0 to 4", | |
| "output_type": "error", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-63-4ca87abb99dd>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m# The number can't be negative (else exception)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0ma\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mFieldElement\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", | |
| "\u001b[0;32m~/git/programmingbitcoin/code-ch01/ecc.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, num, prime)\u001b[0m\n\u001b[1;32m 9\u001b[0m error = 'Num {} not in field range 0 to {}'.format(\n\u001b[1;32m 10\u001b[0m num, prime - 1)\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merror\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 12\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnum\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnum\u001b[0m \u001b[0;31m# <2>\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprime\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mprime\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mValueError\u001b[0m: Num -1 not in field range 0 to 4" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The number can't be negative (else exception)\n", | |
| "a = FieldElement(-1, 5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 64, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "False\n", | |
| "True\n", | |
| "True\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# You can compare elements\n", | |
| "a = FieldElement(7, 13)\n", | |
| "b = FieldElement(6, 13)\n", | |
| "print(a == b)\n", | |
| "print(a == a)\n", | |
| "print(a != b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 65, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "False\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The elements must have the same prime to be considered equal\n", | |
| "a = FieldElement(6, 13)\n", | |
| "b = FieldElement(7, 11)\n", | |
| "print(a == b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 66, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Addition is similar to integers\n", | |
| "a = FieldElement(2, 5)\n", | |
| "b = FieldElement(1, 5)\n", | |
| "print(a+b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 67, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(1)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# But the values are always modulo-reduced by the prime\n", | |
| "a = FieldElement(2, 5)\n", | |
| "b = FieldElement(4, 5)\n", | |
| "print(a+b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 68, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(1)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The + operator translates to a much less readable\n", | |
| "# call to a \"dunder\" (double-underscore) class function:\n", | |
| "print(a.__add__(b))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 69, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Subtraction is obvious too, except if the result is\n", | |
| "# negative, modulo-reduction brings the result back to\n", | |
| "# the range 0..prime-1\n", | |
| "a = FieldElement(2, 5)\n", | |
| "b = FieldElement(4, 5)\n", | |
| "print(a-b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 70, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "3\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# This is the same as how normal mod works\n", | |
| "print((2 - 4) % 5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 71, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Multiplication is as normal too, but with modulo-reduction\n", | |
| "a = FieldElement(2, 5)\n", | |
| "b = FieldElement(4, 5)\n", | |
| "print(a*b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 72, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "2\n", | |
| "2\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# This may not be obvious about modulo-reduction\n", | |
| "print((4083343 * 1376284) % 5)\n", | |
| "# This can be simplified by first reducing the operands\n", | |
| "print(((4083343 % 5) * (1376284 % 5)) % 5)\n", | |
| "# (This applies to all other operations too)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 73, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(2)\n", | |
| "FieldElement_5(2)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Every finite field has a unique additive identity, 0,\n", | |
| "# and a unique multiplicative identity, 1\n", | |
| "print(FieldElement(2, 5) + FieldElement(0, 5))\n", | |
| "print(FieldElement(2, 5) * FieldElement(1, 5))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 74, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "2 * 0 = FieldElement_5(0)\n", | |
| "2 * 1 = FieldElement_5(2)\n", | |
| "2 * 2 = FieldElement_5(4)\n", | |
| "2 * 3 = FieldElement_5(1)\n", | |
| "2 * 4 = FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# What is the multiplicative inverse (of 2)?\n", | |
| "# x = 1/2\n", | |
| "# But fractions aren't allowed! (closure)\n", | |
| "# In a finite field, only whole numbers allowed\n", | |
| "# \n", | |
| "# We can rewrite (multiply both sides by 2):\n", | |
| "# 2 * x = 1 (mod 5)\n", | |
| "# let's search for which x makes that true\n", | |
| "for i in range(5):\n", | |
| " x = FieldElement(i, 5)\n", | |
| " print(\"2 *\", i, \"=\", FieldElement(2, 5) * x)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 75, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# We could have figured out 2's inverse in our\n", | |
| "# heads: what multiplied by 2 gives us (say)\n", | |
| "# one greater than 5 (so 1 mod 5)? Answer 3\n", | |
| "print((2*3) % 5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 76, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(3)\n", | |
| "FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# FieldElement supports division, but that's just\n", | |
| "# multiplication by the multiplicative inverse (like\n", | |
| "# subtraction is addition of the additive inverse)\n", | |
| "print(FieldElement(1, 5) / FieldElement(2, 5))\n", | |
| "print(FieldElement(1, 5) * FieldElement(3, 5))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 77, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(2)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# If 3 is 2's inverse, then 2 should be 3's inverse\n", | |
| "print(FieldElement(1, 5) / FieldElement(3, 5))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 78, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1 / 1 = FieldElement_5(1)\n", | |
| "1 / 2 = FieldElement_5(3)\n", | |
| "1 / 3 = FieldElement_5(2)\n", | |
| "1 / 4 = FieldElement_5(4)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# What are the multiplicative inverses of the other elements?\n", | |
| "for i in range(1, 5):\n", | |
| " print(\"1 /\", i, \"=\", FieldElement(1, 5) / FieldElement(i, 5))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# 4 is its own inverses, which seems strange, because \n", | |
| "# with normal integers, only 1 is its own inverse." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 79, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1 FieldElement_5(1)\n", | |
| "2 FieldElement_5(2)\n", | |
| "3 FieldElement_5(3)\n", | |
| "4 FieldElement_5(4)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# How do we calculate an element's inverse without\n", | |
| "# searching for the value that multiplies to produce 1?\n", | |
| "# \n", | |
| "# Fermat's Little Theorem says that if we raise any\n", | |
| "# element to the prime (5), we get the same element\n", | |
| "for i in range(1, 5):\n", | |
| " x = FieldElement(i, 5)\n", | |
| " print(i, x**5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 80, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1 FieldElement_5(1)\n", | |
| "2 FieldElement_5(1)\n", | |
| "3 FieldElement_5(1)\n", | |
| "4 FieldElement_5(1)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# If we reduce the power by 1, we always get 1\n", | |
| "# because one times the element gives the element\n", | |
| "for i in range(1, 5):\n", | |
| " x = FieldElement(i, 5)\n", | |
| " print(i, x**(5-1))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 81, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1 FieldElement_5(1)\n", | |
| "2 FieldElement_5(3)\n", | |
| "3 FieldElement_5(2)\n", | |
| "4 FieldElement_5(4)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# If we reduce the power by one more (exponent = prime-2),\n", | |
| "# then we get the inverse, since that value times\n", | |
| "# the element gives 1\n", | |
| "for i in range(1, 5):\n", | |
| " x = FieldElement(i, 5)\n", | |
| " print(i, x**(5-2))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 82, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "27\n", | |
| "2\n", | |
| "FieldElement_5(2)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The FieldElement class also support exponentiation,\n", | |
| "print(3**3)\n", | |
| "print((3**3) % 5)\n", | |
| "print(FieldElement(3, 5) ** 3)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 83, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(2)\n", | |
| "FieldElement_5(2)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# But note that the exponent is *not* a FieldElement,\n", | |
| "# it's just an integer; this is because exponentiation\n", | |
| "# is really just repeated multiplication\n", | |
| "a = FieldElement(3, 5)\n", | |
| "result = FieldElement(1, 5)\n", | |
| "for _ in range(3):\n", | |
| " result *= a\n", | |
| "print(result)\n", | |
| "print(a**3)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 84, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(2)\n", | |
| "FieldElement_5(2)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# A computational optimization is to mod-reduce\n", | |
| "# the exponent by (prime-1)\n", | |
| "print(FieldElement(3, 5) ** 103)\n", | |
| "print(FieldElement(3, 5) ** (103 % 4))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 85, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_113(35)\n", | |
| "FieldElement_113(50)\n", | |
| "FieldElement_113(23)\n", | |
| "FieldElement_113(49)\n", | |
| "FieldElement_113(70)\n", | |
| "FieldElement_113(100)\n", | |
| "FieldElement_113(46)\n", | |
| "FieldElement_113(98)\n", | |
| "FieldElement_113(27)\n", | |
| "FieldElement_113(87)\n", | |
| "FieldElement_113(92)\n", | |
| "FieldElement_113(83)\n", | |
| "FieldElement_113(54)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Exponentiation is important because of the \"discrete\n", | |
| "# log problem\".\n", | |
| "# \n", | |
| "# Roughly, it says that if the field is large, and you\n", | |
| "# raise an element to a large power and reveal that value\n", | |
| "# and the base element, it's very hard to work backwards\n", | |
| "# and figure out the exponent.\n", | |
| "for i in range(77, 90):\n", | |
| " print(FieldElement(66, 113) ** i)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# If someone told you 113 (the prime), 66 (the base element),\n", | |
| "# and 35, it would be hard for you to calculate the exponent (77)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 86, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "19683\n", | |
| "19683\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# We're going to leave finite fields for a moment...\n", | |
| "\n", | |
| "# Intuitive (slow) exponentiation: repeated multiplication\n", | |
| "# example: 3 ** 9\n", | |
| "n = 3\n", | |
| "r = 1 # eventual result\n", | |
| "for i in range(9):\n", | |
| " r *= n\n", | |
| "print(r)\n", | |
| "print(3**9)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 87, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "19683\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# More efficient way: Square and Multiply\n", | |
| "# Note that (x**2)**2 = x**4\n", | |
| "# (because (x*x)*(x*x) = x*x*x*x = x**4)\n", | |
| "\n", | |
| "# same example, 3 ** 9, note that 9 = 1001 binary\n", | |
| "n = 3\n", | |
| "r = 1 # eventual result\n", | |
| "s = n # sequence of squares (n**1, n**2, n**4, n**8...)\n", | |
| "\n", | |
| "r *= s; s *= s # 1 (least significant bit)\n", | |
| "r *= 1; s *= s # 0\n", | |
| "r *= 1; s *= s # 0\n", | |
| "r *= s; s *= s # 1 (most significant bit)\n", | |
| "\n", | |
| "print(r)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 88, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "19683\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Or, just write this as a loop\n", | |
| "n = 3\n", | |
| "r = 1 # eventual result\n", | |
| "s = n # sequence of squares (n**1, n**2, n**4, n**8...)\n", | |
| "e = 9 # exponent\n", | |
| "while e > 0:\n", | |
| " if e & 1:\n", | |
| " r *= s\n", | |
| " s *= s\n", | |
| " e >>= 1\n", | |
| "\n", | |
| "print(r)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 89, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "3\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# If we're working in a finite field, we must mod-reduce\n", | |
| "# the final result (say, prime=5)\n", | |
| "print(r % 5)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 90, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "3\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# But we can be more efficient by mod-5-reducing as we go\n", | |
| "n = 3\n", | |
| "r = 1 # eventual result\n", | |
| "s = n # sequence of squares (n**1, n**2, n**4, n**8...)\n", | |
| "e = 9 # exponent\n", | |
| "# but note that (x**9) % 5 is (x**(9%(5-1)) % 5)\n", | |
| "e %= 4\n", | |
| "while e > 0:\n", | |
| " if e & 1:\n", | |
| " r *= s\n", | |
| " r %= 5 # continually mod-reduce\n", | |
| " s *= s\n", | |
| " s %= 5 # continually mod-reduce\n", | |
| " e >>= 1\n", | |
| "\n", | |
| "print(r)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 92, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "19683\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# The python pow() builtin uses this algorithm\n", | |
| "print(pow(3, 9))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 93, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "FieldElement_5(3)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Our FieldElement class uses pow()\n", | |
| "print(FieldElement(3, 5) ** 9)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 94, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "prime = 115792089237316195423570985008687907853269984665640564039457584007913129639747\n", | |
| "result = 56856439206753777796161714236253098497449858320241055486435022170541264382655\n", | |
| "pow builtin = 56856439206753777796161714236253098497449858320241055486435022170541264382655\n", | |
| "FieldElement_115792089237316195423570985008687907853269984665640564039457584007913129639747(56856439206753777796161714236253098497449858320241055486435022170541264382655)\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Let's scale this up..\n", | |
| "n = 74829857218757390747636325024242767123 # completely random\n", | |
| "p = 2**256 - 189\n", | |
| "print(\"prime =\", p)\n", | |
| "r = 1 # eventual result\n", | |
| "s = n # sequence of squares (n**1, n**2, n**4, n**8...)\n", | |
| "exp = 2**215 - 157 # exponent (doesn't have to be prime)\n", | |
| "e = exp\n", | |
| "while e > 0:\n", | |
| " if e & 1:\n", | |
| " r *= s\n", | |
| " r %= p # continually mod-reduce\n", | |
| " s *= s\n", | |
| " s %= p # continually mod-reduce\n", | |
| " e >>= 1\n", | |
| "\n", | |
| "print(\"result = \", r)\n", | |
| "print(\"pow builtin =\", pow(n, exp, p))\n", | |
| "print(FieldElement(n, p) ** exp)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# fin" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 1\n", | |
| "\n", | |
| "Write the corresponding method `__ne__` which checks if two `FieldElement` objects are _not equal_ to each other.\n", | |
| "\n", | |
| "#### Make [this test](/edit/code-ch01/ecc.py) pass: `ecc.py:FieldElementTest:test_ne`" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "scrolled": true | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 1\n", | |
| "\n", | |
| "reload(ecc)\n", | |
| "run(ecc.FieldElementTest(\"test_ne\"))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "print(7 % 3)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "print(-27 % 13)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 2\n", | |
| "\n", | |
| "Solve these problems in \\\\(F_{57}\\\\) (assume all +'s here are \\\\(+_{f}\\\\) and -`s here \\\\(-_{f}\\\\))\n", | |
| "\n", | |
| "* 44+33\n", | |
| "* 9-29\n", | |
| "* 17+42+49\n", | |
| "* 52-30-38" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 2\n", | |
| "\n", | |
| "# remember that % is the modulo operator\n", | |
| "prime = 57\n", | |
| "for i in (44+33, 9-29, 17+42+49, 52-30-38):\n", | |
| " print(i%prime)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "from ecc import FieldElement\n", | |
| "a = FieldElement(7, 13)\n", | |
| "b = FieldElement(12, 13)\n", | |
| "c = FieldElement(6, 13)\n", | |
| "print(a+b==c)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 3\n", | |
| "\n", | |
| "Write the corresponding `__sub__` method which defines the subtraction of two `FieldElement` objects.\n", | |
| "\n", | |
| "#### Make [this test](/edit/code-ch01/ecc.py) pass: `ecc.py:FieldElementTest:test_sub`" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 3\n", | |
| "\n", | |
| "reload(ecc)\n", | |
| "run(ecc.FieldElementTest(\"test_sub\"))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 4\n", | |
| "\n", | |
| "Solve the following equations in \\\\(F_{97}\\\\) (again, assume ⋅ and exponentiation are field versions):\n", | |
| "\n", | |
| "* 95⋅45⋅31\n", | |
| "* 17⋅13⋅19⋅44\n", | |
| "* \\\\(12^{7}\\\\)⋅\\\\(77^{49}\\\\)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 4\n", | |
| "\n", | |
| "prime = 97\n", | |
| "for i in 95*45*31, 17*13*19*44, (12**7)*(77**49):\n", | |
| " print(i % prime)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 5\n", | |
| "\n", | |
| "For k = 1, 3, 7, 13, 18, what is this set in \\\\(F_{19}\\\\)?\n", | |
| "\n", | |
| "{k⋅0, k⋅1, k⋅2, k⋅3, ... k⋅18}\n", | |
| "\n", | |
| "Do you notice anything about these sets?" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 5\n", | |
| "\n", | |
| "prime = 12\n", | |
| "for k in range(prime+3):\n", | |
| " print(\"k\", k, end=' ')\n", | |
| " a = [(k*i) % prime for i in range(prime)]\n", | |
| " print(len(set(a)), (a))\n", | |
| "# loop through all possible k's 0 up to prime-1\n", | |
| "# calculate k*iterator % prime\n", | |
| "\n", | |
| "# Hint - sort!" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "from ecc import FieldElement\n", | |
| "reload(ecc)\n", | |
| "a = FieldElement(3, 13)\n", | |
| "b = FieldElement(12, 13)\n", | |
| "c = FieldElement(10, 13)\n", | |
| "print(a*b==c)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 6\n", | |
| "\n", | |
| "Write the corresponding `__mul__` method which defines the multiplication of two Finite Field elements.\n", | |
| "\n", | |
| "#### Make [this test](/edit/code-ch01/ecc.py) pass: `ecc.py:FieldElementTest:test_mul`" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 6\n", | |
| "\n", | |
| "reload(ecc)\n", | |
| "run(ecc.FieldElementTest(\"test_mul\"))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "from ecc import FieldElement\n", | |
| "reload(ecc)\n", | |
| "a = FieldElement(3, 13)\n", | |
| "b = FieldElement(1, 13)\n", | |
| "print(a**3==b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 7\n", | |
| "\n", | |
| "For p = 7, 11, 17, 31, what is this set in \\\\(F_{p}\\\\)?\n", | |
| "\n", | |
| "{\\\\(1^{(p-1)}\\\\), \\\\(2^{(p-1)}\\\\), \\\\(3^{(p-1)}\\\\), \\\\(4^{(p-1)}\\\\), ... \\\\((p-1)^{(p-1)}\\\\)}" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 7\n", | |
| "\n", | |
| "# when prime (test 12), every element is a generator:\n", | |
| "primes = (7, 12, 17, 31, 43)\n", | |
| "for p in primes:\n", | |
| " print(p, end=' ')\n", | |
| " powers = set()\n", | |
| " for i in range(p):\n", | |
| " powers.add(pow(i, p-2, p))\n", | |
| " print(len(powers), powers)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 8\n", | |
| "\n", | |
| "Solve the following equations in \\\\(F_{31}\\\\):\n", | |
| "\n", | |
| "* 3 / 24\n", | |
| "* \\\\(17^{-3}\\\\)\n", | |
| "* \\\\(4^{-4}\\\\)⋅11" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 8\n", | |
| "\n", | |
| "print((3 * 24**29) % 31) # 3/24\n", | |
| "print((24 * 8**29) % 31) # 24/8\n", | |
| "print((1 * (17**3)**29) % 31) # 17^(-3)\n", | |
| "print((11 * ((4**4)**29)) % 31) # 4**-4*11" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "### Exercise 9\n", | |
| "\n", | |
| "Write the corresponding `__truediv__` method which defines the division of two field elements.\n", | |
| "\n", | |
| "Note that in Python3, division is separated into `__truediv__` and `__floordiv__`. The first does normal division, the second does integer division.\n", | |
| "\n", | |
| "#### Make [this test](/edit/code-ch01/ecc.py) pass: `ecc.py:FieldElementTest:test_div`" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "# Exercise 9\n", | |
| "\n", | |
| "reload(ecc)\n", | |
| "run(ecc.FieldElementTest(\"test_div\"))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "from ecc import FieldElement\n", | |
| "a = FieldElement(7, 13)\n", | |
| "b = FieldElement(8, 13)\n", | |
| "print(a**-3==b)" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [] | |
| } | |
| ], | |
| "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.7.1" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment