path: root/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 03: Page 239"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The quotient when 101 is divided by 11 is 9 = 101 div 11 and the remainder is 2 = 101 mod 11\n"
     ]
    }
   ],
   "source": [
    "#To find the quotient and remainder \n",
    "dividend=101\n",
    "divisor=11\n",
    "quotient=dividend/divisor #To find quotient\n",
    "remainder=dividend%divisor #To find remainder\n",
    "dividend=(divisor*quotient)+remainder\n",
    "print \"The quotient when\",dividend,\"is divided by\",divisor,\"is\",quotient,\"=\",dividend,\"div\",divisor,\"and the remainder is\",remainder,\"=\",dividend,\"mod\",divisor\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 04: Page 240"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The quotient when -11 is divided by 3 is -4 = -11 div 3 and the remainder is 1 = -11 mod 3\n"
     ]
    }
   ],
   "source": [
    "#To find the quotient and remainder\n",
    "dividend=-11\n",
    "divisor=3\n",
    "quotient=dividend/divisor\n",
    "remainder=dividend%divisor\n",
    "dividend=(divisor*quotient)+remainder\n",
    "print \"The quotient when\",dividend,\"is divided by\",divisor,\"is\",quotient,\"=\",dividend,\"div\",divisor,\"and the remainder is\",remainder,\"=\",dividend,\"mod\",divisor\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 01: Page 246"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter a number: 101011111\n",
      "351\n"
     ]
    }
   ],
   "source": [
    "#To convert binary to decimal equivalent\n",
    "binary_num= raw_input('enter a number: ')\n",
    "decimal = 0\n",
    "for digit in binary_num:\n",
    "    decimal = decimal*2 + int(digit)\n",
    "\n",
    "print decimal\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 03: Page 247"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter a number: 2AE0B\n",
      "The conversion of 2AE0B to hexadeimal is 175627\n"
     ]
    }
   ],
   "source": [
    "#To convert decimal to hexadecimal\n",
    "dec= raw_input('enter a number: ')\n",
    "\n",
    "print \"The conversion of\",dec,\"to hexadeimal is\",int(dec,16)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 04: Page 247"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter a number12345\n",
      "The decimal number 12345 is converted to its octal equivalent :  3 0 0 7 1\n"
     ]
    }
   ],
   "source": [
    "#To compute decimal to octal\n",
    "numbers= []\n",
    "dec=input(\"Enter a number\");\n",
    "num=dec\n",
    "while dec!=0:\n",
    "    \n",
    "    rem=dec%8\n",
    "    dec=dec/8\n",
    "    numbers.append(rem)\n",
    "print \"The decimal number\",num,\"is converted to its octal equivalent : \",\n",
    "for i in reversed(numbers):\n",
    "    print i,\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 05: Page 248"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the decimal number which is to be converted to hexadecimal177130\n",
      "The hexadecimal equivalent of decimal 177130 is 0 2 B 3 E A\n"
     ]
    }
   ],
   "source": [
    "#To convert Decimal to hexadecimal\n",
    "num=[]\n",
    "def ChangeHex(n): #function to convert\n",
    "    if (n < 0):\n",
    "        num.append(\"\")\n",
    "    elif (n<=1):\n",
    "        num.append(n)\n",
    "    else: #for numbers greater than 9\n",
    "        x =(n%16)\n",
    "        if (x < 10):\n",
    "            num.append(x) \n",
    "        if (x == 10):\n",
    "            num.append(\"A\")\n",
    "        if (x == 11):\n",
    "            num.append(\"B\")\n",
    "        if (x == 12):\n",
    "            num.append(\"C\")\n",
    "        if (x == 13):\n",
    "            num.append(\"D\")\n",
    "        if (x == 14):\n",
    "            num.append(\"E\")\n",
    "        if (x == 15):\n",
    "            num.append(\"F\")\n",
    "        ChangeHex( n / 16 )\n",
    "dec_num=input(\"Enter the decimal number which is to be converted to hexadecimal\");\n",
    "ChangeHex(dec_num)\n",
    "print \"The hexadecimal equivalent of decimal\",dec_num,\"is\",\n",
    "for i in reversed(num):\n",
    "    print i,\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 06: Page 249"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter a decimal number241\n",
      "\n",
      "The binary equivalent of decimal 241 is 1 1 1 1 0 0 0 1\n"
     ]
    }
   ],
   "source": [
    "#Compute Decimal to Binary\n",
    "array=[]\n",
    "def conv(n):\n",
    "    if n==0:\n",
    "        print ''\n",
    "    else:\n",
    "        array.append(str(n%2)) #to compute remainder and append it to the result\n",
    "        return conv(n/2) \n",
    "dec_num=input(\"Enter a decimal number\")\n",
    "conv(dec_num)\n",
    "print \"The binary equivalent of decimal\",dec_num,\"is\",\n",
    "for i in reversed(array):\n",
    "    print i,\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 06: Page 249"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter the first number: 1110\n",
      "enter the second number: 1011\n",
      "The sum of binary numbers 1110 and 1011 is 11001\n"
     ]
    }
   ],
   "source": [
    "#To compute the binary addition\n",
    "def binAdd(bin1, bin2): #function to add two binary numbers\n",
    "    if not bin1 or not bin2:#checks if both the numbers are binary\n",
    "        return '' \n",
    "\n",
    "    maxlen = max(len(bin1), len(bin2))\n",
    "\n",
    "    bin1 = bin1.zfill(maxlen) #zfill fills with zero to fill the entire width\n",
    "    bin2 = bin2.zfill(maxlen)\n",
    "\n",
    "    result  = ''\n",
    "    carry   = 0\n",
    "\n",
    "    i = maxlen - 1\n",
    "    while(i >= 0):\n",
    "        s = int(bin1[i]) + int(bin2[i])#adding bit by bit\n",
    "        if s == 2: #1+1\n",
    "            if carry == 0:\n",
    "                carry = 1\n",
    "                result = \"%s%s\" % (result, '0')\n",
    "            else:\n",
    "                result = \"%s%s\" % (result, '1')\n",
    "        elif s == 1: # 1+0\n",
    "            if carry == 1:\n",
    "                result = \"%s%s\" % (result, '0')\n",
    "            else:\n",
    "                result = \"%s%s\" % (result, '1')\n",
    "        else: # 0+0\n",
    "            if carry == 1:\n",
    "                result = \"%s%s\" % (result, '1')\n",
    "                carry = 0   \n",
    "            else:\n",
    "                result = \"%s%s\" % (result, '0') \n",
    "\n",
    "        i = i - 1;\n",
    "\n",
    "    if carry>0:\n",
    "        result = \"%s%s\" % (result, '1')\n",
    "    return result[::-1]\n",
    "bin1 = raw_input('enter the first number: ')\n",
    "bin2 = raw_input('enter the second number: ')\n",
    "print \"The sum of binary numbers\",bin1,\"and\",bin2,\"is\",binAdd(bin1,bin2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 02: Page 258"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number for which the prime factors have to be found100\n",
      "[2, 2, 5, 5]\n"
     ]
    }
   ],
   "source": [
    "#to find the prime factors\n",
    "\n",
    "def prime_factors(n):\n",
    "    i = 2\n",
    "    factors = []\n",
    "    while i * i <= n:\n",
    "        if n % i: #modulp division to check of the number is prime or not\n",
    "            i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i) #append those numbers which readily divides the given number\n",
    "    if n > 1:\n",
    "        factors.append(n)\n",
    "    return factors\n",
    "number=input(\"Enter the number for which the prime factors have to be found\");\n",
    "a=prime_factors(number)\n",
    "print a\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 03: Page 258"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number101\n",
      "101 is prime\n"
     ]
    }
   ],
   "source": [
    "#To say if a number is prime or not\n",
    "globals() ['count']=0\n",
    "n=input(\"Enter the number\");\n",
    "for i in range(2,n):#number thats not divisible by other than one and itself.  so from 2 to n (n-1 in python for loop)\n",
    "    if n%i==0:\n",
    "       count=count+1\n",
    "       num=i\n",
    "if count==0:\n",
    "     print n,\"is prime\" \n",
    "else:\n",
    "    print n,\"is not prime because its divisible by\",num\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 04: Page 259"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the number for which the prime factors have to be found7007\n",
      "[7, 7, 11, 13]\n"
     ]
    }
   ],
   "source": [
    "#to find the prime factors\n",
    "\n",
    "def prime_factors(n):\n",
    "    i = 2\n",
    "    factors = []\n",
    "    while i * i <= n:\n",
    "        if n % i: #modulp division to check of the number is prime or not\n",
    "            i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i) #append those numbers which readily divides the given number\n",
    "    if n > 1:\n",
    "        factors.append(n)\n",
    "    return factors\n",
    "number=input(\"Enter the number for which the prime factors have to be found\");\n",
    "a=prime_factors(number)\n",
    "print a\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 10: Page 263"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the first number24\n",
      "Enter the second number36\n",
      "GCD( 24 , 36 ) is 12\n"
     ]
    }
   ],
   "source": [
    "#To compute GCD\n",
    "def gcd(a,b):#fuction computes gcd\n",
    "    if b > a:\n",
    "        return gcd(b,a)\n",
    "    r = a%b\n",
    "    if r == 0:\n",
    "        return b\n",
    "    return gcd(r,b)\n",
    "n1=input(\"Enter the first number\");\n",
    "n2=input(\"Enter the second number\");\n",
    "print \"GCD(\",n1,\",\",n2,\") is\",gcd(n1,n2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 11: Page 263"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the first number17\n",
      "Enter the second number22\n",
      "GCD( 17 , 22 ) is 1\n"
     ]
    }
   ],
   "source": [
    "#To compute GCD\n",
    "def gcd(a,b):#fuction computes gcd\n",
    "    if b > a:\n",
    "        return gcd(b,a)\n",
    "    r = a%b\n",
    "    if r == 0:\n",
    "        return b\n",
    "    return gcd(r,b)\n",
    "n1=input(\"Enter the first number\");\n",
    "n2=input(\"Enter the second number\");\n",
    "print \"GCD(\",n1,\",\",n2,\") is\",gcd(n1,n2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 16: Page 268"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the first number414\n",
      "Enter the second number662\n",
      "gcd( 414 , 662 )is 2\n"
     ]
    }
   ],
   "source": [
    "#to find gcd using euclidean algorithm\n",
    "def gcd(a,b):#euclidean algithm definition\n",
    "    x=a\n",
    "    y=b\n",
    "    while y!=0:\n",
    "        r=x%y\n",
    "        x=y\n",
    "        y=r\n",
    "    print \"gcd(\",a,\",\",b,\")is\",x\n",
    "num1=input(\"Enter the first number\");\n",
    "num2=input(\"Enter the second number\");\n",
    "gcd(num1,num2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 17: Page 270"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the first number252\n",
      "Enter the second number198\n",
      "gcd( 252 , 198 )is 18\n"
     ]
    }
   ],
   "source": [
    "#to find gcd using euclidean algorithm\n",
    "def gcd(a,b):#euclidean algithm definition\n",
    "    x=a\n",
    "    y=b\n",
    "    while y!=0:\n",
    "        r=x%y\n",
    "        x=y\n",
    "        y=r\n",
    "    print \"gcd(\",a,\",\",b,\")is\",x\n",
    "num1=input(\"Enter the first number\");\n",
    "num2=input(\"Enter the second number\");\n",
    "gcd(num1,num2)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}