Last Update: May 1, 2024
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!
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.
For more details, see this 2002 masterpiece.
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
#Please do not post homework
or
#OK to post homework
Followed by
#Your Name, Date, Assignment X
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.
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.
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.
a -> ae 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): ae mod n, the stupid way
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.
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.
and the decrypton is
a GOES TO ad mod n
Try:
MakeRSAkey(100);
EAnew(m,n): inputs m > n and outputs, the gcd(m,n) (homemade version, using iteration rather then recursion)
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.
[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)
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.
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?
Carefully read section IV of the seminal Rivest-Shamir-Adleman paper, about digital Signatures, and implement it, using the RSA encrypton.
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.
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.
Added Feb. 4, 2024: read the students' nice solutions in this directory.
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.>
[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 λ.
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?
Added Feb. 4, 2024: read the students' nice solutions in this directory.
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.
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 .
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.
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.
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.
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]
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
T:=DecodeT(q,n,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
[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.
Subject: hwValentine
and an attachment
hwValentineFirstNameLastName.txt
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).
Subject: HomeWork#8 (if possible Homework#8#9)
and an attachment(s)
hw8FirstNameLastName.txt (and if possible together with hw9FirstnameLastName.txt)
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)
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.
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.
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)]
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.
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])
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.
Hampcm(r,q) that outputs the parity-check matrix (in standard form) of Ham(r,q),
Ham(r,q)
that outputs a generating matrix for Ham(r,q)
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.
MonicPols(q,d,x): all the monic poynomials of degree d over GF(q)
Irreds(q,d,x): all monic irreducible polynomials in GF(q)[x] of degree d
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.
nops(Irreds(q,20,x)), for q=2,5,7,11
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.
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.
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.
Subject: HomeWork#13
and an attachment
hw13FirstNameLastName.txt
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?
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)
Weight(Outcome):=(-1)^NumberOfUpsets*mul(a[i]^s[i],i=1..r)
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.
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
Subject: HomeWork#14
and an attachment
hw14FirstNameLastName.txt
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)]
Added March 17, 2024: read the students' nice solutions in this directory.
Contains procedures:
Subject: HomeWork#15
and an attachment
hw15FirstNameLastName.txt
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.
[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);
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]
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.
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.
Contains procedures:
x[t]=x[t-L[1]]+...+x[t-L[nops(L)] mod 2
Subject: HomeWork#16
and an attachment
hw16FirstNameLastName.txt
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
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.
Contains procedures:
Subject: HomeWork#17
and an attachment
hw17FirstNameLastName.txt
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?
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?
Added March 24, 2024: read the students' nice solutions in this directory.
Contains procedures:
Subject: HomeWork#18
and an attachment
hw18FirstNameLastName.txt
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
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.
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.
Contains procedures:
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)]
[Warning: for large P this is impractical (as pointed out by George Spahn)]
Subject: HomeWork#19
and an attachment
hw19FirstNameLastName.txt
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.
[Glroia Liu (see here) and Joseph Koutsoutis (see here) met this challenge!
Added March 31, 2024: read the students' nice solutions in this directory.
Contains procedures:
Subject: HomeWork#20
and an attachment
hw20FirstNameLastName.txt
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)
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
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.
Contains procedures:
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
Subject: HomeWork#21
and an attachment
hw21FirstNameLastName.txt
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.
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.
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
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.
Contains procedures:
[See the optional homework challenge to expand it]
Subject: HomeWork#22
and an attachment
hw22FirstNameLastName.txt
Acknowledgment: I owe this exercise to Professor David Vanderbilt from the Rutgers physics department.
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.
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.
Contains No procedures (just a place holder)
Today we discussed some of the class projects, we will go back to cryptography on Monday
Subject: HomeWork#23
and an attachment
hw23FirstNameLastName.txt
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
Subject: HomeWork#24
and an attachment
hw24FirstNameLastName.txt
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.
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.
Subject: HomeWork#25
and an attachment
hw25FirstNameLastName.txt
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:
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.
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.
Added April 21, 2024: read the students' nice solutions in this directory.
[COMPLETED BY JOSEPH KOUTSOUTIS who won 10 dollars]
Subject: HomeWork#26
and an attachment
hw26FirstNameLastName.txt
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_
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.
We implemented the Manuel Blum's protocol in his article Zero-Knowledge proofs
[Corrected after class]
Subject: HomeWork#27
and an attachment
hw27FirstNameLastName.txt
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.
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.
Today was a "hackaton" and there were two challenges. Both met
pmatSeq(1,5,10);
gives the first 5 terms of OEIS sequence A135944
[Code by George Spahn but the team consisting of Daniel Elwell, Ramesh Balaji, Alex Varajabedian also did it]
ABseq(15,[0,0],[0,1]);
are the first 15 terms of OEIS sequence A371358, and
ABseq(15,[0,0,0],[0,0,1]);
are the first 15 terms of OEIS sequence A371662, and
[Code essentially by the team consisting of Joseph Koutsoutis, Gloria Liu, and Alex Valention, with editing by Dr. Z.]
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
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