Math 640: EXPERIMENTAL MATHEMATICS (Coding Theory and Cryptography) (Spring 2024)

http://sites.math.rutgers.edu/~zeilberg/math640_24.html

Last Update: May 1, 2024


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.


Added May 3, 2024: Enjoy Students' AMAZING Final Presentations of their projects and Grande Finale by Neil Sloane

HAVE A GREAT SUMMER!


ADDED MARCH 17, 2024: pick a project.

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


Optional (but Highly recommended) Getting Started Homework

Teach yourself the basics of Maple by reading Frank Garvan's golden-oldie part 1, part 2
Note: a few commands are no longer valid in today's Maple. The most important one is that " has been replaced by %.

For more details, see this 2002 masterpiece.

How to submit homework

Programs done on Thurs., Jan. 18, 2024

C1.txt , Contains procedures


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

Please email ShaloshBEkhad at gmail dot com an email with

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

C2.txt , Contains procedures

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

Please email ShaloshBEkhad at gmail dot com an email with

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

C3.txt , Contains procedures (in addition to those of C2.txt, NextPrime1 and ME1, see above):

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

Please email ShaloshBEkhad at gmail dot com an email with

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

C4.txt , Contains procedures

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

Please email ShaloshBEkhad at gmail dot com an email with

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=2r-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

C5.txt , Contains procedures (in addition to those from C4.txt that are mentioned in Help4();)

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

Please email ShaloshBEkhad at gmail dot com an email with

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

C6.txt , Contains procedures (in addition to those from C4.txt and C5.txt that are mentioned in Help4(); and Help5();)

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

Please email ShaloshBEkhad at gmail dot com an email with

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

    [Ik|A]

    where Ik 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

C7.txt , Contains procedures (in addition to those from C4.txt, C5.txt and C6.txt that are mentioned in Help4();, Help5();, and Help6();)

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

Please email ShaloshBEkhad at gmail dot com an email with

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

  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

Please email ShaloshBEkhad at gmail dot com an email with

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();)

    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();)

    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();)

    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())

    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();)

    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)


    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)

    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:

    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:

    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:

    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:

    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:

    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 pn, 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 ga=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:

    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:

    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:

    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 ,

    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 ,

    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 ,

    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 262=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 262=676 pairs of letters how many show up up as consecutive two lettersmore than ten times?

      Out of the 263=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.

      Added April 28, 2024: Joseph Koutsoutis met this challenge and won ten dollars. It is now part of C26.txt ,

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


    Programs done on Thurs., April 25, 2024

    C27.txt ,

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

    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.

      Added May 1, 2024: Dayoon Kim met this challenge! See her nice code.

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


    Programs done on Monday, April 29, 2024

    C28.txt ,

    Today was a "hackaton" and there were two challenges. Both met

    Optional Homework for Monday April 29, 2024, class (no due date)

    Please email ShaloshBEkhad at gmail dot com an email with

    1. Find out whether

      pmatSeq(1,5,d);

      for d=5,6,7,8,9

      are in the OEIS, and if not, submit them, mentioning that they were created in this class

    2. Find several pairs w1 and w2 such that ABseq(15,w1,w2) are not yet in the OEIS and submit them.


    May 2, 2024, 12:00-2:30 pm: Students' Final Presentations of their projects and Grande Finale by Neil Sloane


    Added May 16, 2024: Read the students' teaching evaluations


    Dr. Z.'s teaching page