Open in CoCalc
##############################################################################
###
### MATH 201 FALL 2017 SAGEMATH (COCALC) PYTHON EXAMPLES
###
###############################################################################

#
#      use the toolbar button to the right of the large letter A to go to the line indicated.
#
#
#     57  Birthday problem
#     79  Pascal's Triangle
#    123  Prime numbers and modular arithmetic
#    180  Mod m multiplication, etc. tables
#    216  Euclidean algorithm
#    317  RSA baby examples


nDays =365
listOfDays = [1..nDays]

classSize =25

nTrials = 1000
successCount =0
for _ in range(nTrials):
#make a random sample of dates of size classSize
sample=[]
for _ in range(classSize):
index=randint(0,nDays-1)
sample.append(listOfDays[index])
successCount += len(sample)>len(set(sample))
successCount


558


p=[[1],[1,1]]
r = 12
for _ in range(r):

previousRow=p[-1]
l = len(previousRow)
newRow =[1]
for k in range(l-1):
newRow.append(previousRow[k]+previousRow[k+1])
newRow.append(1)
p.append(newRow)

p

for r in p:
print r

[1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] [1, 6, 15, 20, 15, 6, 1] [1, 7, 21, 35, 35, 21, 7, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1]
p=[[1],[1,1]]
m = 2
r = 15
for _ in range(r):

previousRow=p[-1]
l = len(previousRow)
newRow =[1]
for k in range(l-1):
newRow.append(mod(previousRow[k]+previousRow[k+1],m))
newRow.append(1)
p.append(newRow)

for r in p:
print r

