Last Update: April 25, 2024

• Teacher: Dr. Doron ZEILBERGER ("Dr. Z")

• Classroom: Allison Road Classroom Building [Busch Campus], IML Room ARC 118

• Time: Mondays and Thursdays, period 3 (12:10-1:30pm)

• Dr. Zeilberger's Email: DoronZeil at gmail dot com ; Official Email: zeilberg@math.rutgers.edu
  
• Dr. Zeilberger's e Office Hours (Spring 2024): MTh 10:50-11:50am
  

Description

Experimental Mathematics used to be considered an oxymoron, but the future of mathematics is in that direction. In addition to learning the philosophy and methodology of this budding field, students will become computer-algebra wizards, and that should be very helpful in whatever mathematical specialty they are doing (or will do) research in.

We will first learn Maple, and how to program with it. This semester we will learn, from an experimental mathematics point of view, Coding Theory and Cryptography. The final projects may lead to published papers. People who already took previous editions of this class are welcome to take it again, since except for the basics, there is very little overlap with previous years.

This class is suitable for graduate students in other departments, and the software development skills learned will be useful for doing any quantitative research. Very smart advanced undergraduates are also welcome. In particular, the methods learned for researching Coding Theory and Cryptography should be applicable almost everywhere.

The projects (a text file: projX.txt, and a write-up and/or puzzle book, projX.pdf) are due, May 1, 2024, 11:00pm.

