Chapter 04: Number Theory and Cryptography

Example 03: Page 239

In [1]:
#To find the quotient and remainder 
dividend=101
divisor=11
quotient=dividend/divisor #To find quotient
remainder=dividend%divisor #To find remainder
dividend=(divisor*quotient)+remainder
print "The quotient when",dividend,"is divided by",divisor,"is",quotient,"=",dividend,"div",divisor,"and the remainder is",remainder,"=",dividend,"mod",divisor

The quotient when 101 is divided by 11 is 9 = 101 div 11 and the remainder is 2 = 101 mod 11

Example 04: Page 240

In [2]:
#To find the quotient and remainder
dividend=-11
divisor=3
quotient=dividend/divisor
remainder=dividend%divisor
dividend=(divisor*quotient)+remainder
print "The quotient when",dividend,"is divided by",divisor,"is",quotient,"=",dividend,"div",divisor,"and the remainder is",remainder,"=",dividend,"mod",divisor

The quotient when -11 is divided by 3 is -4 = -11 div 3 and the remainder is 1 = -11 mod 3

Example 01: Page 246

In [3]:
#To convert binary to decimal equivalent
binary_num= raw_input('enter a number: ')
decimal = 0
for digit in binary_num:
    decimal = decimal*2 + int(digit)

print decimal

enter a number: 101011111
351

Example 03: Page 247

In [5]:
#To convert decimal to hexadecimal
dec= raw_input('enter a number: ')

print "The conversion of",dec,"to hexadeimal is",int(dec,16)

enter a number: 2AE0B
The conversion of 2AE0B to hexadeimal is 175627

Example 04: Page 247

In [6]:
#To compute decimal to octal
numbers= []
dec=input("Enter a number");
num=dec
while dec!=0:
    
    rem=dec%8
    dec=dec/8
    numbers.append(rem)
print "The decimal number",num,"is converted to its octal equivalent : ",
for i in reversed(numbers):
    print i,
    

Enter a number12345
The decimal number 12345 is converted to its octal equivalent :  3 0 0 7 1

Example 05: Page 248

In [7]:
#To convert Decimal to hexadecimal
num=[]
def ChangeHex(n): #function to convert
    if (n < 0):
        num.append("")
    elif (n<=1):
        num.append(n)
    else: #for numbers greater than 9
        x =(n%16)
        if (x < 10):
            num.append(x) 
        if (x == 10):
            num.append("A")
        if (x == 11):
            num.append("B")
        if (x == 12):
            num.append("C")
        if (x == 13):
            num.append("D")
        if (x == 14):
            num.append("E")
        if (x == 15):
            num.append("F")
        ChangeHex( n / 16 )
dec_num=input("Enter the decimal number which is to be converted to hexadecimal");
ChangeHex(dec_num)
print "The hexadecimal equivalent of decimal",dec_num,"is",
for i in reversed(num):
    print i,

Enter the decimal number which is to be converted to hexadecimal177130
The hexadecimal equivalent of decimal 177130 is 0 2 B 3 E A

Example 06: Page 249

In [9]:
#Compute Decimal to Binary
array=[]
def conv(n):
    if n==0:
        print ''
    else:
        array.append(str(n%2)) #to compute remainder and append it to the result
        return conv(n/2) 
dec_num=input("Enter a decimal number")
conv(dec_num)
print "The binary equivalent of decimal",dec_num,"is",
for i in reversed(array):
    print i,

Enter a decimal number241

The binary equivalent of decimal 241 is 1 1 1 1 0 0 0 1

Example 06: Page 249

