Sharedmath 201-17FPublicShared.sagewsOpen in CoCalc
Author: Paul Zeitz
Views : 2
############################################################################## ### ### MATH 201 FALL 2017 SAGEMATH (COCALC) PYTHON EXAMPLES ### ############################################################################### ###### TABLE OF CONTENTS # # 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 headerRow=['x']+range(1,m) data=[headerRow] for r in range(1,m): data.append([r]+[mod(r*c,m) for c in range(1,m)]) table(data,header_row=True, header_column=True)
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) headerRow=['x']+nums data=[headerRow] for r in nums: data.append([r]+[mod(r*c,m) for c in nums]) table(data,header_row=True, header_column=True)
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 headerRow=['+']+range(m) data=[headerRow] for r in range(m): data.append([r]+[mod(r+c,m) for c in range(m)]) table(data,header_row=True, header_column=True)
+ | 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 headerRow=['^']+range(1,m) data=[headerRow] for r in range(1,m): data.append([r]+[mod(r^c,m) for c in range(1,m)]) table(data,header_row=True, header_column=True)
^ | 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) headerRow=['x']+nums data=[headerRow] for r in nums: data.append([r]+[mod(r*c,m) for c in nums]) table(data,header_row=True, header_column=True)
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