Last Update: March 27, 2025
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, Quantum computing and algorithmic graph theory. 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 should be applicable almost everywhere.
Maple packages produced in this class
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.
Write a procedure AM(G) that inputs a graph [n,E] and outputs the adjacency matrix, represented as a list of lengthn of lists of length n, such that M[i][j]=1 if {i,j} belongs to E and 0 otherwise. For example
AM([2,{{1,2}});
should output [[0,1],[1,0]] .
Image(pi,G)
that inputs a permutation pi of {1,...,n} and a graph G=[n,E] and outputs the image under pi.
ULgraphs(n)
that outputs a set of graphs with ONE member of each equivalence class.
What is
[seq(nops(ULgraphs(i)),i=1..6)]
Is is in the OEIS? What is its A-number.
Added Jan. 26, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
RG(n,p)
Cliques(G,k): inputs a graph G and a pos. integer k outputs the set of k-cliques
Subject: HomeWork#2
and an attachment
hw2FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
[Optional for novices] Write a procedure
TotClique(G,k)
that inputs a graph G=[n,E] and a positive integer k, and outputs the total number of k-cliques and k-anti-cliques.
CheckRamsey(k,K), that inputs a positive intgeger k and a large integer K that picks K random graphs (using RG(18,1/2)) and finds the minimum of ToClique(G,4);
EstimateAverageClique(n,p,k,K)
that estimates the average number of cliques of size k in a random graph given by RG(n,p) by picking K of them and averaging.
What did you get for
EstimateAverageClique(10,1/2,4,10000)?
[Optional challenge, 5 dollars] Find a closed-form expression for the average number of k-cliques in a graph with p vertices where the prob. of every edge showing up is p.
Added Feb. 2, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C3.txt , Contains procedures (in addition to those of C1.txt and C2.txt listed in Help1(); and Help2(); respectively)
NuCG(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices, in other words sequence OEIS A001187 , done by brute force
NuCGc(n): the first n terms of the sequence enumerating CONNECTED labeled graphs on n vertices, in other words sequence OEIS A001187 , done cleverly, using Exponential Generting Function, the fact that
Sum(CC[i]/i!*z^i,i=0..infinity)= log(Sum(2^binomial(i,2)/i!*z^i,i=0..infinity)
Subject: HomeWork#3
and an attachment
hw3FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
PC:=proc(n,p,K) local i:evalf(coeff(add(IsCo(RG(n,p)),i=1..K),true,1)/K):end:
is an estimate, with large enough K (say at least 200), for the probability of coonectivity of a random graph with n edges where every edge is picked with prob. p (the Edros-Renyi model)
With n=10,20,30, and p=1/10, 2/10, ... and K=200 experiment and try to estimate the threshhold for connectivity, i.e. when it changes being very unlikely to very likely.
Procedure NuCCc(n) outputs the first n terms (starting at n=1) of OEIS sequence A1187 that counts the sequence let's call it C[n], of the number of connected labeled graphs with n vertices. It is based on the formula
Sum(C[n]*z^n/n!,n=0..infinity)=log(Sum(2^(n*(n-1)/2)*z^n/n!,n=0..infinity)
Let P[n](x) be the polynomial in x whose coefficient of x^r is the number of labeled connected graphs on n vertices and EXACTLY r edges. Convince yourself (or believe) that using generating functions one has the formula
Sum(P[n](x)*z^n/n!,n=0..infinity)=log(Sum((1+x)^(n*(n-1)/2)*z^n/n!,n=0..infinity)
Write a procedure
NuCGx(n,x)
that inputs a pos. integer n and a variable x, and outputs a list of length n whose i-th entry is P[i](x)
Convince yourself that the lowest power (lowdegree in Maple) of P[n](x) is n-1. Using NuCGx(n,x) (make sure to put "option remember" there), Write a procedure
NuCGk(n,k)
that inputs a positive integer n and a non-negative integer k and outputs the sequence of cofficients of x^(n-1+k) of P[n](x)
What OEIS number is NuCGk(n,0)?
What OEIS number is NuCGk(n,1)? (if it exists)
Keep upping k and see the largest k for which NuCGk(n,k) is in the OEIS
C4.txt , Contains procedures (in addition to those of C1.txt and C2.txt and C3.txt listed in Help1(); and Help2(); Help3(); respectively)
Subject: HomeWork#4
and an attachment
hw4FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
UM(alpha,beta,gamma,delta)
that implements box 1.1. on p. 20 of the The Nielsen-Chuang book [Note the superflous comma]
For random alpha, beta, gamma, delta apply it to IsUM(A). Also, a litle bit of challenge, prove it for geneal (symbolic) alpha,beta,gamma, delta
Added Feb. 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C5.txt , Contains procedures
Subject: HomeWork#5
and an attachment
hw5FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
RandomState(n,K)
that inputs a pos. integer n and a pos. integer K and outputs a random state vector with n complex components whose real and imaginary parts are from -K to K, then normalize it.
GeneralPauli(n)
that inputs a NORMALIZED vector n=[nx,ny,nz]
that constructs the 2 by 2 matrix. at the bottm of p. 349 of the Susskind-Frieman Quantum Mechanics book book.
Find its eigenvalues and eigenvectors.
Added Feb. 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C6.txt ,
ProbDist(L,A): Given an obervalble represented by the Hermitian matrix L and a state vector A (i) the list if eigenvalues (possible outcomes of observing L regardless of the state A (ii) the respective probabilities of the outcome being that eigenvalue, if the system is at state A (iii) the expected value of the outcome
Subject: HomeWork#6
and an attachment
hw6FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
AllHM2(K)
that inputs a positive integer K and outputs ALL 2 by 2 matrices of the form
[[a,b+I*c],[b-I*c,d]]
where a,b,c,d, are integers such that 1 ≤ a,b,c,d ≤ K (there are K4 of them
Write a procedure
RealSV2(K)
that inputs a positive integer K and outputs all normalizations of the vectors (i.e. make them unit vectors)
[a,b]
with
where a and b are integers 1 ≤ a,b ≤ K (there are K2 of them
UncertaintyContest(K)
that inputs a positive integer K and goes all throgh the pairs A, B of matrices in AllMH2(K), and RealSV2(K) (quite a few of them) and outpts the triplet [A,B,V] that make CheckUP(A,B,V) as small as possible and as big as possible [Make sure that you exclude the case when A and B commute, since then the ratio is infinity]
What are
UncertaintyContest(2)?, UncertaintyContest(3)?
Added Feb. 16, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Design a Valentine that says
I love Algorithmic Graph Theory
OR
I love Quantum Computing
email two attachments
ValentineFirstLast.jpg
and ValentineFirstLast.txt (with the source code)
and fill the form
and email ShaloshBEkhad@gmail.com with
Subject: Valentine Ballot
and an attachment
ValentineBallotFirstLast.txt
with your ratings (from 1 to 10, please reserve 0 for your own valentine and for those that have no submissions)
[The winner will get a chocolate box.]
Added Feb. 17: Congratulations to Lucy Martinez for winning first prize.
C7.txt ,
AntiPC(P): inputs a list of length n-2 with entries from {1, ...,n} outputs the tree T such that PC(T)=P
Subject: HomeWork#7
and an attachment
hw7FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "Please do not post", it will be posted.
NumberOfLeaves(T)
that inputs a labeled tree, T, and outputs the number of leaves (vertices of degree 1). For example
NumberOfLeaves({{1,2},{1,3},{1,4}}); should output 3
RandomTree(n)
that inputs a positive integer n, and outputs a random labeled tree on {1, ...,n}
[Hint: using rand(1..n), generate a random list of length n-2, P, and then let T:=AntiPC(P)]
EstimateAverageNumberOfLeavs(n,K)
that uses simulation to esimates the average number of leaves in a random labeled tree with n vertices
[Hint: run RandomTree(n) K times, for each time find out the number of leaves, add them all up and divide by K.]
What did you get for
EstimateAverageNumberOfLeavs(100,1000)?
EstimateAverageNumberOfLeavs(100,10000)?
Are they close?
limit(an/n, n goes to infinity)
exists, and find its value.
Added Feb. 16, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C8.txt ,
Read Turing and Abel prizes winner Avi Wigderson's essay (section III.24, pp. 196-199) in the Princeton Companion of Mathematics edited by Sir W. Timothy Gowers.
Subject: HomeWork#8
and an attachment
hw8FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
By taking V:=RSV(2,100); verify that
add(ExpMV(PM()[i],V)^2,i=1..3)=1
Do it three times. In other words the sum of the squares of the expectation of the three Pauli matrices adds up to 1 for every state vector.
TP(PM()[i],PM()[4])
Let's call them Ax,Ay,Az. For a random state vector, obtained by RSV(4,10), say, write a procedure
EntanglementAlice(V)
that outputs the sum of the squares of the expected values of Alice's measurement in that state.
RandomProductState4(K)
that outputs a random product state vector of length 4 obtained by taking the tensor product of two RSV(2,K)
What is it for a random product state?
By using RSV(4,10) twenty times, find the vector with maximal entanglemt (i.e. the smallest value of EntanglementAlice(V)) and the least (closest to 1)
Added Feb. 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C9.txt , contains the following procedures:
[The original name in class was Nei(v) but Pablo suggested changing the name since in C3.txt there was a procedure called Neis(v)]
Subject: HomeWork#9
and an attachment
hw9FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
Using the definition of the Cheeger constant in this wikipedia article, write a procdeure
CheegerC(G)
that inputs a graph in our format [n,E] and outpits the Cheeger constant.
[Hints: 1.with the combinat package loaded, choose(S,i) gives you the set of subsets of S of size i 2. To get the number of edges between S and its complement form the set of potential edges {s1,s2} where s1 is in S and s2 is in its complement and then intersect it with E and then take its nops) ]
CheckBounds(G)
that outputs the Cheeger constant and the interval [(d-Lambda_2)/2,sqrt(2*d*(d-Lambda_2))] and checks that the former is inside the latter.
What did you get for CheckBounds(G) for
G=Gnd(n,2), 5 ≤ n ≤ 10
G=Gnd(n,3), 5 ≤ n ≤ 10
1. (3 dollars) Conjecture an explicit expression for
charpoly(AM(Ck(k)),x)
2. (5 dollars, I don't know the answer): by searching the intenet find out whether it is well-known, and if possible find a reference for a proof
Added Feb. 24, 2025: Joseph Koutsoutis won the prize and also Lucy Martinez who found this this interesting thesis by Captain Stanley F. Florkowski III.
3. (20 dollars, I don't know the answer), Without "peeking" prove this conjecture.
Added Feb. 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C10.txt , contains the following procedures:
NAND(x,y): not (x and y)
NOT(x): NAND(x,x)
Read Don Knuth's half-a-page version of Hao Huang's Proof of the sensitivity conjecture
Subject: HomeWork#10
and an attachment
hw10FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
SimulateNAND(n,k, K)
that for K times does the following
SimulateNAND(10,5, 1000), SimulateNAND(10,10, 1000), SimulateNAND(10,20, 1000), SimulateNAND(10,50, 1000)?
(Modified Feb. 26, 2025)
Adapt RSLP(n,k) to write a procedure
Monotone(n,k,p) where n and k are positive integers and p is a rational number between 0 and 1), that has no NOT, i.e. only using AND and OR, and a typical member is [i,j,AND] or [i,j,OR] (now i ≤ j, i=j is not allowed) and for each non-input gate, the probability of AND is p and the probability of OR is 1-p)
then write
SimulateMonotone(n,k, p, K)
What did you get for
SimulateMonotone(10,5, 1/2,1000), SimulateMonotone(10,10, 1/2, 1000), SimulateMonotone(10,20, 1/2, 1000), SimulateMonotone(10,50, 1/2, 1000),
SimulateMonotone(10,5, 3/4,1000), SimulateMonotone(10,10, 3/4, 1000), SimulateMonotone(10,20, 3/4, 1000), SimulateMonotone(10,50, 3/4, 1000),
SimulateMonotone(10,5, 1,1000), SimulateMonotone(10,10, 1, 1000), SimulateMonotone(10,20, 1, 1000), SimulateMonotone(10,50,1, 1000),
Hint: In order to simulate a "loaded die" that returns true with probabality p (where p is a rational number between 0 and 1) you can use
LD:=proc(p):evalb(rand(1..denom(p))()<=numer(p)):end:
Added March 2, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C11.txt ,
Contains (in addition to old procedures from C1.txt, C2.txt and C9.txt that can be viewed via Help1(), Help2(), Help9(), respectively):
Subject: HomeWork#11
and an attachment
hw11FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
MaxNNpablo(G,r)
to write a procedure
IndNu(G)
that finds the independence number of a graph G=[n,E]
What are the independence numbers of Gnd(n,2) for n from 3 to 15? Can you make a conjecture? [5 dollars to be divided] Can you prove it?
What are the independence numbers of Gnd(n,3) for n from 3 to 15? Can you make a conjecture? [5 dollars to be divided] Can you prove it?
UpperBoundMinMaxNN(G,r,K)
that uses combinat[randcomb]({seq(i,i=1..n)},r) K times and finds the minimum of MaxNN(G,H) for K random r-element subsets of the set of vertices {1,..,n}.
What did you get for
UpperBoundMinMaxNN(Ck(8),129,5000)?
How far is it from the actual minimum of 3 (according to the sensitivity theorem)?
Added March 2, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C12.txt ,
Subject: HomeWork#12
and an attachment
hw12FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
AveLuckyVertexFriends(n,K)
that inputs a positive integer n, and for K random subsets of {1, ..., 2^n} with 2^(n-1)+1 elements gotten with
combinat[randcomb](2^n,2^(n-1)+1)
does the following
1. Finds the lucky vertex (in terms of the row number)
2. Finds the number of members of H that are joined by an edge to it
[Hint: The absolute value of An(n) is the adjacency matrix of the n-dim unit cube so you have to sum the absolute value of the entry in the row that
correpond to the lucky vertex that belong to columns of H]
Call that number FriendsOfLucky(n,H)
3. Make sure that it is always ≥ sqrt(n), according to the sensitivity lemma
If you can find an H that violates it, return FAIL.
4. Average it over all K random chices and output the average.
What did you get for
AveLuckyVertexFriends(9,100)?
Added March 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C13.txt ,
Contains the following procedures:
[The output is a pair T=[Table,Base]. To see how T[1] acts on a a member of the base do T[1][T[2][i]] where i is between 1 and 2^n.
[From previous claases: Mul(A,B) (matrix multiplcation AB in list-of-lists format. TP(A,B): Tensor product of A and B, ES(), the four famous Bell states (maximally entangled)
Subject: HomeWork#13
and an attachment
hw13FirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
HXH=Z
This can be rephrased, in our program as
Mul(Mul(C1QG()[7],C1QG()[2]),C1QG()[7])=C1QG()[4]
Find all triples 2 ≤ i,j,k ≤ 7 (there are 6^3=216 such triples) such that
Mul(Mul(C1QG()[i],C1QG()[j]),C1QG()[k])
is equal to a member of C1QG(), say C1QG()[r]. Output the set of all such quadruples [i,j,k,r] (in particular [7,2,7,4] should be a member of that set).
In other words find all such identities where a product of three (not necessarily distinct) mmembers of C1QG() equals to one of them.
How big is that set? for some 1 ≤ r ≤ 7
Mul(Mul(C1QG()[i],C1QG()[j]),C1QG()[k])=c*C1QG()[r]
Output the set of all such [i,j,k,r,c].
ApplyT(T,X,n,u)
where T=[T1,V], T1 is a table and V is nBasis(n,X), and u is an arbitrary linear combination of of members of nBasis(n,X), that uses the linearity of the table , and outputs the result of applying the linear transformation T (given as a table defined on the canonical basis), as a linear combination of the basis elements.
If T=UMtoT(TP(H,Z)), what is
ApplyT(T,X,2,X[[0,0]]+I*X[[0,1]]+2*I*X[[1,0]]+5*X[[1,1]]); ?
a[1]*a[2]=a[2]*a[1]
can be rewriiten as
add(c[pi]*a[pi[1]]*a[pi[2]], pi in permute(2))=0
where c[12]=1 and c[21]=-1,
As you know, for 2 by 2 matrices A[1] and A[2] it is usually not true that A[1]A[2]=A[2]A[1] .
But perhaps something analogous is true for them if you allow something more complicated. Can you find six numbers c[123], ..., c[321] such that
add(c[pi]*Mul(Mul(A[pi[1]],A[pi[2]]),A[pi[3]]), pi in permute(3))= [[0,0],[0,0]]
for every three 2 by matrices A[1],A[2],A[3]?
If not, can you find 24 numbers c[1234], ..., c[4321] such that
add(c[pi]*Mul(Mul(A[pi[1]],A[pi[2]]),Mul(A[pi[3]],A[pi[4]])), pi in permute(4))=[[0,0],[0,0]]
for every four 2 by matrices A[1],A[2],A[3], A[4]?
[Hint (modified March 7, 2025, 2:10pm): You have to look for 24 numbers such that the above relation holds for EVERY choice of four 2 by 2 matrices A[1],A[2],A[3],A[4]. To find 24 unknown numbers you need 24 independent homogeneous equations. By making 6 random choices (using rand(1..10)(), for example, and then writing a little procedure RM() that outputs a random 2 by 2 matrix), pick 6 random choices of quadruple of numerical 2 by 2 matrices. For each random choice you get a 2 by 2 matrix featuring the unknowns c[pi]. Then set them all equal to zero. Then use Maple's solve. If you get a not-all-zero solution it is good news, and you have a conjecture. Finally to prove it rigorously, plug in four SYMBOLIC matrices A[1],A[2],A[3],A[4].]
Added March 9, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
C14.txt contains:
Bell(C1QG()[4],C1QG()[2], -(C1QG()[2]+C1QG()[4])/sqrt(2),(C1QG()[2]-C1QG()[4])/sqrt(2),ES()[1]);
C14pi.txt contains:
LeibnitzN(N): using N terms in the Lebnitz formula to appx. Pi
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#14pi
and an attachment
hw14piFirstNameLastName.txt
and indicate whether it is OK to post. If you do not say "OK to post", it will not be posted.
JesusG(N)
that uses N terms of Jesus Guillera's amazing formula in his homepage (given in "Ramanujan notation") that computes an approximation to 128/π2.
How close is JesusG(10) to 128/π2?, How close is JesusG(100) to 128/π2?,
[Hint: Many series for Pi are of hypergeometric type: Sum(p(n)*f(n),n=0..infinity) where p(n) is a polynoial and f(n)/f(n-1) is a rational function. It is most efficient to just have the current value of f(n) and keep adding p(n)*f(n)]
Added March 13, 2025: See all Students' Pi codes
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#14
and an attachment
hw14FirstNameLastName.txt
[Modified and simplified, March 11]
Write a process
RandomBell1(K)
(1) After defining ra:=proc(K): rand(-K..K)():end: Keeping the same A0,A1,B0,B1, as in the wikipedia article
A0:=C1QG()[4],A1:=C1QG()[2],B0:= -(C1QG()[2]+C1QG()[4])/sqrt(2),B1:=(C1QG()[2]-C1QG()[4])/sqrt(2)
(2) Picks a random state (in the 2-qubit space generated by 00,01,10,11, sets V=[ra(K)+I*ra(K),ra(K)+ra(K)*I,ra(K)+I*ra(K),ra(K)+I*ra(K)]:
(3) NORMALIZE it! , i.e. divide V by its NORM. rename the new state V.
Computes Bell(A0,A1,B0,B1,V)
RandomBell(K,N)
that runs RandomBell1(K) N times and returns
(1) The average value over all N trials.
(2) The fraction of times it exceeds 2, thereby refuting Albert (and Boris and Nathan)
What did you get for
RandomBell(10,1000)?
Added March 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Today we celebrated (one day early) Pi day.
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#15
and an attachment
hw15FirstNameLastName.txt
a(n)=Sum(binomial(n-1,2*k-1)*a(2*k-1)*a(n-2*k),k=1..trunc(n/2)):
(subject to the initial condition a(1)=1).
What is
evalf([seq(2*n*a(n-1)/a(n),n=1000..1010)]) ?
Does it seem to converge to any famous constant?
Added March 23, 2025: Students' homework (that they kindly agreed to be posted) are in this directory
Contains procedure:
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#16
and an attachment
hw16FirstNameLastName.txt
and indicate whether it is OK to post.
ToffoliMatrix(): and FredkinMatrix()
that returns the appropriate 8 by 8 matrices
Sjk(j,k)
that expresses the matrix Sj,k (Eq. (4.3), p. 14) in our notation of lists-of-lists
QFTC(l)
that inputs a pos. integer n and outputs the quantum circuit of Eq. (4.4) (but replace l by n) in the same format at the output of RQC. i,e.
[n,[H,[n-1]], ....
where H is the Hadamard matrix C1QG()[7]=[[1/2*2^(1/2), 1/2*2^(1/2)], [1/2*2^(1/2), -1/2*2^(1/2)]]
Contains procedure:
FindFact(n,K): tries to find a factor of n using FindFact1(n) K times or returns FAIL (very unlikely if K is big)
ModExp(x,r,n): x^r mod n the fast way where r is given in reverse binary [2^0,2^1,2^2,...]
Please email ShaloshBEkhad at gmail dot com an email with
Subject: HomeWork#17
and an attachment
hw17FirstNameLastName.txt
and indicate whether it is OK to post.
xphi(n) mod n =1 .
Hence the order must be a divisor of phi(n). The Maple package numtheory has both phi and divisors. Write a procedure
MyOrd(x,n)
that (i) computes phi(n) (ii) finds its set of divisors, (iii) sorts them (iv) keeps trying xr mod n until it gets 1.
Take random large x and n and compare the time it takes.
Why is even this more (possibly more) clever way of computing the order of x mod n not crack RSA with a classical computer?
A weighted directed graph with n vertices can be described as an n by n matrix with non-negative entries (for the sake of simplicity, integers). Write a procedure, where the diagonal is 0 (the distance from a vertex to itself is 0)
RWG(n,K)
that generates such a matrix (as a list-of-lists)
Give a few examples by using RWG(n,10);