#OK to post homework
#GLORIA LIU, Mar 21 2024, Assignment 16

read `C17.txt`:

#=====================================#
#1. Read and understand pp. 887-890 (until section 5) of Clifford Cocks' Mathematics and Crytography
#Done

#=====================================#
#2. Write a procedure generalizing SR, call it
#qSR(q,INI,L,n)
#that (i) inputs INI (a list of length L[nops(L)][2] of integers in {0,...,q-1} (ii) a list of pairs 
#[c[i],a[i]] , i=1..r where c is in {1, ..., q-1}, and a[i] are positive integers and a[1]<.. 
#x[t]=c[1]*x[t-a[1]]+ ... + c[r]*x[t-a[r]] mod q

qSR:=proc(q,INI,L,n) local r,i,ng,M:
r:=nops(L):
M:=INI:
while(nops(M)) < n do
 ng:=add(L[i][1]*M[-L[i][2]], i=1..r) mod q:
 M:=[op(M),ng]:
od:
M:
end:

#=====================================#
#3. What are the periods of
#qSR(3,[1,2,1],[[1,2],[2,3]],10000)? 
#qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000)? 
#qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000)? 
#qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000)?

q31:=qSR(3,[1,2,1],[[1,2],[2,3]],10000):
q32:=qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000):
q33:=qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000):
q34:=qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000):

FindPer(q31);
FindPer(q32);
FindPer(q33);
FindPer(q34);

#Answers:
#qSR(3,[1,2,1],[[1,2],[2,3]],10000) period 26 
#qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000) period 744
#qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000) period 3660
#qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000) period 744