[lordachita]_ProjectZKM_Assignment1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "import math"
      ],
      "metadata": {
        "id": "ddMtVaBSR-8N"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#3.9 Algorithm Pollard’s rho algorithm for factoring integers"
      ],
      "metadata": {
        "id": "4ArcolydHqHw"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "PR6Bzf87Qs2R"
      },
      "outputs": [],
      "source": [
        "def algorithm_3_9(n):\n",
        "  # Step 1\n",
        "  a, b = 2, 2\n",
        "  n = abs(n)\n",
        "  f = lambda x: (x**2 + 1) % n\n",
        "\n",
        "  while True:\n",
        "    # Step 2.1\n",
        "    a = f(a)\n",
        "    b = f(f(b))\n",
        "\n",
        "    # Step 2.2\n",
        "    d = math.gcd(a-b, n)\n",
        "\n",
        "    # Step 2.3\n",
        "    if 1<d<n:\n",
        "      return d\n",
        "    # Step 2.4\n",
        "    elif d == n:\n",
        "      return 'Error'\n",
        "    else:\n",
        "      pass\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 3.10 Example (Pollard’s rho algorithm for finding a non-trivial factor of n = 455459)"
      ],
      "metadata": {
        "id": "WZeIHzoFIG-j"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "algorithm_3_9(455459)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pmi4CQxh-q6Q",
        "outputId": "8ea651a2-6673-443d-fbfe-f38cec6ee60d"
      },
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "743"
            ]
          },
          "metadata": {},
          "execution_count": 28
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#3.60 Algorithm Pollard’s rho algorithm for computing discrete logarithms\n",
        "\n",
        "Let\n",
        "\n",
        "*   $S_1 = {x %3 = 1}$\n",
        "*   $S_2 = {x %3 = 0}$\n",
        "*   $S_3 = {x %3 = 2}$"
      ],
      "metadata": {
        "id": "6UT5a-qfzUbx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def algorithm_3_60(alpha, beta, n, k=383):\n",
        "\n",
        "  # Step 1\n",
        "  x_0, a_0, b_0 = 1, 0, 0\n",
        "\n",
        "  def f(x, a, b):\n",
        "    if x%3 == 1:\n",
        "      return beta * x % k, a, (b+1) % n\n",
        "    elif x%3 == 0:\n",
        "      return x * x % k, (2*a) % n, (2*b) % n\n",
        "    else:\n",
        "      return alpha * x % k, (a+1) % n, b\n",
        "\n",
        "  x_i_1, a_i_1, b_i_1 = x_0, a_0, b_0\n",
        "  x_2i_2, a_2i_2, b_2i_2 = x_0, a_0, b_0\n",
        "\n",
        "  while True:\n",
        "    # Step 2.1\n",
        "    x_i, a_i, b_i = f(x_i_1, a_i_1, b_i_1)\n",
        "    x_2i, a_2i, b_2i = f(*f(x_2i_2, a_2i_2, b_2i_2))\n",
        "\n",
        "    x_i_1, a_i_1, b_i_1 = x_i, a_i, b_i\n",
        "    x_2i_2, a_2i_2, b_2i_2 = x_2i, a_2i, b_2i\n",
        "\n",
        "    #print(x_i, a_i, b_i)\n",
        "\n",
        "    # Step 2.2\n",
        "    if x_i == x_2i:\n",
        "      r = (b_i - b_2i) % n\n",
        "      if r == 0:\n",
        "        return 'Error'\n",
        "      else:\n",
        "        return (pow(r, -1, n) * (a_2i - a_i)) % n"
      ],
      "metadata": {
        "id": "loIZ8CSkSdWg"
      },
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#3.61 Example (Pollard’s rho algorithm for logarithms in a subgroup of $Z^∗_{383}$)"
      ],
      "metadata": {
        "id": "YndmBO4qH3qI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "algorithm_3_60(2, 228, 191)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ueV22PoP46ma",
        "outputId": "7ccdbc53-513e-4fd4-e928-d07a185dab83"
      },
      "execution_count": 69,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "228 0 1\n",
            "279 0 2\n",
            "92 0 4\n",
            "184 1 4\n",
            "205 1 5\n",
            "14 1 6\n",
            "28 2 6\n",
            "256 2 7\n",
            "152 2 8\n",
            "304 3 8\n",
            "372 3 9\n",
            "121 6 18\n",
            "12 6 19\n",
            "144 12 38\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "110"
            ]
          },
          "metadata": {},
          "execution_count": 69
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Reference\n",
        "\n",
        "https://drive.google.com/file/d/187_2HrVvWalC-aRcpYw4CPCUVLE7EeiI/view?pli=1"
      ],
      "metadata": {
        "id": "Q7C3SUZGHjNW"
      }
    }
  ]
}