CB.EN.P2CSE19011_Diffie_Hellman_key_exchange

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code for Finding a large prime number (min 20-digit) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randrange, getrandbits\n",
    "def is_prime(n, k=128):\n",
    "    \"\"\" Test if a number is prime\n",
    "        Args:\n",
    "            n -- int -- the number to test\n",
    "            k -- int -- the number of tests to do\n",
    "        return True if n is prime\n",
    "    \"\"\"\n",
    "    # Test if n is not even.\n",
    "    # But care, 2 is prime !\n",
    "    if n == 2 or n == 3:\n",
    "        return True\n",
    "    if n <= 1 or n % 2 == 0:\n",
    "        return False\n",
    "    # find r and s\n",
    "    s = 0\n",
    "    r = n - 1\n",
    "    while r & 1 == 0:\n",
    "        s += 1\n",
    "        r //= 2\n",
    "    # do k tests\n",
    "    for _ in range(k):\n",
    "        a = randrange(2, n - 1)\n",
    "        x = pow(a, r, n)\n",
    "        if x != 1 and x != n - 1:\n",
    "            j = 1\n",
    "            while j < s and x != n - 1:\n",
    "                x = pow(x, 2, n)\n",
    "                if x == 1:\n",
    "                    return False\n",
    "                j += 1\n",
    "            if x != n - 1:\n",
    "                return False\n",
    "    return True\n",
    "def generate_prime_candidate(length):\n",
    "    \"\"\" Generate an odd integer randomly\n",
    "        Args:\n",
    "            length -- int -- the length of the number to generate, in bits\n",
    "        return a integer\n",
    "    \"\"\"\n",
    "    # generate random bits\n",
    "    p = getrandbits(length)\n",
    "    # apply a mask to set MSB and LSB to 1\n",
    "    p |= (1 << length - 1) | 1\n",
    "    return p\n",
    "def generate_prime_number(length=60):\n",
    "    \"\"\" Generate a prime\n",
    "        Args:\n",
    "            length -- int -- length of the prime to generate, in          bits\n",
    "        return a prime\n",
    "    \"\"\"\n",
    "    p = 4\n",
    "    # keep generating while the primality test fail\n",
    "    while not is_prime(p, 128):\n",
    "        p = generate_prime_candidate(length)\n",