# Chapter 04: Number Theory and Cryptography¶

## Example 03: Page 239¶

In :
#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 :
#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 :
#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 :
#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 :
#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 :
#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 :
#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 :
#To compute the binary addition
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 :
#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 :
#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 :
#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 :
#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 :
#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 :
#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 :
#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