[lordachita]_ProjectZKM_Assignment2.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "3ATzucG4vhyG"
      },
      "outputs": [],
      "source": [
        "import math\n",
        "import random\n",
        "from sympy import isprime"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Part 1\n",
        "\n",
        "* Create a phrase of about 45 letters, including your name.\n",
        "* Convert to a number as follows: A = 01, . . . , Z = 26, space = 27 etc.\n",
        "Concatenating the digits, you will get a number of about 90 digits.\n",
        "* Add 10 random digits at the end to obtain an odd 100-digit number and test if n is a\n",
        "prime number. Change these last 10 digits until n is prime."
      ],
      "metadata": {
        "id": "eLj4gFx4vmhu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a phrase of about 45 letters, including your name.\n",
        "phrase = ' ACHITA IS BULLISH ON METIS AND HYBRID ROLLUP'"
      ],
      "metadata": {
        "id": "hb_ziL4yvr68"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "len(phrase)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mOiQ8bP_xEeA",
        "outputId": "8c481354-7725-4cad-b17a-ff618b3a5d14"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "45"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def char_to_number(s):\n",
        "    result = \"\"\n",
        "\n",
        "    # Concatenating the digits, you will get a number of about 90 digits.\n",
        "    for char in s.upper():\n",
        "        # Convert to a number as follows: A = 01, . . . , Z = 26, space = 27 etc.\n",
        "        if 'A' <= char <= 'Z':\n",
        "            result += f\"{ord(char) - 64:02}\"\n",
        "        elif char == ' ':\n",
        "            result += \"27\"\n",
        "        else:\n",
        "            continue\n",
        "\n",
        "    return result"
      ],
      "metadata": {
        "id": "8fvXdEQcxgdj"
      },
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "num_phrase = char_to_number(phrase)\n",
        "num_phrase"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "NaT_JOCbxsp0",
        "outputId": "3ac3197b-bf2a-4abd-edc1-1fb66e62a615"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'270103080920012709192702211212091908271514271305200919270114042708250218090427181512122116'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def generate_odd_100_digit_number(num):\n",
        "    while True:\n",
        "        # Add 10 random digits at the end to obtain an odd 100-digit number and test if n is a prime number.\n",
        "        random_digits = ''.join([str(random.randint(0, 9)) for _ in range(9)]) + str(random.choice([1, 3, 5, 7, 9]))\n",
        "        candidate = int(num + random_digits)\n",
        "\n",
        "        if len(str(candidate)) == 100 and candidate % 2 != 0:\n",
        "            return candidate\n",
        "\n",
        "def find_100_digit_prime(num):\n",
        "    while True:\n",
        "        # Change these last 10 digits until n is prime.\n",
        "        candidate = generate_odd_100_digit_number(num)\n",
        "        if isprime(candidate):\n",
        "            return candidate"
      ],
      "metadata": {
        "id": "SQeuUIozw5fn"
      },
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "## prime_number = 2425260103080920011702092123060417060502101115161801190518202301180505150702102304100220115438909631\n",
        "prime_number = find_100_digit_prime(num_phrase)\n",
        "print(f\"Prime number: {prime_number}\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GvnmZim-y6pl",
        "outputId": "e56efb39-c203-490b-b1fb-4ceed103845a"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Prime number: 2701030809200127091927022112120919082715142713052009192701140427082502180904271815121221166481104813\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#prime_number = 2701030809200127091927022112120919082715142713052009192701140427082502180904271815121221166481104813"
      ],
      "metadata": {
        "id": "JU-umV0z8uhS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Part 2\n",
        "\n",
        "* You can use existing libraries to do computations on large numbers, but you must\n",
        "implement your own version of the Miller-Rabin algorithm, according to Fact 4.24 in the\n",
        "HAC (Chapter 4, Page 139). You should hand in the text of this function."
      ],
      "metadata": {
        "id": "iJE-IvJYvre0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_exponent_of_2(n):\n",
        "    if n % 2 == 0:\n",
        "        return \"n must be odd\"\n",
        "\n",
        "    n_minus_1 = n - 1\n",
        "    exponent_of_2 = 0\n",
        "\n",
        "    while n_minus_1 % 2 == 0:\n",
        "        n_minus_1 //= 2\n",
        "        exponent_of_2 += 1\n",
        "    return exponent_of_2\n",
        "\n",
        "def find_s_and_r(n):\n",
        "    s = find_exponent_of_2(n)\n",
        "    r = (n-1)//(2**s)\n",
        "    return s, r"
      ],
      "metadata": {
        "id": "nE7gnFLWdzOz"
      },
      "execution_count": 77,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Algorithm 2.143: Repeated square-and-multiply algorithm for exponentiation in Z_n\n",
        "def repeated_square_and_multiply(a, k, n):\n",
        "  '''\n",
        "  Input:\n",
        "  a - Z_n\n",
        "  0 <= k < n, where k = Sum^{t}_{i=0} k_i*2^i\n",
        "\n",
        "  Output:\n",
        "  a**k % n\n",
        "  '''\n",
        "  if k < 0:\n",
        "    return 'k must greater than or equal to 0'\n",
        "  if k >= n:\n",
        "    return 'k must less than n'\n",
        "\n",
        "  binary_k = bin(k)[2:][::-1]\n",
        "\n",
        "  # Step 1\n",
        "  b = 1\n",
        "  if k == 0:\n",
        "    return b\n",
        "\n",
        " # Step 2\n",
        "  A = a\n",
        "\n",
        "  #Step 3\n",
        "  if binary_k[0] == '1':\n",
        "    b = a\n",
        "\n",
        "  #Step 4\n",
        "  for i in range (1, len(binary_k)):\n",
        "    A = A**2 % n\n",
        "    if binary_k[i] == '1':\n",
        "      b = A*b % n\n",
        "\n",
        "  return b"
      ],
      "metadata": {
        "id": "UDhwxPIpfgqr"
      },
      "execution_count": 70,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def MILLER_RABIN(n, t):\n",
        "  '''\n",
        "  Input:\n",
        "  n - odd number >= 3\n",
        "  t - security parameter t >= 1\n",
        "  Output:\n",
        "  Check whether n is prime?\n",
        "  '''\n",
        "  # Step 1\n",
        "  s,r = find_s_and_r(n)\n",
        "  # Step 2\n",
        "  for i in range(1, t):\n",
        "    # Step 2.1\n",
        "    a = random.randint(2, n-2)\n",
        "    # Step 2.2\n",
        "    y = repeated_square_and_multiply(a, r, n)\n",
        "    if y!= 1 and y!= n-1:\n",
        "      j  = 1\n",
        "      while j <= s - 1 and y != n-1:\n",
        "        y = y**2 % n\n",
        "        if y == 1:\n",
        "          return 'composite'\n",
        "        j += 1\n",
        "      if y!= n-1:\n",
        "        return 'composite'\n",
        "    # Step 3\n",
        "    return 'prime'"
      ],
      "metadata": {
        "id": "XPSMBnKlvw4I"
      },
      "execution_count": 110,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "t = 10\n",
        "MILLER_RABIN(prime_number, t)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "TIioVtbQsErF",
        "outputId": "64a2228f-5458-4c1f-c267-33f5ede2efee"
      },
      "execution_count": 111,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'prime'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 111
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Part 3\n",
        "\n",
        "* If you test only one $a \\in \\mathbb{Z}^{*}_{n}$, what is the probability of error according to Table 4.3 of the HAC? (Chapter 4, Page 147)"
      ],
      "metadata": {
        "id": "LSKIvlmkvw9U"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "n = prime_number\n",
        "k = len(bin(n)[2:])\n",
        "print(k)"
      ],
      "metadata": {
        "id": "5bA7v6DlxONZ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3c690986-360a-44b9-820b-ebb3f9ab97a7"
      },
      "execution_count": 98,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "331\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "t = 10"
      ],
      "metadata": {
        "id": "yNgsGDoR4fPu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# From 4.48\n",
        "def compute_upper_bounds_p(k, t):\n",
        "  if (t == 1) and (k >= 2):\n",
        "    return k**2 * 4**(2-k**(1/2))\n",
        "  elif ((t == 2) and (k >= 88)) or ((k/9 >= t >= 3) and (k >= 21)):\n",
        "    return k**(3/2) * 2**t * t**(-1/2) * 4**(2-(t*k)**(1/2))\n",
        "  elif (k/4 >= t >= k/9) and (k >= 21):\n",
        "    return (7/20) * k * (2**(-5*t)) + (1/7) * (k**(15/4)) * (2**(-k/(2 - 2*t))) +12 * k * (2**(-k/4 - 3*t))\n",
        "  elif (t >= k/4) and (k >= 21):\n",
        "    return 1/7 * (k**(15/4)) * (2**(-k/2 - 2*t))\n",
        "  else:\n",
        "    return 'error'"
      ],
      "metadata": {
        "id": "BESzWCXBxngd"
      },
      "execution_count": 106,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Compute the exponential of p_{k, t} with base 1/2\n",
        "math.log(compute_upper_bounds_p(k, t), 1/2)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "boPdL8pf0IfF",
        "outputId": "964f7a1b-d5ab-4bec-d20b-ce401cf869ba"
      },
      "execution_count": 109,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "90.17013184637307"
            ]
          },
          "metadata": {},
          "execution_count": 109
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Reference\n",
        "\n",
        "*   https://drive.google.com/file/d/1Wi4E6cg2QazGZgvkWlDC3xExByfhg71d/view?pli=1\n",
        "*   https://docs.google.com/forms/d/e/1FAIpQLSc2VBg2l6ONCXUJGC88_CvnzTKAtX42l4xfa5n4wRr-OlyP3g/viewform"
      ],
      "metadata": {
        "id": "HNb8lbDzxN5x"
      }
    }
  ]
}