Note: instead of a final exam students will give presentations (and demos) of their projects in a WebEx session to happen on May 2, 2024, 12:00-2:30 pm (with a break of 15 minutes in the middle). These will be recorded (with the speakers' permission), and posted in this website.

Texts

• The wonderful book: A First Course in Coding Theory by Raymond Hill

• Normal Levinson's defense of Applied Mathematics

• Srinivasa Ramanujan's seminal paper

• Clifford Cocks' insightful and lucid summary of Mathematics and Crytography scanned from the Princeton Companion of Mathematics.

• These nice Yale lecture notes by Ewa Syta (instructor: Michael Fischer)

• The nice book A course in cryptography, by Rafael Pass and Abhi Shelat

• Marcel Golay's seiminal paper

• Digital Signatures, engaging lecture notes by Cole Watson.

• geeksforgeeks article on DES

• Manuel Blum's article on Zero-Knowledge proofs

• Hadas Zeilberger's simple explanation of Zero-Knowledge proofs

• Peter Shor's seminal paper

Optional (but Highly recommended) Getting Started Homework

For more details, see this 2002 masterpiece.

How to submit homework

• Every class has a homework assignment. Both Mondays and Thursdays' are due 8:00pm Sunday of the following week.

  It should be sent to the email address

  ShaloshBEkhad at gmail dot com

  Subject: HomeWork#X

  and then attach a .txt file(s) called

  hwXYourFirstNameYourLastName.txt

  where X is the number of the assignment

  Except for the first assignment, you should have two attached .txt files.

  For example, when David Hilbert submits homework assignments 2 and 3, he should email ShaloshBEkhad at gmail dot com, with

  Subject: HomeWork#2#3

  and attach the text files (the source code plus human comments (such lines must start with #)

  hw2DavidHilbert.txt and hw3DavidHilbert`.txt

• The very first line of the .txt files should have

  #Please do not post homework
  or
  #OK to post homework

  Followed by
  #Your Name, Date, Assignment X

Programs done on Thurs., Jan. 18, 2024

• CC(P,k1): Implements the Ceaser code Inputs a message, given a list of characters, P (in lower case) and an integer k from 0 to 25, outputs the encrypted message For example CC([d,o,r,o,n],2); should output [f,q,t,q,p]

• SC(P,pi): Inputs a message, given a list of characters, P (in lower case) and a permutation pi of outputs the encrypted message where the letter A[i] goes to A[pi[i]] For example
  SC([d,o,r,o,n],[2,3,4,...., 25,1]); should output []

• InvPi(pi): The inverse of the permutation pi. For example InvPi([2,3,4,1]) is [4,1,2,3]

Homework for Thurs., Jan. 18, 2024, class (due Sunday Jan. 21, 8:00pm)

Subject: HomeWork#1

and an attachment

hw1FirstNameLastName.txt

and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in the first 30 pages of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everyone!] Read and (try to understand) the seminal Rivest-Shamir-Adleman paper.

3. [Optional (but strongly recommended) to novices, mandatory for experts]

   Generalize procedure CC(P,k) call it CCg(P,A,k) that inputs an arbitrary "alphabet" (e.g. [0,1,...,9], [C,A,G,T]) given as a list and encodes it.
   CCg(P,[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z],k)
   should give the same output as CC(P,k). In addition it should check that all the members of the plaintext, P, belong to A, and return FAIL if it doesn't.

4. [Optional BIG challenge to novices; Mandatory for experts]

   Using the file ENGLISH.txt

   (Download it to your computer and read it, ENG()[5], for example is the list of 5-letter words)

   Creates the lists T[i,j] (3 ≤ i ≤ 10, 1 ≤ j ≤ i) each of length 26, where T[i,j][i1] is the frequency of the i1-th letter of the English alphabet in the j-th place of an i-letter word. Also create s list, call it, F of the total frequency (only using from 3-letter words to 10-letter words) in the whole text. Can you find any differences?
   

Added Jan. 21, 2024: read the students' nice solutions in this directory.

Programs done on Monday., Jan. 22, 2024

• NextPrime1(n): inputs a pos. integer n and outputs the first prime >=n

• MakeRSAKey(D1): creates an RSA key [n,e] (under consturction, so far it only gives n) The RSA encrypton is

  a -> a^e mod n

  (n must be a product of two primes). Inputs D1 and outputs an RSA key [n,e], where n is a product of two primes with D1 digits. Try: MakeRSAkey(100);

  [e is coming up next time]

• ME1s(a,e,n): a^e mod n, the stupid way

• ME1(a,e,n): a^e mod n,the smart way

Homework for Monday, Jan. 22, 2024, class (due Sunday Jan. 28, 8:00pm)

Subject: HomeWork#2 (if possible Homework#2#3)

and an attachment(s)

hw2FirstNameLastName.txt (and if possible together with hw3FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in pages 30-60 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [For everyone]
   Read and understand this lecture note. Make up similar excercises but with much bigger number, and use Maple as a "calculator".

3. [Optional for novices, mandatory for expects]

   I. Write a procedure

   MyIfactor(n)

   that inputs a positive integer and outputs a list of its prime factors (with repetition), in weakly increasing order. For example, MyIfactor(100) should output [2,2,5,5].

   [Hint, If n=1 the output is the empty list. Now find the smallest prime divisible by n (by either using nextprime, or ithprime in the numtheory Maple package). Call it p. Then recursively find the output of MyIfactor(n/p), getting some list, and then output a longer list where the first entry is p followed by the entries of the output of MyIfactor(n/p)]

   II. Test your home-made procedure against Maple ifactor. Using the time() command, find out who is better (probably Maple's ifactor), and by how much.

Added Jan. 28, 2024: read the students' nice solutions in this directory.

Programs done on Thursday, Jan. 25, 2024

• MakeRSAkey: The key [n,e,d]: n must be a product of two primes inputs D1 and outputs an RSA key [n,e,d], where n is a product of two primes with D1 digits (and the encrption is
  a GOES TO a^e mod n

  and the decrypton is
  a GOES TO a^d mod n

  Try:
  MakeRSAkey(100);

• EA(m,n): inputs m > n and outputs the gcd(m,n) (homemade version, using recursion)

• [Added after class]

  EAnew(m,n): inputs m > n and outputs, the gcd(m,n) (homemade version, using iteration rather then recursion)

Homework for Thursda, Jan. 25, 2024, class (due Sunday Jan. 28, 8:00pm)

Subject: HomeWork#3 (if possible Homework#2#3)

and an attachment(s)

hw3FirstNameLastName.txt (and if possible together with hw2FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in pages 61-90 of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. [Mantaory for experts, strongly recommended for novices] Look at the Maple procedure
   EAnew(m,n)
   that I added after class, and compare it with Maple's gcd(m,n) and EA(m,n). Why is EAnew better?
   Also run several time, in a Maple session (once you read C3.txt):

   a:=rand(10^50000..10^50001)(): b:=rand(10^50000..10^50001)(): time(gcd(a,b)); time(EAnew(a,b));

   who is faster? Why? (I am not sure of the answer myself)

3. [Mantaory for experts, strongly recommended for novices]
   Write a procedure

   EstimateProbGCD(N,K)

   that estimates the probability (given in floating point) that two randomly chosen integers between 1 and N are relatively prime, by doing the experiment K times. What did you get for

   EstimateProbGCD(10^10,10^4)

   Run it several times, and see whether the answers are close.

4. [Optional challenge, 5 dollars]. Find the exact value of the limit of this probability as N goes to infinity

5. [Mantaory for experts, strongly recommended for novices]

   Write a procedure

   MakeRSAkeyG(D1,g);

   that takes n (the modulus) to be a product of g distinct primes (MakeRSAkeyG(D1,2) should do the same as MakeRSAkey(D1))

   Why is, for example, MakeRSAkey(D1,3) less secure?

6. [Optional Challenge, 10 dollars to be divided among all correct solutions]

   Carefully read section IV of the seminal Rivest-Shamir-Adleman paper, about digital Signatures, and implement it, using the RSA encrypton.

7. [Reading homework for everyone]

   Get ready for the next class (starting Coding theoy) by reading Chapter I of
   A First Course in Coding Theory by Raymond Hill

Added Jan. 28, 2024: read the students' nice solutions in this directory.

Programs done on Monday, Jan. 29, 2024

• Fqn(q,n): {0,1,...,q-1}^n

• HD(u,v): The Hamming distance between two words (of the same length)

• SPB(q,n,d): The best you can hope for (as far as the size of C) for q-ary (n,2*t+1) code, in other words, the Sphere-packing bound

• RV(q,n): A random word of length n in {0,1,..,q-1}

• RC(q,n,d,K): inputs q,n,d, and K and keeps picking K+1 (thanks to Nuray) random vectors whenver the new vector is not distance <=d-1 from all the previous one

Homework for Monday, Jan. 29, 2024, class (due Sunday Feb. 4, 2024, 8:00pm)

Subject: HomeWork#4 (if possible Homework#4#5)

and an attachment(s)

hw4FirstNameLastName.txt (and if possible together with hw5FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.

1. [People who took this class before, or already know Maple, are excempt from this] Read and do all the examples, plus make up similar ones, in pages 91-end of Frank Garvan's awesome Maple booklet ( part 1, part 2)
   Only record a small sample in hw1YourName.txt .

2. Inspired by Exercise 1.1 of Raymond Hill's book (p. 10) (there is an answer at the end of the book) form a matrix with 0-1 whose number of rows and number of columns are both prime numbers and "draw" your initials (in my case e.g. DZ) such that the 1's will show it. (and the 0-th are the background). Then turn it into a 1-dimensional vector.

3. Uee RC(q,n,d,K) with q=2, d=3,5,7, and 5 ≤ n ≤16 and K very big (say 10000), and each time run it several times and pick the one with the most elements (to get M as big as possible). How do the codes that you got compare to the best possible values in table 2.4 on p.14 of Hill's book?

4. [Corrected Feb. 1, 2024]
   The binary Hamming codes (to be studied later) have n=2^r-1 (where r is a positive integer), and minimal distance 3. They are known to be perfect. How big are they? (i.e. what is there M?) (Hint: use the Sphere Packing Bound)

Added Feb. 4, 2024: read the students' nice solutions in this directory.

Programs done on Thurs., Feb. 1, 2024

• BDfano(): The block design that comes from the Fano plane, {{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}

• BDex212(): The (11,5,2) symmetric block design mentioned in Ex. 2.12 of Hall's book (p. 27), namely {{1,3,4,5,9},{2,4,5,6,10},{3,5,6,7,11},{1,4,6,7,8},{2,5,7,8,9},{3,6,8,9,10},{4,7,9,10,11},{1,5,8,10,11},{1,2,6,9,11},{1,2,3,7,10},{2,3,4,8,11}}

• Nei(q,c): all the neighbors of the vector c in Fqn(q,n)

• SP(q,c,t): the set of all vectors in Fqn(q,n) whose distance is <=t from c

• GRC(q,n,d): Using the greedy algorithm to generate q-ary code with the given n and minimal distance d. For example GRC(2,7,3) gives (a code equivalent) the Hamming code (to be studied later) with n=7, M=16, and d=3. More impressively, GRC(2,15,3) gives the Hamming code with n=15 and

• MinD(C): The minimal (Hamming) distance of the code C

• BDtoC(BD,n): uses the block design ( a certain collection of finite sets with special property (see Hall's book, p.21) to generate a good code. For example try BDtoC(BDfano(),7); and BDtoC(BDfano(),7); and BDtoC(BDex212(),11);

Homework for Thursday, Feb. 1, 2024, class (due Sunday Feb. 4, 2024, 8:00pm)

Subject: HomeWork#5 (if possible Homework#4#5)

and an attachment(s)

hw5FirstNameLastName.txt (and if possible together with hw4FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.>

1. [For everyone] Read and understand Chapter 2 of Hill's book. Do human exercises 2.1,2.2,2.3,2.4

2. [For everyone] Read and understand Chapters 3 and 4 of Hill's book. Most people should be familar with this material from abstract algebra and linear algebra classes (note that the linear algebra is the same, but over a finite field)

3. [For everyone] Use GRC(q,n,d) with q=2, d=3,5,7, and 5 ≤ n ≤20, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

4. [For everyone] Use GRC(q,n,d) with q=3, d=3,5,7, and 5 ≤ n ≤10, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

5. [For everyone] USe GRC(q,n,d) with q=5, d=3,5,7, and 5 ≤ n ≤7, for each case find the cardinality of the code (what's called M in the book). Also find the Sphere-Packing Bound. How far are they in each case?

6. [Mandatory for experts, optional but stronlgy recommended for novices]
   Write a procedure ParaBD(BD,v), that inputs a potential block design with v varieties (or points) (i.e. the universal set is {1, ..., v}) and checks whether it is indeed a block design (if it is not it should return FAIL). If it is the output should be the 5-tuple

   [b,v,r,k,lambda]

   (see the bottom of p. 21) Check your program with the following
   ParaBD(BDfano(),7); and ParaBD(BDex212(),11);

   Hint added Feb. 4, 2024, 2:25pm: First construct the incidence matrix (a certain 0-1 matrix), (like in Fig. 2.22) of the block design where the rows are labelled by the points and the columns by blocks. b is just nops(BD) (it always exists). Then check that (1) the row sums are all the same. If not return FAIL, otherwise you got got your r. (2) the column sums are all the same. If not, return FAIL, otherwise your got your k. (3) The dot product of all (distinct) pairs of rows are all the same. If not, return FAIL, otherwise, you got your λ.

7. [For everyone, modified Feb. 2, thanks to Lucy Martinez]
   Using Ex. 2.21 (p. 29) write a procedure

   PlotkinBound(n,d)

   For binary codes. For all d from 2 to 20 and n from 2 to 2d find which is bigger, the Sphere-Packing bound or the Plotkin bound?

8. [Optional challenge, I don't know the answer, 10 dollars to be divided]
   Search the internet for other examples of block designs (or the special case, projective plane) given explictly as a collection of subests of {1, ..., n} for some n (like BDfano() and BDex212()), and use BDtoC(BD,n) to come up with interesting codes.

Added Feb. 4, 2024: read the students' nice solutions in this directory.

Programs done on Monday, Feb. 5, 2024

• LtoC(q,M): inputs a list of basis vectors for our linear code over GF(q) outputs all the codewords (the actual subset of GF(q)^n with q^k elements

• MinW(q,M): The minimal weight of the Linear code generated by M over GF(q)

Homework for Monday, Feb. 5, 2024, class (due Sunday Feb. 11, 2024, 8:00pm)

Subject: HomeWork#6 (if possible Homework#6#7)

and an attachment(s)

hw6FirstNameLastName.txt (and if possible together with hw7FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.

1. [For everyone]
   Read and understand chapter 5 of Raymond Hill's book. In particular Lemma 2.

2. [For everyone, human exercise] do (without peeking at the answers at the end of the book, but it is OK to check your answers once you did your best) excercies 5.1, 5.2, 5.3, 5.5 (p. 53).

3. [For everyone]
   Write a program

   SearchLC(q,n,k,K)

   That inputs q and n for GF(q)^n, and k (for the dimension of the linear code, a certain subspace of GF(q)^n) and a very large positive integer K (say 1000) and keeps generationg, K times, random lists, M, of k members of GF(q)^n, for each determines MinW(q,M) and outputs the one with the largest minimum weight.

   Run it, with K=1000 for q=2,3,5   ;   4 ≤ n ≤ 10   ;   ; and 3 ≤ k ≤ 5 .

4. [Mandatory for experts, optional, but highly recommended challenge for novices. The best code will get 5 dollars and be incorporated in C8.txt (with due credit)]
   Write a porgram (all by yourself, (not using the Maple Linear Algebra package)

   SF(q,M)

   that inputs q (for GF(q)^n) a generating matrix M ( a list of vectors of lenght n in GF(q)^n), and k=nops(M), and outputs the matrix in statdard form, i.e. of the from

   [I_k|A]

   where I_k is the k by k identity matrix and A is k by (n-k) matrix.

   [Hints: 1. don't forget to use modular arithmetic (mod q) and remember that the reciprocal of a is a&^(-1) mod q 2. You are welcome to write small subroutines for the various row and column operations in Gaussian elimination before writing the main program.]

Added Feb. 11, 2024: read the students' nice solutions in this directory.

Programs done on Thurs., Feb. 8, 2024

• [added Feb. 12, 2024, from challenge to hw6, code by Daniel Elwell who won 5 dollars]

  SFde(q,M): inputs a matrix M over GF(q) (as a list of lists) and outputs its standard form. Note that the linear code generated by the new matrix is not always the same, but it is an equivalent code.

• NN(C,v): the set of members of C closest to the vector v (assuming that C is a subset of Fqn(q,n) for some q with n=nops(v))

• DecodeT(q,n,C): Constructs once and for all a table that sends every member of Fqn(q,n) to one of its nearest neighbor

• GLC1(q,M,d): tries to add a new member to the current basis M out of the other vectors in GF(q)^n such that if you append it to the basis the resulting linear code still has min. weight d

• GLC(q,n,d): inputs q and n and d (for min. distance) greedily and randomly tries to get as large a linear code given by a basis as possible)

• [Added Feb. 12, 2024, code by Aurora Hiveley, who co-won 5 dollars]
  SAah(q,n,M): inputs a basis M of a linear [n,nops(M),d] code (for some d), outputs Slepian's Standard Array as a matrix of vectors containing all the vectors in GF(q)^n (alias Fqn(q,n)) such that the first row is an ordering of the members of the actual code (LtoC(q,M)) with [0$n] the first entry and the first columns are the coset reprenatives

Homework for Thursday, Feb. 8, 2024, class (due Sunday Feb. 11, 2024, 8:00pm)

Subject: HomeWork#7 (if possible Homework#6#7)

and an attachment(s)

hw7FirstNameLastName.txt (and if possible together with hw6FirstnameLastName.txt)

and indicate whether it is OK to post. unless you say "OK to post", it will be not posted.

1. [For everyone] Read and understand pp. 55-60 of Chapter 6 of the book. Optionally, read (or at least skim) pp. 60-65. Do a first reading of pp. 67-71.

2. [5 dollars to be divided among all correct solutions] p. 59, lines 7 and 8 from the bottom (that start with (a) and (b)) has two typos. Find them!

3. [for everyone] using Maple's rand(1..n) command write a procedure

   LC(N)

   that inputs a positive integer N, larger than 1, and outputs 1 with probability 1/N and 0 otherwise

   For example, LC(10) should output 1 about one tenth of the times.

   Test it out by doing
   add(x[LC(10)],i=1..10000);
   and make sure that it is close to 1000*x[1]+9000*x[0]
   [Hint: use rand(1..N)() and output 1 it is 1, and 0 otherwise]

4. [for everyone]

   Write a procedure

   TestCode(q,n,C,N,K)

   that inputs a code q-ari code,C, on n letters (a subset of GF(q)^n, a positive integer N and a large positive integer K and K times does the following

   • Constructs, once and for all the table

     T:=DecodeT(q,n,C) :

   • Picks a random member v, of C

     for each component of v, with probabiliy 1/N, changes it (you can add 1 mod q), getting a (possibly) distorted vector v1.

     See whether T[v1]≠ v. If it is add it to the counter

   • output evalf(co/K)

5. With the above program, run it with q=2, n=7, K=10000, C=GRC(2,7,3) and
   N=2,3,4,5,6,7,8,9,10,15,20,30
   What were the failure rates for each choice of N above?

6. [Mandatory for experts, strongly recommended for novices. 5 dollar prize for the best code that will be part of this class corpus and would make it to C8.txt]

   Finish procedure SA(q,n,M) that we just started. Test it with
   q=2,n=4, M=[[1,0,1,1],[[0,1,0,1]]
   and see whether you get tge sane as the standard array for the small code in Example 6.6 on p. 59 of Hill's book (make sure that your top row agrees with his.

Added Feb. 11, 2024: read the students' nice solutions in this directory.

Special Homework due Wed., Feb. 14, 8:00pm

Subject: hwValentine

and an attachment

hwValentineFirstNameLastName.txt

1. Use Maple's graphics to draw a nice Valentine, if possible a cardiodid (or other Valentine-like shape) with the iside an encryption of the sentence

   I LOVE CODING THEORY

   but using Caesar Code with a (positive) shift that is your age (if you are over 25, make it mod 26, if you are 26 make it 1). Submit two files: ValentineFirstLast.txt (for the Maple code), and ValentineFirstLast.jpg (for the picture).

   The best valentine will win a chocolate box on Feb. 15

   The Valentines will be in a special directory and every student should rank each valentine (in a form that I will email you) from 0 to 10. Please rank your own valentine 5. The top scorer, by popular vote, would win the chocolate box.

   Please use the following Evaluation form , replacing the X's by the score (0 if the person does not appear in the directory and 5 for yourself).

   ---

   Programs done on Mon., Feb. 12, 2024

   C8.txt , Contains procedures (in addition to those from C4.txt, C5.txt, C6.txt, and C7.txt that are mentioned in Help4();, Help5();,Help6();, and Help7();)
   • PCM(q,M): inputs the mod. q and a non-empty basis (a list of lists) n=nops(M[1]) M is k by n matrix and H=PCM(q,M) is an n-k by n matrix describing the basis of some linear code over GF(q)^n outputs of dimension k=nops(M) the (n-k) by n

   • DP(q,u,v): The dot-product of vectors u and v (assumed of the same length) mod q

   • Syn(q,H,y): The syndrom of the received vector y if the Parity-Check-Matrix (PCM) is H

   Homework for Monday Feb. 12, 2024, class (due Sunday Feb. 18, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#8 (if possible Homework#8#9)

   and an attachment(s)

   hw8FirstNameLastName.txt (and if possible together with hw9FirstnameLastName.txt)

   1. Write a Maple procedure

      WtEnumerator(q,M,t)

      that inputs a generating matrix M (with k rows say, so so it is an [n,k,d] code for some d )for a linear code over GF(q) (q prime) and outputs the

      Sum(t^wt(v), v in C)

      over all the q^d vectors v in the code (including the zero-vector of weight 0)

   2. [Challenge, 5 dollars, please do not "peek" at the book or the internet, try to discover it by experimenting]

      Find a relation between WtEnumerator(q,M,t) and WtEnumerator(q,H,t) where H is the PCM(q,M) (and hence a generating matrix for the dual code). First do it for q=2, then for other q, and try to discover the relation (if it exists)

      Added Feb. 20, 2024: Congratulations to Joseph Koutsoutis for meeting this challenge brilliantly. He won ten dollars for rediscovering, experimentally, the fundamental MacWilliams Identity, also covered in Chapter 13 of Raymond Hill's book.

   Added Feb. 18, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., Feb. 15, 2024

   C9.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, and C8.txt, that are mentioned in Help4();, Help5();,Help6();, and Help7();, and Help8();)
   • SynT(q,M): inputs q and a basis (in standard form) M of some linear code over GF(q) outputs the syndrom table mapping each possible syndorm to its correponding coset leader in its standard array.

   Homework for Thursday Feb. 15, 2024, class (due Sunday Feb. 18, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#9 (if possible Homework#8#9)

   and an attachment(s)

   hw9FirstNameLastName.txt (and if possible together with h8FirstnameLastName.txt), BUT not the same file.

   1. By looking at the beautiful valentines figure out the age of each of the creators (recall that 26 and 27 yield the same coded message). Also make sure that the authors consistently used the Caesar code.

   2. [For everyone, among the correct answers one will be picked to be in C10.txt, that we would need in future classes)]

      Writre a procedure

      antiPCM(q,H):

      inputs the modolus q, and a parity check matrix in standard form, outputs the corresponding generating matrix M of a linear code over GF(q) such that

      antiPCM(q,PCM(q,M))=M and PCM(q,AntiPCM(q,H))=H

      [Suggestion: do NOT try to "reverse engineer" PCM(q,M) like I did in class, it is easier to start all over (using the same methodology) by looking at the definition in theorem 7.6 (p. 70 of the book)]

   3. [For everyone, among the correct answers one will be picked to be in C10.txt, that we would need in future classes)]

      Write a procedure

      DecodeLT(q,M) :

      that is similar to DecodeT(q,n,C), that inputs a generating matrix M (note that n=nops(M[1])), and uses the Syndrom Table to construct a table that sends every vector in Fqn(q,n) to the member of LtoC(q,M) that it is mapped to, i.e. the "closest vector".

   Added Feb. 18, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, Feb. 19, 2024

   C10.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, C8.txt, and C9.txt that are mentioned in Help4();, Help5();,Help6();, and Help7();, Help8();, and Help9();)
   • TRA(M): inputs a matrix M as a list of lists outputs the transpose matrix also as a list of lists

   • Ham2pcm(r): The parity check matrix of the binary Hamming code of order r

     Ham2(r): The generating matrix of the binary Hamming code of order r

   • Encode(q,M,u): encodes the message vector u, of length nops(M) into a code-word of length nops(M[1])

   • Decode(q,M,v): decodes the received vector v to the most likely original transmitted vector u

   Reading Homework for Monday Feb. 19, 2024, due Feb. 22

   1. Read and understand chapter 8 of Raymond Hill's book up to the top of p. 89, and Chapter 9 up to the middle of p. 102 of Raymond Hill's book A First Course in Coding Theory .

   Coding Homework for Monday Feb. 19, 2024, class (due Sunday Feb. 25, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#10 (if possible Homework#10#11)

   and an attachment(s)

   hw10FirstNameLastName.txt (and if possible together with h11FirstnameLastName.txt), BUT NOT the same file.

   1. Write a procedure

      Hampcm(r,q) that outputs the parity-check matrix (in standard form) of Ham(r,q),

   2. Write a procedure

      Ham(r,q)

      that outputs a generating matrix for Ham(r,q)

   3. Using the bottom half of p. 88, write a procedure

      DecodeHamming(q,r,v)

      that decodes a received vector v if Ham(r,q) was used. Experiment with it, by coding a random message vector, getting a code-word, randomly changing ONE place, and then decoding it. Did you get the same thing?

   Added Feb. 25, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thursday, Feb. 22, 2024

   C11.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, C8.txt, and C9.txt, C10.txt that are mentioned in Help4();, Help5();,Help6();, and Help7();, Help8();, Help9();, and Help10())
   • G24(): The BINARY [24,12,8] Golay code

   • G12(): The TERNARY [12,6,6] Golay code

   • CycS(u): all the cyclic shifts of u

   • IsCC(q,M): Is the linear code over GF(q) generated by the basis M cyclic?

   • AllPols(q,d,x): the set of all the polynomials of degree <=d in x over GF(q) (q is a prime)

   • Mul(q,P1,P2,x,f): P1*P2 mod q mod f

     ---

   • [Added after class]

     MonicPols(q,d,x): all the monic poynomials of degree d over GF(q)

   • [Added after class]

     Irreds(q,d,x): all monic irreducible polynomials in GF(q)[x] of degree d

   Homework for Thurs, Feb. 22, 2024, class (due Sunday Feb. 25, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#11 (if possible Homework#10#11)

   and an attachment(s)

   hw11FirstNameLastName.txt (and if possible together with h10FirstnameLastName.txt), BUT NOT the same file.

   1. Read and understand pp. 141-150 of Raymond Hill's book A First Course in Coding Theory .

   2. Read and understand procedure Irreds(q,d,x) added after class. By finding the number of irreducible polynomials over GF(q) of degree up to 8, and using the OEIS, find the following numbers (DO NOT do them directly!)

      nops(Irreds(q,20,x)), for q=2,5,7,11

   3. Write a procedure

      MulTable(q,f,x)

      that inputs a prime q, a polynomial f (of x) and outputs the multiplication table in the ring GF(q)[x]/f(x), where you order the non-zero polynomials of degree degree(f,x)-1, in some order but starting at 1, both rows and columns are labeled by these polynomials and computes a similar multipliction table as in the top of p. 144 (except don't have the 0). Try to recreate that table.

   4. Pick your favorite irreducible polynomial of degree 3 over GF(q), construct its multiplication table, with the rows and columns labelled by the non-zero polynomials over GF(3) of degree ≤ 2, and verify that it is a field (i.e. that every row has a 1 in it)

      Now pick your favorite reducible polynomial, construct its multiplication table and show that it is NOT a field, i.e. that there are some polynomials, mod f(x) (and mod q) that do not have multiplicative inverses.

   5. [Optional, the best code will be part of C12.txt]

      Since using the syndrom table takes too long for G24(), just treat it as a regular code (a collection of 4096 members of GF(2)^24) and do the decoding by inputting a received vector of length 24, and finding out whether the "sphere" of radius 3 around v belogs to LtoC(2,G24()), and then decodes it to that vector. In fact make it more general and for a any code over GF(q)^n write a procedure

      NearestNeigbor(C,v)

      that finds the member of C whose Hamming distance to v is minimal.

   Added Feb. 25, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, Feb. 26, 2024

   C12.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, C8.txt, and C9.txt, C10.txt, C11.txt that are mentioned in Help4();, Help5();,Help6();, and Help7();, Help8();, Help9(); and Help10(); and Help11();)
   • CtoL(n,x,g): inputs a positive integer n, a variable x, and a polynomial g (a generator of a cyclic code) outputs the generating matrix for the corresponding linear code (NOT in standard form)

   • AllFactors(n,q,x): all NON-TRIVIAL factors of x^n-1 mod q (q is a prime) (i.e. except for 1 and x^n-1)

   Reading Homework for Monday Feb. 26, 2024, due 11:00am Feb. 29

   1. Read and understand Chapter 12 of Raymond Hill's book A First Course in Coding Theory .

   ---

   Programs done on Thurs., Feb. 29, 2024

   C13.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, C8.txt, and C9.txt, C10.txt, C11.txt, and C12.txt, that are mentioned in Help4();, Help5();,Help6();, and Help7();, Help8();, Help9(); and Help10(); Help11(); and Help12();, respectively)
   • CCshop(n,q,x,K): shopping for codes with codewords of length n over GF(q) Fqn(q,n) with at most K code words if M is the basis corresponding to g (q^nops(M)<=K)

   • V(a,r): The r by r Vandermonde matrix whose i,j,entry is a[j]^(i-1)

   • Vd(a,r): the explicit expression for the determinant of V(a,r)

   ---

   Homework for Thurs, Feb. 29, 2024, class (due Sunday March 3, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#13

   and an attachment

   hw13FirstNameLastName.txt

   1. Write a procedure

      CCshopF(N,q,x,K,R,W): that inputs a positive integer N, a prime q, a variable x, a large positive integer K, a number R between 0 and 1, and a positive integer W and outputs the tuples [g,rate,MinWt] (like the members of the output of CCshoop(n,q,x,K) for all n between 2 and N, but for which the rate is ≥ R and the minimum weight is ≥ W.

      What are

      CCshopF(30,2,x,10000,1/2,5)? how many members does it have?

      CCshopF(30,3,x,10000,1/2,5)? how many members does it have?

      CCshopF(30,5,x,10000,1/2,5)? how many members does it have?

   2. Implement theorem 12.15 by writing a procedure

      CtoDual(n,q,x,g): that inputs a positive integer n, a prime q, a variable x, and a polynomial g (a generator of a cyclic code) mod q and outputs the generator matrix for the dual code of CtoL(n,x,g)

   3. [Human problem] Without "peeking", prove that det(V(a,r))=Vd(a,r)

   4. [Challenge, 10 dollars] There are r tennis players, 1, ..., r, and each of the r(r-1)/2 pairs play each other. suppose that at the beggining they were ranked according to ability where 1 is the worst and r is the best. Whenver someone lower-rankded beats someone higher it is an upset. Whenever a player wins one of their games they score a point. Let's look at the collection of all possible 2^(r(r-1)/2) and for each possible outcome let [s[1], ..., s[r]] be the score vector. Define

      Weight(Outcome):=(-1)^NumberOfUpsets*mul(a[i]^s[i],i=1..r)

      1. Prove that Vd(a,r)=Sum of all Weight(Outcome) over all possible 2^(r(r-1)/2) outcomes.
      2. An outcome is called transitive if you don't have a cycle i1 beats i2, i2 beats i3, i3 beats i1. Prove that V(a,r) is the sum of the weights of all transitive tournaments.
      3. Prove that the sum of the weights of all the 2^(r(r-1)/2)-r! non-transitive outcomes is 0
      4. Conclude that det(V(a,r))=Vd(a,r)

   5. [Optional challenge, do your best!] The code of Example 11.3 (p. 128 in the book) is a subset of given by the 4 by 10 parity check matrix . Write a procedure

      Encode113(x)

      that inputs a vector in {0,1,...,9}^6 representing [x[1],..., x[6]] and completes it to a vector

      x=[x[1],..., x[10]]

      that belongs to the code, i.e. such that the PCM given there times x is the 0 vector.

      Hint:Plug in x[1],..., x[6] into the system of four equations getting a linear system (mod 11) for the unknwons x[7],x[8],x[9],x[10]. You should use Maple's command msolve (NOT solve)

   Added March 3, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Mon., March 4, 2024

   C14.txt , Contains procedure (in addition to those from C4.txt, C5.txt, C6.txt, C7.txt, C8.txt, and C9.txt, C10.txt, C11.txt, C12.txt, and C13.txt, that are mentioned in Help4();, Help5();,Help6();, and Help7();, Help8();, Help9(); ,and Help10();, Help11();, Help12();, and Help13(); respectively)
   • Encode113(x): inputs a vector length 6 and completes it to a vector of length 10 that belongs to the code of Ex. 11.3

   • RV113(): a random member of the Ex. 11.3 code

   • Sy113(x): The vector of length 4 that is the syndrom of the received vector x

     Decode113(y): if the received vector was y, assuming at most two errors, outputs the intended transmitted vetor of the code of Ex. 11.3

   Homework for Monday, March 4, 2024, class (due Sunday March 10, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#14

   and an attachment

   hw14FirstNameLastName.txt

   1. Generalize procedures Encode113(x), RV113(), and Syl113(x), call them

      Enocde113G(x,q), Sy113G(x,q), and Decode113G(y,q)

      that generalizes the code of Ex. 11.3 from n=10 to general n, and from q=11 to general prime q.

      [Note that n is implied, n:=nops(x)+4 for Encode113G(x,q), n:=nops(x) for Sy113G(x,q) and n:=nops(y) for Decode113G(y,q)]

   2. Read and understand Chapter 11 of the book and Ramanujan's paper

   Added March 17, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs, March 7, 2024

   C15.txt ,

   Contains procedures:

   • S(x,y): maps a pair of lists of numbers of the same length, n, say, and outputs a list of numbers of length 2*n [x[1]+....+x[n],x[1]*y[1]+...+x[n]*y[n],...., x[1]*y[1]^(2*n-1)+.. x[n]*y[n]^(2*n-1)]

   • aS(a): reverse S(x,y) using Maple's solve command. inputs a list of length 2*n and outputs lists x,y of length n, such that S(x,y)=a (because of symmetry it gives n! solutions, not very efficient)

   • [corrected after class]
     OurPF(R,t): inputs a rational function of t outputs the #partial fraction decomopition over the complex numbers of the form [a1,r1],..., [an,rn] where 1/r1,..., 1/rn are the complex roots of the bottom. Assumed distinct.

   • modified after class
     aSr(a): solves the system of Ramanujan using his method with partial fractions outputs the rational function whose partial fraction would solve the system. Because of symmetry the output has the y-list in increasing order. It assumes that they are all distict.

   Homework for Thurs., March 7, 2024, class (due Sunday March 10, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#15

   and an attachment

   hw15FirstNameLastName.txt

   1. Prove that if a rational function of the form

      A(t)/((1-t*y1)*...*(1-t*yn)), with all y1,y2, ..., yn, distinct, is written in partial fractions

      C[1]/(1-t*y1)+ ...+ C[n]/(1-t*yn)

      then C[i]=-y[i]*A(1/y[i])/B'(1/y[i])

      [Hint: first show that C[i] is the limit, as t->1/y[i], of ((1-t*y[i])*A(t))/B(t), then use L'Hospital's rule]

      Convince yourself the code for aSr(a), modified after class is correct.

   2. Use the corrected procedure aSr(a) in C15.txt to check that Ramanujan's example on the second page of his seminal paper is correct.

      [Warning: Maple is not so good with simplifying expressions with radicals, you can either do "evalf", or to check that two alegranic expressions, expressed in radicals, a and b, represent the same number, do : simplify(a-b);

   3. [A little bit of a challenge, do your best] Write a finite field analog of procedures, S(x,y), OurPF(R,t), and aSr(a), call them

      qS(x,y,q), qOurPF(R,t,q), and qaSr(a,q)

      where everyhing is done modolu q

      Test it with q=11 and the example on p. 134 of the book, in other words, find

      qaSr([2,8,4,5,3,2],11);

      [Hint: to find the roots of the denominator just do it by brute force, collecting all i such that B(i) mod q=0. To get the reciprocal of a mod q do a&^(-1) mod q]

   4. [Optional challenge, (typo corrected Marcu 18, 2024)]

      Write a procedure

      EncodeBCH(d,q,x) (n=nops(x)+d-1, d <= n <=q-1), d odd

      That inputs a vector of length n-(d-1) [x[1],...,x[n-(d-1)]] and completes it to a vector of length n (in V(n,q)) x=[x[1], ..., x[n]] such that the d-1 conditions in the def. of C on p. 131 are satisfied.

   5. [Optional challenge]

      Using your qaSr(a,q) that you did, write a procedure

      DecodeBCH(d,q,x)

      that inputs a received word and finds the transmitted word assuming that at most (d-1)/2 errors occurred.

      [Congratulations to Josesh Koutsoutis who did a great job on all these challenges.

   ---

   Added March 17, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, March 18, 2024

   C16.txt ,

   Contains procedures:

   • SR(INI,L,n): inputs a 0-1 list of length L[nops(L)] a list of increasing positive integers L, and outputs the sequence of 0-1 generated by them of length n outputs the list of length n generated by the recurrence

     x[t]=x[t-L[1]]+...+x[t-L[nops(L)] mod 2

   • IsPer(L,t): Is L periodic of period t?

   • [corrected after class, please use the above C16.txt]
     FindPer(L): finds the period of L, if it exists. Otherwise is returns FAIL.

   Homework for Monday March 18, 2024, class (due Sunday March 24, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#16

   and an attachment

   hw16FirstNameLastName.txt

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

   2. [Corrected March 19, 2024, thanks to Lucy Martinez (who won a dollar)]
      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, L, of pairs [c[i],a[i]] , i=1..r where c is in {1, ..., q-1}, and a[i] are increasing positive integers

      (i.e. a[1] ≤ .... ≤ a[r])

      and outputs the first n terms of the recurrence

      x[t]=c[1]*x[t-a[1]]+ ... + c[r]*x[t-a[r]] mod q

   3. [Corrected March 19, 2024, thanks to Lucy Martinez (who won another dollar)]
      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)?

   Added March 24, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., March 21, 2024

   C17.txt ,

   Contains procedures:

   • Pols(x,d): The SET of all polynomials of degree <=d in x mod 2 such that the constant term is 1

   • PolsE(x,d): The set of polynomials of EXACTLY degree d

   • IsIr(P,x): is the polynomial P in x irreducuble (mod 2) ?
   • IsPr(P,x): is the polynomial P in x (mod 2) primitive?

   • WisW(d,x): inputs a pos. integer d and outputs the list of sets of pol. of degree exactly d such that (i) neither (ii) Irred. but not Primitive (iii) Primitive but not irreducible (iv) both

   Homework for Thurs. March 21, 2024, class (due Sunday March 24, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#17

   and an attachment

   hw17FirstNameLastName.txt

   1. Write a procedure

      MaxPer(d,x)

      that inputs a positive integer d and putputs the set of all polynomials of degree d in x (mod 2) that correspond (via the recurrence) to sequences of period 2^d-1 with initial condition INI=[1,0$(d-1)] [Hint: you first need a litte macro PolToList(P,x), in order to use FindPer(SR(INI,L,n))]

      Is MaxPer(d,x)=WisW(d,x)[4] for all d from 3 to 10?

   2. Write procedures

      qPols(q,x,d), qPolsE(q,x,d), qIsPr(q,P,x), qWisW(q,d,x), and qMaxPer(q,d,x)

      that generalize to GF(q) from GF(2). Is

      qMaxPer(3,d,x)=qWisW(3,d,x)[4] for all d from 3 to 5?

   3. Read and understand the wikipedia article on the DES

   Added March 24, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, March 25, 2024

   C18.txt ,

   Contains procedures:

   • RW(k): a random binary word of length k

   • BinToIn(L): inputs a binary word L and outputs the integer n whose binary representationit is

   • InToBin(n,k): inputs a non-neg. integer n<2^k into its binary representation with 0's in front if neccessary so that it is of length k

   • BinFun(F,L): conmverts a function on the integers (mod 2^k) to a function on binary words

   • Feistel(LR,F): The Feistel transform that takes [L,R] goes to [R+F(L) mod 2, L]

   • revFeistel(LR,F): The reverse Feistel transform that takes [L,R]->[R,L+F(R)]

   Homework for Monday March 25, 2024, class (due Sunday March 31, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#18

   and an attachment

   hw18FirstNameLastName.txt

   1. Write a procedure

      MakeCubic(L,n)

      that inputs a binary string of length 20 and outputs the cubic polynomial in n

      BinToIn([op(1..5,L)]+BinToIn([op(6..10,L)]*n+BinToIn([op(11..15,L)]*n^2+BinToIn([op(16..20,L)]*n^3

   2. [corrected and clarified, March 28, 2024, thanks to Lucy Martinez]
      Write a procedure

      EncodeDES(M,K,r)

      that inputs a message M in binary (M has to be of even length) (the usal DES has M is of lenght 64),a key of length 20*r (a random binary string only known to you and the recipient), uses the key to generate r cubic functions (the usual DES has r=16, but the key-length is always 56, and it does not use cubics) uses the key to generate a list of r cubic polynomials [F1,...,Fr], and then applies the Feistel procedure r times, (composing F1, F2, ..., Fr) to the message M.

   3. Write a procedure

      DecodeDES(M,K,r)

      Such that for ANY key of length 20*r, and any message M

      DecodeEDES(EncodeDES(M,K,r),K,r)=M

   Added March 31, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., March 28, 2024

   C19.txt ,

   Contains procedures:

   • FindRD(d): finds a random prime with d digits

     IsPrimi(g,P): Is g primitive mod P? {g,g^2,..., g^(p-2)} are all different if g^i mod p=1 doesn't happen until i=p-1

     [Warning: for large P this is impractical (as pointed out by George Spahn)]

   • FindPrimi(P): given a prime P, finds a primitive g by brute force

     [Warning: for large P this is impractical (as pointed out by George Spahn)]

   • FindSGP(d,K): finds a random Sophie Germain prime (i.e. a number P such that both P and (P-1)/2 are prime) such that (P-1)/2 has d digits

   • FindPrimiSGP(P): finds a random primitive element mod P if P is a Sophie Germain prime

   • AliceToBob(P,g): alice picks her secret integer a from 2 to P-2 does not tell anyone (not even Bob) and sends Bob g^a mod P
     (the output is a pair [a, g_a=g^a mod P], the first part (a) ALice keeps to herself, the second part, g_a, she emails Bob)

   • BobToAlice(P,g): Bob picks his secret integer b from 2 to P-2 does not tell anyone (not even Alice) and sends Alice g^b mod P
     (the output is a pair [b, g_b=g^b mod P], the first part (b) Bob keeps to himself, the second part, g_b, he emails Alice)

   Homework for Thursday March 28, 2024, class (due Sunday March 31, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#19

   and an attachment

   hw19FirstNameLastName.txt

   1. If you haven't done it yet email me your choice of project, and whether you are willing to be the team leader.

   2. Read and understand Jean-Paul Delahaye's fascinating column ( Pour La Science, April 2024). [en Francais, but you can click on "English"] (here is the .pdf version (in French)

   3. Write Maple procedures p_n, t(n), Π(n), implementing these sequences in Delahaye's article. Verify that they give what they are supposed to give.

   4. By using AliceToBob(P,g) and BobToAlice(P,g) verify that they share the same key (do it several times)

   5. Write a procedure

      DL(x,P,g)

      that inputs an integer x between 1 and P-1 and outputs an integer a between 1 and P-1 such that g^a=x (or returns FAIL if none exits). Convince yourself that for large P it is very slow.

   6. [Optional challenge, 5 dolalrs for the best implementation] Implement (in Maple) the Rabin-Miller (pseudo-) primality test

      [Glroia Liu (see here) and Joseph Koutsoutis (see here) met this challenge!

   Added March 31, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Mon., April 1, 2024

   C20.txt ,

   Contains procedures:

   • RP(a,b): a random point on the elliptic curve y²=x³+ ax+b

   • DoesLie(a,b,P): does the point P lie on the elliptic curve y²=x³+ ax+b ? It returns 0 if it does, otherwise not.

   • AddE(a,b,P,Q): the "addition" (over real elliptic curves) of the point P and Q that lie on the elliptic curve   y²=x³+ ax+b ?

   Homework for Monday April 1, 2024, class (due Sunday April 7, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#20

   and an attachment

   hw20FirstNameLastName.txt

   1. [Graphical challenge, try your best]

      Using Maple's graphing command, write a procedure

      Diag(a,b)

      that draws a picture like Fig. 3 (with the points A, B,C, A+B labeled and indicated on the diagram) for a general elliptic curve y^2=x^3+a*x+b , for general a, and b, and A and B picked using RP(a,b)

   2. Write a procedure

      IntSol(a,b,K)

      that finds all integer solutions [x,y] with -K<=x<=K of the diopphantine equation

      y^2=x^3+a*x+b

   3. Write a procedure

      SolChain(a,b,S1,S2,K)

      That starts out with two solutions S1 and S2 of y^2=x^3+a*x+b and repeatedly uses AddE(a,b,L[-2],L[-1]) to get a list of length K+2 of solutions in rational numbers. Can you get infinitely solutions this way?

   Added April 7, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., April 4, 2024

   C21.txt ,

   Contains procedures:

   • AE(a,b,P,Q): "adding" (in the sense of elliptic curves) the points P and Q on the elliptic curve (over the reals) (does the same thing AddE(a,b,P,Q) but can handle the case where P[1]<>Q[1] and also handles infinity)

   • EC(a,b,p): the set of all the points (x,y) such that y^2=x^3+a*x+b mod p

   • AEp(a,b,P,Q,p): "addition" in the elliptic curve y^2=x^3+a*x+b mod p

   • Mul(g,A,a,b,p): inputs a member,g, of the elliptic curve y^2=x^3+a*x+b mod p and outputs g+g+...+g (A times)

   • Finished after class (but still inefficient for large primes p)

     Sqrt(n,p,K): an x such that x^2=n mod p (if it exists, or returns FAIL), tries Cippola's algorithm K times

   Homework for Thurs. April 4, 2024, class (due Sunday April 7, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#21

   and an attachment

   hw21FirstNameLastName.txt

   1. Read and understand Ewa Syta's notes

   2. Read and understand the wikipedia article Cippola's algorithm. Then read the Maple procedure (that I finished after class) Sqrt(n,p,K). Note that it does use the Legendre symbol directly but rather the so-called Euler criterion (n is a square mod p if (n^((p-1)/2) mod p=1)

   3. Write procedure

      RandPt(a,b,p)

      that inputs integers a and b and a prime p and outputs a random point on the elliptic curve y^2=x^3+a*x+b mod p

      [Hint: keep trying to pick a random x and then use Sqrt(x,p,k) (if it exists, and keep trying it until it does) to get the corresponding y.

   4. Write procedures

      AliceToBobEC(a,b,p,g) and BobToAliceEC(a,b,p,g)

      where after both agree on a,b, (the elliptic curve), on p (the prime) and some random point g on EC(a,b,p) where

      Alice picks a random (large) A (and keeps it to herself) and sends Bob Ag (i.e. g+....+g repeated A times)

      Bob picks a random (large) B (and keeps it to himself) and sends Alice Bg (i.e. g+....+g repeated B times)

      Experiment it with a few random cases and verify that the shared key (AB(g)=BA(g)) is indeed the same.

   5. Write a procedure

      Hasse(a,b,K)

      that finds the primes for which the number of points in y^2=x^3+a*x+b mod p minus (p+1), divided by sqrt(p), for all primes between 3 and K is maximal and minimal. Tabulate

      Hasse(a,b,500) for 1<=a,b<=10

   6. [Optional challenge, 5 dollars] Write a procedure

      SqrtF(n,p,K)

      whose input and output are the same as Sqrt(n,P,K) but does it much faster (for large p).

      [Hint, right now if you have a radical expression a+b*sqrt(Q) with a and b integers, Maple can't do

      (a+b*sqrt(Q))&^n mod p

      efficiently. The current code (for Sqrt(n,p,K), does
      expand((a+b*sqrt(Q))^n)

      getting A+B*sqrt(Q), for huge A and B and then does mod p

   Added April 7, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, April 8, 2024

   C22.txt ,

   Contains procedures:

   • ProveEclipse(): proves that the apparent sizes of the moon and the sun, to an observer on earth are very close, making a total solar eclipse possible

   • SE(SunCenter,SunRadius,MoonCenter,MoonRadius,EarthCenter,EarthRadius): the very beginning of a graphical procedure to draw a diagram similar to the one in the "Geometry" section of the wikipedia article on solar eclipse

     [See the optional homework challenge to expand it]

   Homework for Mon. April 8, 2024, class (due Sunday April 14, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#22

   and an attachment

   hw22FirstNameLastName.txt

   1. Read and understand the wikipedia article on solar eclipse

   2. Read and understand the wikipedia article on Tidal force and convince youself that the tidal strength of a heavenly body on the earth is proportional to its mass divided by the cube of the distance to the earth from that object. Explain how this fact, combined with the fact that the apparent sizes of the moon and the sun to an observer on Earth is about the same (making at total eclipse possible, but just barely) combined with the known fact that the lunar tide is much stronger than the solar tide, proves that the density (mass per volume) of the moon is significantly greater than that of the sun.

      Acknowledgment: I owe this exercise to Professor David Vanderbilt from the Rutgers physics department.

   3. Start working on your chosen class final project and report the progress so far (including the empty set, but you have to respond)

   4. [Optional challenge, 10 dollar prize for the best entry]

      Complete procedure SE(SunCenter,SunRadius,MoonCenter,MoonRadius,EarthCenter,EarthRadius) (that we barely started in C22.txt , to draw a diagram similar to the one in the "Geometry" section of the wikipedia article on solar eclipse

      Added April 15, 2024: Congratulations to Nuray Kutlu (see her maple code and gorgeous picture) and Gloria Liu (see her maple code and beautiful picture) sharing the prize. Each got 5 dollars.

   5. [Optional challenge, 20 dollar prize for the best entry. I have no clue how to do it myself, neither whether it is doable in Maple]

      Use the animate function in the plots package of Maple to illustrate the earth moving around the sun (where the orbit is drawn, but a point labeled E is moving around the sun). If possible also have the moon going around the earth. The input parameters should be an abitrary year length (365.5 for us) and lunar sideral period (27.32 for us), as well as the center of the sun, and the distance of the sun to the earth. You can assume that it is a circular orbit.

      Extra credit: have the earth rotate around itself (1 day for us)

      Added April 15, 2024: Congratulations to Ryan Badi (see his maple code and gorgeous animation) and Aurora Hiveley see her maple code and run it) for sharing the prize. They each got 10 dollars.

   Added April 14, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., April 11, 2024

   C23.txt ,

   Contains No procedures (just a place holder)

   Today we discussed some of the class projects, we will go back to cryptography on Monday

   Homework for Thurs. April 11, 2024, class (due Sunday April 14, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#23

   and an attachment

   hw23FirstNameLastName.txt

   1. Read and understand Section 6 of Clifford Cocks' article

   2. Try to make some progress on your class projects (with your team-mates) beyond what we did in class today. For those projects for which there is no preliminary version yet, please send me something to post in the project page, namely proj2.txt, proj6.txt, proj7.txt, proj8.txt, proj9.txt . At the very minimum it should have the name of the team members of the project and Help();

   ---

   Programs done on Monday, April 15, 2024

   C24.txt ,
   • MakeRSAkey1(K): makes a triple [N,e,d], where N is a product of two K-digit primes. N, and e, are public and d is private, with one try. Often returns FAIL.

   • MakeRSkey(K,M): makes an RSA key by trying MakeRSAkey1(K) M times, if M is big enough (say M=20) it is very unlikely to return FAIL

   • AliceToBob(M,Nbob,eBob,Nalice,dAlice,H): #Inputs Alice's message M, the [Nbob,eBob] public part of Bob's RSA key, the Nalice (public) and dAlice (private) of Alice's key and H a large public integer and we agree that the Hash function is x^3 mod H, where x is the message
     output a pair consisting of the the encrypted message, followed by the (usually, in real life application) much shorter signature

   • BobReadAlice(MS,Nbob,dBob,Nalice,eAlice,H): inputs a signed message MS=[M1,S] sent from Alice, as well as Nbob (public),dBob (that only Bob knows),Nalice, eAlice, and H (all public) outputs the deciphered message that Alice sent and also checks that it indeed came from Alice and not from a bad guy pretending to be Alice

   Homework for Monday April 15, 2024, class (due Sunday April 21, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#24

   and an attachment

   hw24FirstNameLastName.txt

   1. Decide whether you would like to sign up for the annual field trip to the Princeton cemetery followed by a free dinner. Due to the size of the class, there are two dates, each of them limited to eight people. Either:
      • Monday May 6, 2024, 6:00pm, OUTSIDE the Princeton Public Libary
      • Wed. May 8, 2024, 6:00pm, OUTSIDE the Princeton Public Libary
      • If you are unable to make it, or are not interested, return the empty set: {}.

      • If you can ONLY make it on May 6, return [6]. If you can ONLY make it on May 8, return [8].

      • If you can make it on both days but prefer one to the other return the LIST (in order of preferance) [6,8] or [8,6].

      • If you can make it on both dates, and don't care, return the SET {6,8}.

   2. Generalize AliceToBob(M,Nbob,eBob,Nalice,dAlice,H) and BobReadAlice(MS,Nbob,dBob,Nalice,eAlice,H) to

      AliceToBobG(ListM,Nbob,eBob,Nalice,dAlice,H) and BobReadAliceG(MS,Nbob,dBob,Nalice,eAlice,H) (where MS=[ListM',S]),

      where ListM is an arbitrary list of integers each between 1 and Nbob, and the signature is the sum of the integers in ListM cubed mod H. The encrypting and descryting is done separately for each member of ListM.

   3. Look at the class mailing list and find the three students right after you (mod 19, so for the three students at the bottom (Alex Val., Alex Var., and Kaylee W.), they would have to go to the beginning)
      • Email them your public ([N,e]) part of your public key (but keep d to yourself). Also email them your public H (so the Hash function is M^3 mod H)

      • Ask them to email you THEIR [N,e] but to keep their d to themselves.

      • Convert your birthday to an integer: mm/dd/yyyy -> mmddyyyy. For example July 2, 1950 becomes the integer 02071950 (same as 2071950). This is your secret message. For each of them encrypt your birthday using their public key [N,e] (different for each, of course [most probably]). Then for two of them sign them the right way, but for one of them sign it the wrong way. Ask them to send you back your birthday, and whether they believe it is you.

        Alltogether you should have six email exchanges, the three behind you and the three ahead of you. Describe in detail all these interactions (on both ends), including the RSA keys and the Hash chosen, and the birthdays of your three classmates who kindly sent them to you.

   Added April 21, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Thurs., April 18, 2024

   C25.txt ,
   • LD(p): inputs a pos. rational number from 0 to 1 and outputs true with prob. p

   • RG(n,p): inputs a pos. integer n and a rational number p between 0 and 1, and outputs a simple graph on n vertices where the prob of an edge is p (independetly)

   • RHG(n,p): inputs a pos. integer n and outputs a simple HAMILTONIAN graph on n vertices where the prob of an edge is p (independetly) together with the Hamiltonian path. The output is a pair [G,permutation] where the permutation of {1,...,n} is the Hamiltonian cycle that you know and you don't want anyone else to know BUT you do want to convince them that you DO know

   • ZKP1(n,G,pi,Opt): Does ONE ROUND of the Blum protocol. Inputs a graph n,G, a Hamiltonian pi, and Opt=1 or Opt=2. If Opt=1, then you show all the n+binomial(n,2) boxes, while if Opt=2, then you show the contents of the n boxes correponsing to the mapping of your Hamiltonian cyle [the homework below asks you to modify it so the output is true or false]

   Homework for Thurs. April 18, 2024, class (due Sunday April 21, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#25

   and an attachment

   hw25FirstNameLastName.txt

   1. Read and understand Manuel Blum's article on Zero-Knowledge proofs and Hadas Zeilberger's engaging explanation of Zero-Knowledge proofs in plain English

   2. Write a procedure

      VerifyOpt1(n,G,B1,B2)

      that inputs a positive integer n, a graph (set of edges) G, and tables B1 (of size n) and B2 (of size binomial(n,2)) and outputs true if it is a faithful relabling of the graph G, otherwise false.

      Having done that Modify procedure ZKP1(n,G,pi,Opt) to return true or false, as follows:

      • If it is Option 1, then it returns VerifyOpt1(n,G,B1,B2)

      • If it is Option 2, then it returns true if you get {1}, otherwise it returns false.

   3. Write a procedure

      ZKP(n,G,pi,K)

      that uses (the modified) ZKP1(n,G,pi,Opt) by having K rounds, and at each round, picking Option 1 or Option 2 each with probability 1/2 and returning true if and only if ZKP1(m,G,pi,Opt) always returns true.

   4. [Optional challenge: 10 dollars to be divided, the best code will make it to C25.txt, with due credit]
      • Write a procedure

        R3CG(n,p)

        that inputs a positive integer n, then first generates a random list C, of length n whose entries are {1,2,3} (corresponding to the three colors) and constructs a random graph for which this coloring is legal. In other words for each 1 ≤ i < j ≤ n first find out whether C[i] ≠ C[j] and if it is add it to the set of edges with probabilty p. It returns the pair [G,C]. This will supply you with a ready-made graph for which you know a (legal) 3-coloring.

      • Implement the ZK protocl for proving that a graph G is 3-colorable, given in pages 1449 and 1450 of Manuel Blum's great paper, and test it with several examples gotten from R3CG(n,p).

   Added April 21, 2024: read the students' nice solutions in this directory.

   ---

   Programs done on Monday, April 22, 2024

   C26.txt ,
   • FT(SetL): The frequency table of all words whose length belobgs to SetL For example FT({3,4}) returns the randked frequency table for words of length 3 and 4

   • TM(SetL): The frequency table of all words whose length belobgs to SetL #For example FT({3,4}) returns the randked frequency table for words of length 3 and 4 AND the Transiton matrix 28x28 the first "letter" is ST and the last is EN

     WARNING: NOT YET FINISHED. (see optional challenge below in homework)

   Homework for Monday April 22, 2024, class (due Sunday April 28, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#26

   and an attachment

   hw26FirstNameLastName.txt

   1. Continue to work on your project due May 1, 11:00pm

   2. Using the file ENGLISH.txt, where ENG() is a list of length 26 whose i-th entry is the list of words of length i, find

      Out of the 26²=676 pairs of letters how many actualy show up as consecutive two letters? (For example for the word [a,l,e,x] the pairs [a,l],[l,e],[e,x] shosed up.

      Out of the 26²=676 pairs of letters how many show up up as consecutive two lettersmore than ten times?

      Out of the 26³=175676 triples of letters how many actualy show up as consecutive three letters? (For example for the word [v,a,l,e,n,t,i,n,o] the triples [v,a,l],[a,l,e],[l,e,n],[e,n,t],[n,t,i],[t,i,n],[i,n,o] showed up_

   3. Optional challenge [10 dollars to be divided and code added to C26.txt with due credit]: Finish up procedure TM(SetL) that should output a 28 by 28 matrix (in decimals) where the order is ALPH1:=[ST,a,b,c ..., z, EN], and the [i,j] entry is the probability that if you are currently at letter ALPH1[i] that the letter after that is ALPH1[j]. The last row should of course be all zeores.

   ---

   Programs done on Thurs., April 25, 2024

   C27.txt ,

   We implemented the Manuel Blum's protocol in his article Zero-Knowledge proofs

   • RGC3(n): inputs a pos. integer and outputs the triple (n,E,C) where E is the set of edges and C is a proper coloring

   • ZKP3(n,E,C,Opt) : implements one round of the Manuel Blum protocol for Zero Knowledge Proof of a 3-coloring of a simple graph. The inputs are n (the number of vertices whose names are 1,2,..,n, E the set of edges, the secret 3-coloring, and Opt=1 or Opt=2 correponding to the two choices the Verifier can ask the prover to perform

   • Verify1(n,E,B2,B1v): verifies that B2 and B1v are consistent with the graph, if verifier chose Option 1

   • Verify2(B1c,S):verifies that part of B2 and B1c are consistent with the graph coloring, if verifier chose Option 2

     [Corrected after class]

   Homework for Thurs. April 25, 2024, class (due Sunday April 28, 2024, 8:00pm)

   Please email ShaloshBEkhad at gmail dot com an email with

   Subject: HomeWork#27

   and an attachment

   hw27FirstNameLastName.txt

   1. Continue to work on your project due May 1, 11:00pm

   2. Write a procedure

      MetaZKP3(n,E,C,K) where the verifier asks the prover K questions and randomly picks the option (each with prob. 1/2) and if it is true all the times returns true, if it is false even one time, it returns false.

      Once you have it, and experiment with several large graphs and asociated cloring, gotten from RGC3(n) and convince yourself that the graph is genuine, using K=20.

      Now change the coloring randomly (so it is probably no longer proper) and see whether MetaZKP3(n,E,C,20) is still true.

   3. [Optional challenge] Read and understand the alternative, hopefully simpler approach (pointed out by George Spahn) and implement it.

   ---

   Dr. Z.'s teaching page