#OK to post homework
#Joseph Koutsoutis, 02-25-2024, Assignment 11

read `C11.txt`:

#1 done

#2

#I read the procedure Irreds(q,d,x) and here is the number of irreducible polynomials
#of degree up to 8 over GF(q) for q=2,5,7,11 computed using nops(Irreds(q,d,x)):

# q    deg 1    deg 2    deg 3    deg 4    deg 5    deg 6    deg 7    deg 8
# 2        2        1        2        3        6        9       18       30
# 5        5       10       40      150      624     2580    11160    48750
# 7        7       21      112      588     3360    19544   117648        ?
#11       11       55      440     3630    32208   295020        ?        ?

#(I put a ? in the entries that were taking a while to compute if the previous values
#were enough to find the sequence on OEIS)


#Using the OEIS and these sequences here are the number of irreducible polynomials of deg 20:
#q=2: 52377 (https://oeis.org/A001037)
#q=5: 4768371093720 (https://oeis.org/A001692)
#q=7: 3989613300756720 (https://oeis.org/A001693)
#q=11: 33637499745331128504 (https://oeis.org/A032166)

#I also confirmed that I copied these numbers correctly by computing them using a formula
#covered in math452 (algebra ii):

with(NumberTheory):
compute_num_monic:=proc(p, k) local i,n:
 n := 0:
 for i from 1 to k do:
  if k mod i = 0 then n += p^(k/i)*mu(i): fi:
 od:
 n / k:
end:

#3

MulTable:=proc(q,f,x) local pols,T,p1,p2:
 pols := AllPols(q,degree(f,x)-1, x) minus {0}:
 for p1 in pols do:
  for p2 in pols do:
   T[p1,p2] := Mul(q,p1,p2,x,f):
  od:
 od:
 op(T):
end: 

#The multiplication table outputted from MulTable(2,x^2+x+1,x) matches the one from page 144.

#4

#is_field(q,f,x) takes as input a prime p, a polynomial f, and a variable x.
#It then checks if GF(q)[x]/(f) is a field.
is_field:=proc(q, f, x) local pols,p1,p2,T,inv_exists:
 pols := AllPols(q,degree(f,x)-1, x) minus {0}:
 T := MulTable(q,f,x):
 for p1 in pols do:
  inv_exists := false:
  for p2 in pols do:
   if T[p1,p2] = 1 then inv_exists := true: fi:
  od:
  if not inv_exists then return(false): fi:
 od:
 return(true):
end:

#We confirm using Irreds(3,3,x) that x^3+x^2+x+2 is irreducible.
#Running is_field(3,x^3+x^2+x+2,x) returns true, meaning GF(3)[x]/(f) is a field.

#x^3 is reducible, and running is_field(3,x^3,x) returns false as expected.

#5

#Unless I read the problem incorrectly I think that the NN procedure written in a previous lecture
#accomplishes this.
NearestNeighbor:=proc(C,v):
 NN(C,v)[1]:
end: 

#Here's some code that tests NearestNeighbor for the code generated by M=G24() by encoding random vectors, 
#adding noise in up to three places, and seeing if we can recover the original encoded vector.
#We repeat this experiemnt t times.
test_nearest_neighbor:=proc(t) local M,C,v,v1,rand_place,i:
 M := G24():
 C := LtoC(2, M):
 rand_place := rand(1..24):
 for i from 1 to t do:
  v := Encode(2, M, RV(2, 12)):
  v1 := v:
  v1[rand_place()] += 1:
  v1[rand_place()] += 1:
  v1[rand_place()] += 1:
  v1 := v1 mod 2:
  if NearestNeighbor(C,v1) <> v then print(v): print(NearestNeighbor(C,v1)): return(FAIL): fi:
 od:
 return(SUCCESS):
end:

#I ran test_nearest_neighbor(500) and it passed all of these tests.