In [10]:
#To compute the binary addition
def binAdd(bin1, bin2): #function to add two binary numbers
    if not bin1 or not bin2:#checks if both the numbers are binary
        return '' 

    maxlen = max(len(bin1), len(bin2))

    bin1 = bin1.zfill(maxlen) #zfill fills with zero to fill the entire width
    bin2 = bin2.zfill(maxlen)

    result  = ''
    carry   = 0

    i = maxlen - 1
    while(i >= 0):
        s = int(bin1[i]) + int(bin2[i])#adding bit by bit
        if s == 2: #1+1
            if carry == 0:
                carry = 1
                result = "%s%s" % (result, '0')
            else:
                result = "%s%s" % (result, '1')
        elif s == 1: # 1+0
            if carry == 1:
                result = "%s%s" % (result, '0')
            else:
                result = "%s%s" % (result, '1')
        else: # 0+0
            if carry == 1:
                result = "%s%s" % (result, '1')
                carry = 0   
            else:
                result = "%s%s" % (result, '0') 

        i = i - 1;

    if carry>0:
        result = "%s%s" % (result, '1')
    return result[::-1]
bin1 = raw_input('enter the first number: ')
bin2 = raw_input('enter the second number: ')
print "The sum of binary numbers",bin1,"and",bin2,"is",binAdd(bin1,bin2)

enter the first number: 1110
enter the second number: 1011
The sum of binary numbers 1110 and 1011 is 11001

Example 02: Page 258

In [21]:
#to find the prime factors

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i: #modulp division to check of the number is prime or not
            i += 1
        else:
            n //= i
            factors.append(i) #append those numbers which readily divides the given number
    if n > 1:
        factors.append(n)
    return factors
number=input("Enter the number for which the prime factors have to be found");
a=prime_factors(number)
print a

Enter the number for which the prime factors have to be found100
[2, 2, 5, 5]

Example 03: Page 258

In [22]:
#To say if a number is prime or not
globals() ['count']=0
n=input("Enter the number");
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)
    if n%i==0:
       count=count+1
       num=i
if count==0:
     print n,"is prime" 
else:
    print n,"is not prime because its divisible by",num

Enter the number101
101 is prime

Example 04: Page 259

In [23]:
#to find the prime factors

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i: #modulp division to check of the number is prime or not
            i += 1
        else:
            n //= i
            factors.append(i) #append those numbers which readily divides the given number
    if n > 1:
        factors.append(n)
    return factors
number=input("Enter the number for which the prime factors have to be found");
a=prime_factors(number)
print a

Enter the number for which the prime factors have to be found7007
[7, 7, 11, 13]

Example 10: Page 263

In [24]:
#To compute GCD
def gcd(a,b):#fuction computes gcd
    if b > a:
        return gcd(b,a)
    r = a%b
    if r == 0:
        return b
    return gcd(r,b)
n1=input("Enter the first number");
n2=input("Enter the second number");
print "GCD(",n1,",",n2,") is",gcd(n1,n2)

Enter the first number24
Enter the second number36
GCD( 24 , 36 ) is 12

Example 11: Page 263

In [25]:
#To compute GCD
def gcd(a,b):#fuction computes gcd
    if b > a:
        return gcd(b,a)
    r = a%b
    if r == 0:
        return b
    return gcd(r,b)
n1=input("Enter the first number");
n2=input("Enter the second number");
print "GCD(",n1,",",n2,") is",gcd(n1,n2)

Enter the first number17
Enter the second number22
GCD( 17 , 22 ) is 1

Example 16: Page 268

In [26]:
#to find gcd using euclidean algorithm
def gcd(a,b):#euclidean algithm definition
    x=a
    y=b
    while y!=0:
        r=x%y
        x=y
        y=r
    print "gcd(",a,",",b,")is",x
num1=input("Enter the first number");
num2=input("Enter the second number");
gcd(num1,num2)

Enter the first number414
Enter the second number662
gcd( 414 , 662 )is 2

Example 17: Page 270

In [1]:
#to find gcd using euclidean algorithm
def gcd(a,b):#euclidean algithm definition
    x=a
    y=b
    while y!=0:
        r=x%y
        x=y
        y=r
    print "gcd(",a,",",b,")is",x
num1=input("Enter the first number");
num2=input("Enter the second number");
gcd(num1,num2)

Enter the first number252
Enter the second number198
gcd( 252 , 198 )is 18