#Ok to post homework
#Quentin Dubroff, Assignment 23, April 21 2019
with(LinearAlgebra[Modular]):

#Fc(n,K) finds the n-th fibonacci number mod K using repeated squaring
Fc:=proc(n,K) local AA,rep,A,B,m,sum,i,Z:
A:=[[1,1],[1,0]]:
B:=Transpose(K,Mod(K,Matrix([1,0]),integer[])):
m:=ceil(log[2](n+1)):
sum:=0:
for i from 1 to m do
	if (2^(m-i)+sum)<=n-1 then
		sum:=sum+2^(m-i):
		rep[i]:=1:
	else
		rep[i]:=0:
	fi:
od:
for i from 1 to m do
	if rep[i]=1 then 
		AA[i]:=Mod(K,RepSquare(A,m-i,K),integer[]):
	else:
		AA[i]:=Mod(K,Matrix([[1,0],[0,1]]),integer[]):
	fi:
od:
Z:=Mod(K,Matrix([[1,0],[0,1]]),integer[]):
for i from 1 to m do
	Z:=Multiply(K,Z,AA[i]):
od:
Multiply(K,Z,B)[1][1]:
end:

#RepSquare takes in a matrix A and returns A^(2^n)
RepSquareK:=proc(A,n,K) local AA:
option remember:
AA:=Mod(K,Matrix(A),integer[]):
if n=0 then 
	RETURN(AA):
fi:

Mod(K,Multiply(K,RepSquare(AA,n-1,K),RepSquare(AA,n-1,K)),integer[]):

end:


#Tc(n,K) finds the n-th tribonacci number mod K
Tc:=proc(n,K) local AA,rep,A,B,m,sum,i,Z:
A:=[[1,1,1],[1,0,0],[0,1,0]]:
B:=Transpose(K,Mod(K,Matrix([1,0,0]),integer[])):
m:=ceil(log[2](n+1)):
sum:=0:
for i from 1 to m do
	if (2^(m-i)+sum)<=n-1 then
		sum:=sum+2^(m-i):
		rep[i]:=1:
	else
		rep[i]:=0:
	fi:
od:
for i from 1 to m do
	if rep[i]=1 then 
		AA[i]:=Mod(K,RepSquare(A,m-i,K),integer[]):
	else:
		AA[i]:=Mod(K,Matrix([[1,0,0],[0,1,0],[0,0,1]]),integer[]):
	fi:
od:
Z:=Mod(K,Matrix([[1,0,0],[0,1,0],[0,0,1]]),integer[]):
for i from 1 to m do
	Z:=Multiply(K,Z,AA[i]):
od:
Multiply(K,Z,B)[1][1]:
end:


#Tc(n,K) successfully computes the tribonacci numbers mod K, but for some
#reason gets stuck computationally around 10^7 (this is also true for
#the Fc function). I believe the problem is that the modular matrix 
#multiplication in maple is evaluating the mod too late in the process,
#but I haven't been able to fix it.