[1] [1, 1] [1, 0, 1] [1, 1, 1, 1] [1, 0, 0, 0, 1] [1, 1, 0, 0, 1, 1] [1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 0, 0, 0, 0, 0, 1] [1, 1, 0, 0, 0, 0, 0, 0, 1, 1] [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1] [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1] [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1] [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
for r in p:
for v in r:
print v,
print

1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Mod(5, 12)
prime_range(100)
prime_pi(10^6)

5 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 78498
j=8675309
j.is_prime()

True
plot(prime_pi(x),(x,1,1000))

m=[[mod(a^k,17) for k in range(1,17)]for a in range(1,17)]

matrix_plot(m,cmap='seismic', colorbar=true)


j.is_prime()

True
trials = 10000
n = 1000000000
counter = 0
for _ in range(trials):
k = randint(1,n)
k= floor(k)
counter += k.is_prime()
counter

497
prime_pi(10^9)

50847534


m = 7
a = mod(3,7)
a

3
a^67

3
a^5

5
for k in [1..10]:
print k, a^k

1 3 2 2 3 6 4 4 5 5 6 1 7 3 8 2 9 6 10 4
1/a

5
m=15
for r in range(1,m):
data.append([r]+[mod(r*c,m) for c in range(1,m)])

x | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 1 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 | 2 4 6 8 10 12 14 1 3 5 7 9 11 13 3 | 3 6 9 12 0 3 6 9 12 0 3 6 9 12 4 | 4 8 12 1 5 9 13 2 6 10 14 3 7 11 5 | 5 10 0 5 10 0 5 10 0 5 10 0 5 10 6 | 6 12 3 9 0 6 12 3 9 0 6 12 3 9 7 | 7 14 6 13 5 12 4 11 3 10 2 9 1 8 8 | 8 1 9 2 10 3 11 4 12 5 13 6 14 7 9 | 9 3 12 6 0 9 3 12 6 0 9 3 12 6 10 | 10 5 0 10 5 0 10 5 0 10 5 0 10 5 11 | 11 7 3 14 10 6 2 13 9 5 1 12 8 4 12 | 12 9 6 3 0 12 9 6 3 0 12 9 6 3 13 | 13 11 9 7 5 3 1 14 12 10 8 6 4 2 14 | 14 13 12 11 10 9 8 7 6 5 4 3 2 1
m=15
nums = m.coprime_integers(m)
for r in nums:
data.append([r]+[mod(r*c,m) for c in nums])

x | 1 2 4 7 8 11 13 14 +----+----+----+----+----+----+----+----+----+ 1 | 1 2 4 7 8 11 13 14 2 | 2 4 8 14 1 7 11 13 4 | 4 8 1 13 2 14 7 11 7 | 7 14 13 4 11 2 1 8 8 | 8 1 2 11 4 13 14 7 11 | 11 7 14 2 13 1 8 4 13 | 13 11 7 1 14 8 4 2 14 | 14 13 11 8 7 4 2 1


m=7
for r in range(m):
data.append([r]+[mod(r+c,m) for c in range(m)])

+ | 0 1 2 3 4 5 6 +---+---+---+---+---+---+---+---+ 0 | 0 1 2 3 4 5 6 1 | 1 2 3 4 5 6 0 2 | 2 3 4 5 6 0 1 3 | 3 4 5 6 0 1 2 4 | 4 5 6 0 1 2 3 5 | 5 6 0 1 2 3 4 6 | 6 0 1 2 3 4 5
m=24

for r in range(1,m):
data.append([r]+[mod(r^c,m) for c in range(1,m)])

^ | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 | 2 4 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 3 | 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 4 | 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 5 | 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 6 | 6 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 | 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 8 | 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 9 | 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 | 10 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 11 | 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 12 | 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 | 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 14 | 14 4 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 15 | 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 16 | 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 | 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 18 | 18 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 | 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 20 | 20 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 21 | 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 22 | 22 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 23 | 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23
m=24
nums = m.coprime_integers(m)

for r in nums:
data.append([r]+[mod(r*c,m) for c in nums])

x | 1 5 7 11 13 17 19 23 +----+----+----+----+----+----+----+----+----+ 1 | 1 5 7 11 13 17 19 23 5 | 5 1 11 7 17 13 23 19 7 | 7 11 1 5 19 23 13 17 11 | 11 7 5 1 23 19 17 13 13 | 13 17 19 23 1 5 7 11 17 | 17 13 23 19 5 1 11 7 19 | 19 23 13 17 7 11 1 5 23 | 23 19 17 13 11 7 5 1

def EALengthPrint(a,b):
#count number of steps in Euclidean Algorithm
#if a<b then switch em
if a < b:
temp = a
a = b
b = temp

steps =0
r=b
while r>0:
q= floor(a/b)
r = a%b
print('%s=%s*%s+%s'%(a,q,b,r))
temp = b
r = a% b
a = temp
b = r

steps += 1
print('number of steps = %s'%steps)

EALengthPrint(1999,2000)

2000=1*1999+1 1999=1999*1+0 number of steps = 2
def EALengthOut(a,b):
#count number of steps in Euclidean Algorithm
#if a<b then switch em
if a < b:
temp = a
a = b
b = temp

steps =0
r=b
while r>0:
q= floor(a/b)
r = a%b
#print('%s=%s*%s+%s'%(a,q,b,r))
temp = b
r = a% b
a = temp
b = r

steps += 1
return steps

EALengthOut(144,34)

3
n=100000
g=sqrt(2)
float(log(n,g))
lengthData = [EALengthOut(n,k) for k in [1..n]]
histogram(lengthData)
max(lengthData)

33.21928094887362
19
lengthData.index(19)

53532
EALengthPrint(53533,100000)

100000=1*53533+46467 53533=1*46467+7066 46467=6*7066+4071 7066=1*4071+2995 4071=1*2995+1076 2995=2*1076+843 1076=1*843+233 843=3*233+144 233=1*144+89 144=1*89+55 89=1*55+34 55=1*34+21 34=1*21+13 21=1*13+8 13=1*8+5 8=1*5+3 5=1*3+2 3=1*2+1 2=2*1+0 number of steps = 19


n=500000000
x=randint(1,n); y=randint(1,n)
EALengthOut(x,y)


18
matrix_plot(m,figsize=9,origin='lower',cmap='GnBu',colorbar=true)

for x in [1..n]:
for y in [1..n]:
if EALengthOut(x,y)==9:
print x,y

55 89 89 55
m=13
m.coprime_integers(m)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
a=mod(13,60)
a^(-1)

37
13*37

481
n=77

e=17   #encoder exponent
f=53  #decoder exponent

for x in range(n):
y=mod(x^e,n)
print x, y, mod(y^f,n)

0 0 0 1 1 1 2 18 2 3 75 3 4 16 4 5 3 5 6 41 6 7 28 7 8 57 8 9 4 9 10 54 10 11 44 11 12 45 12 13 62 13 14 42 14 15 71 15 16 25 16 17 19 17 18 72 18 19 24 19 20 48 20 21 21 21 22 22 22 23 67 23 24 40 24 25 9 25 26 38 26 27 69 27 28 63 28 29 50 29 30 46 30 31 26 31 32 65 32 33 66 33 34 34 34 35 7 35 36 64 36 37 60 37 38 47 38 39 30 39 40 17 40 41 13 41 42 70 42 43 43 43 44 11 44 45 12 45 46 51 46 47 31 47 48 27 48 49 14 49 50 8 50 51 39 51 52 68 52 53 37 53 54 10 54 55 55 55 56 56 56 57 29 57 58 53 58 59 5 59 60 58 60 61 52 61 62 6 62 63 35 63 64 15 64 65 32 65 66 33 66 67 23 67 68 73 68 69 20 69 70 49 70 71 36 71 72 74 72 73 61 73 74 2 74 75 59 75 76 76 76
43^17

5874403106360420018879553643
mod(54^17, 77)

10
mod(10^53,77)

54
#another baby example
n= 13*67;n

871
e= 31 #public encoder
x= 574
y= mod(x^e,n) #encoded message
y

440
phi = 12*66;phi

792
f = mod(31^(-1),phi);f

511
31*511

15841
float(31*511/792)

20.001262626262626
20*792

15840
mod(440^511,871)

574
#new example
p=61; q= 17
n=p*q; phi= (p-1)*(q-1)
e=19 #encoder exponent
print n, phi

1037 960
#find the decoder
f = mod(1/e, phi);f

859
x= 826 #message
y= mod(x^e,n); y #encoded message

830
#decode message
mod(y^f,n)

826


#homework 9.5.2
mod(1/52,77)

40
(52*40-1)/77

27
gcd(77,52)

1
xgcd(77,52)

(1, 25, -37)

# FERMAT'S LITTLE THEOREM AND ITS FRIENDS

p= 31
a =23
mod(a^(p-1),p)

1
120.next_prime()

127
mod(66666^752272,752273)

1
n=13*127;n

1651
mod(211^1512,n)

1
phi = 12*126;phi

1512
mod(10^phi,n)

1