HW4_EE_4940_code.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "71ca29b3-b8a5-4c9a-a410-ff3656c39883",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Import libraries\n",
    "import sympy as sp\n",
    "import numpy as np\n",
    "from decimal import *\n",
    "np.set_printoptions(legacy='1.25')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ccb3f07",
   "metadata": {},
   "source": [
    "## Problem 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "eb19cf2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def RSA_encrypt(M,e,n) : #Encypts a message using RSA.\n",
    "    \"\"\" Inputs:\n",
    "            M: 8 digit number representation of a 4 letter word.\n",
    "            e: RSA public key list, e.g. 17 = [1,0,0,0,1,1,0,0,0,0]\n",
    "            n: n in RSA, public information.\n",
    "        Returns: M^e (mod n)\n",
    "    \"\"\"\n",
    "    c = 0\n",
    "    f = 1\n",
    "    for i in e :\n",
    "        c = c*2\n",
    "        f = f*f % n\n",
    "        if i==1 :\n",
    "            c = c+1\n",
    "            f = np.multiply(f,M) % n\n",
    "\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "aaeb5428",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected Value = 1; Actual Value = 1\n"
     ]
    }
   ],
   "source": [
    "# A quick example from lecture to make sure my algorithm works.\n",
    "n = 561\n",
    "e = [1,0,0,0,1,1,0,0,0,0]\n",
    "M = 7\n",
    "lecture_example = RSA_encrypt(7,e,n)\n",
    "print(f'Expected Value = 1; Actual Value = {lecture_example}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7ffb2230",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C1 = 00201088, C2 = 85403970, C3 = 19023410, C4 = 22989214\n"
     ]
    }
   ],
   "source": [
    "#Problem 4 work.\n",
    "n=121643759\n",
    "e = [0,0,0,1,0,0,0,1] #e = 17\n",
    "M1 = 3414142 #'Coop'\n",
    "M2 = 31440006 #'er F' \n",
    "M3 = 44413139 #'roem'\n",
    "M4 = 39354033 #'ming'\n",
    "\n",
    "C1 = RSA_encrypt(M1,e,n)\n",
    "C2 = RSA_encrypt(M2,e,n)\n",
    "C3 = RSA_encrypt(M3,e,n)\n",
    "C4 = RSA_encrypt(M4,e,n)\n",
    "print(f'C1 = 00{C1}, C2 = {C2}, C3 = {C3}, C4 = {C4}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "941fcb33",
   "metadata": {},
   "source": [
    "## Problem 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "bd9fb642",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Must have R = [], and Q = [] set outside of function\n",
    "def euclidean_algorithm(a,b,R,Q) : \n",
    "    \"\"\" Recursive function to \n",
    "        find remainders in euclidean algorithm.\n",
    "\n",
    "        Inputs:\n",
    "        a,b: integers in euclidean algorithm.\n",
    "        R is empty list for remainders to be appended\n",
    "        Q is empty list for quotients to be appended\n",
    "\n",
    "        Returns: current remainder.\n",
    "    \"\"\"\n",
    "    q = int(a/b)\n",
    "    r = a-b*q\n",
    "    R.append(r)\n",
    "    Q.append(q)\n",
    "    if r == 1 : # Base Case\n",
    "        return\n",
    "    euclidean_algorithm(b,r,R,Q)\n",
    "\n",
    "\n",
    "def euclidean_mult_inverses(a,b) :\n",
    "    \"\"\" Uses euclidean algorithm to determine\n",
    "        x,y that satisfies x*a + y*b = 1\n",
    "        \n",
    "        Returns: [x,y]\n",
    "    \"\"\"\n",
    "    R = []\n",
    "    Q = []\n",
    "    euclidean_algorithm(a,b,R,Q)\n",
    "    A = [[0,len(Q)-x-1] for x in range(0,len(Q))]\n",
    "    R.reverse()\n",
    "    Q.reverse()\n",
    "    A[0][0] = -Q[0]\n",
    "    A[1][0] = 1\n",
    "    m1 = 0\n",
    "    m2 = 0\n",
    "    i=1\n",
    "    while i<len(R) :\n",
    "        #print(f'i={i}')\n",
    "        A_temp = A[i-1][0]\n",
    "        #print(f'A_temp = {A_temp}')\n",
    "        #print(f'Q[{i}] = {Q[i]}')\n",
    "        A[i-1][0] = 0\n",
    "        A[i][0] = A[i][0] - A_temp*Q[i]\n",
    "        #print(A)\n",
    "        if (i+1)<len(R) : A[i+1][0] = A[i+1][0] + A_temp\n",
    "        else : x = A_temp\n",
    "        i+=1\n",
    "    y = A[len(A)-1][0]\n",
    "    #print(f'm1={x}, m2={y}')\n",
    "    return [x,y]\n",
    "\n",
    "def find_CRT_remainder(list) :\n",
    "    \"\"\" Inputs: \n",
    "                list: [[n1,a1],[n2,a2],...[nk,ak]]\n",
    "        Returns a \"total\" that is satisfies \n",
    "                        total (mod n1) = a1, \n",
    "                        total (mod n2) = a2,\n",
    "                        ... , \n",
    "                        total (mod nk) = ak.\n",
    "    \"\"\"\n",
    "    #Check if all numbers are coprime\n",
    "    for set1 in list :\n",
    "        for set2 in list :\n",
    "            if set1 != set2 :\n",
    "                gcd = np.gcd(set1[0],set2[0])\n",
    "                if (gcd != 1) :\n",
    "                    print(f'ERROR: {set1[0]} and {set2[0]} not GCD')\n",
    "                    return -1\n",
    "    sum = [0 for x in range(0,len(list))]\n",
    "    #Find Capital M\n",
    "    i = 0\n",
    "    for n_a_pair in list :\n",
    "        M = 1\n",
    "        for m_pair in list : \n",
    "            if (m_pair != n_a_pair) : M = M*m_pair[0] #M1 = n2*n3*n4*...*nk, M2 = n1*n3*n4*...*nk, etc.\n",
    "        A = euclidean_mult_inverses(M,n_a_pair[0])[0] # Ai, solution for AiMi+Bi*ni = 1\n",
    "        sum[i] = A*n_a_pair[1]*M #Ai*Mi*ai\n",
    "        i+=1\n",
    "    total = 0\n",
    "    print(sum)\n",
    "    for num in sum :\n",
    "        total = total + num\n",
    "    return total\n",
    "\n",
    "def decimal_cuberoot(input) :\n",
    "    \"\"\" input: integer value \n",
    "    \n",
    "        Returns: cube root of input.\n",
    "    \"\"\"\n",
    "    x = str(input)\n",
    "    minprec = 40\n",
    "    if len(x) > minprec: getcontext().prec = len(x)\n",
    "    else:                getcontext().prec = minprec\n",
    "\n",
    "    x = Decimal(x)\n",
    "    power = Decimal(1)/Decimal(3)\n",
    "\n",
    "    answer = x**power\n",
    "    ranswer = answer.quantize(Decimal('1.'), rounding=ROUND_UP)\n",
    "\n",
    "    #diff = x - ranswer**Decimal(3)\n",
    "    # if diff == Decimal(0):\n",
    "    #     print(\"x is the cubic number of\", ranswer)\n",
    "    # else:\n",
    "    #     print(\"x has a cubic root of \", answer)\n",
    "\n",
    "    return answer\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "4568db79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Checking if euclidean_mult_inverses works...\n",
      "Expected = [102,-209], Result = [102, -209]\n",
      "Expected = [-32,17739], Result = [-32, 17739]\n"
     ]
    }
   ],
   "source": [
    "print('Checking if euclidean_mult_inverses works...')\n",
    "print(f'Expected = [102,-209], Result = {euclidean_mult_inverses(543,265)}') #from P5a\n",
    "print(f'Expected = [-32,17739], Result = {euclidean_mult_inverses(54880,99)}') #from P3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1fb59f78",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-6326006621141027858328701602, -2406261620739535241179646240586, 3126421417765788987900034155805]\n",
      "output = 713833790405112718862059213617\n",
      "output % nA = 2461786\n",
      "output % nB = 32328918\n",
      "output % nC = 40602713\n",
      "M = 8937149730.248965038069054102853901352268\n"
     ]
    }
   ],
   "source": [
    "#Problem 5 d)\n",
    "nA = 64652191\n",
    "nB = 53275609\n",
    "nC = 67903951\n",
    "CA = 2461786\n",
    "CB = 32328918\n",
    "CC = 40602713\n",
    "input = [[nA,CA],[nB,CB],[nC,CC]]\n",
    "\n",
    "output = find_CRT_remainder(input)\n",
    "M = decimal_cuberoot(output)\n",
    "\n",
    "print(f'output = {output}')\n",
    "print(f'output % nA = {output % nA}')\n",
    "print(f'output % nB = {output % nB}')\n",
    "print(f'output % nC = {output % nC}')\n",
    "print(f'M = {M}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c3379f51",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "713833790405112718862059213616.9999999950\n"
     ]
    }
   ],
   "source": [
    "#Check to see if root3 is actually the cubed root.\n",
    "print(M ** 3) #It is!"
   ]
  }
 ],
 "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}