You are currently browsing the category archive for the ‘investigation’ category.
The mathematics behind blockchain, bitcoin and NFTs.
If you’ve ever wondered about the maths underpinning cryptocurrencies and NFTs, then here I’m going to try and work through the basic idea behind the Elliptic Curve Digital Signature Algorithm (ECDSA). Once you understand this idea you can (in theory!) create your own digital currency or NFT – complete with a digital signature that allows anyone to check that it has been issued by you.
Say I create 100 MATHSCOINS which I sell. This MATHSCOIN only has value if it can be digitally verified to be an original issued by me. To do this I share some data publicly – this then allows anyone who wants to check via its digital signature that this is a genuine MATHSCOIN. So let’s get into the maths! (Header image generated from here).
Elliptical curves
I will start with an elliptical curve and a chosen prime mod (here we work in mod arithmetic which is the remainder when dividing by a given mod). For this example I will be in mod 13 and my curve will be:
First I will work out all the integer solutions to this equation. For example (7,5) is a solution because:
The full set of integer solutions is given by:
Now we define addition of 2 non equal points (p_1, p_2) and (q_1, q_2) on the curve mod M by the following algorithm:
And we define the addition of 2 equal points (p_1, p_2) on the curve mod M by the following algorithm:
So in the case of (8,8) if we want to calculate (8,8) + (8,8) this gives:
This is a little tedious to do, so we can use an online generator here to calculate the full addition table of all points on the curve:
This shows that (say) (7,5) + (8,5) = (11,8) etc.
I can then chose a base point to find the order of this point (how many times it can be added to itself until it reaches the point at infinity). For example with the base point (8,8):
We can also see that the order of our starting point A(8,8) is 7 because there are 7 coordinate points (including the point at infinity) in the group when we calculate A, 2A, 3A…
ECDSA: Elliptic Curve Signatures
So I have chosen my curve mod M (say):
And I choose a base point on that curve (p_1, p_2) (say):
And I know the order of this base point is 7 (n=7). (n has to be prime). This gives the following:
I now chose a private key k_1:
Let’s say:
This is super-secret key. I never share this! I use this key to generate the following point on the curve:
I can see that 5(8,8) = (11,5) from my table when repeatedly adding (8,8) together.
Next I have some data z_1 which I want to give a digital signature to – this signature will show anyone who examines it that the data is authentic, has been issued by me and has not been tampered with. Let’s say:
I choose another integer k_2 such that:
Let’s say:
I am now ready to create my digital signature (s_1, s_2) by using the following algorithm:
Note, dividing by 2 is the same as multiplying by 4 in mod 7 (as this is the multiplicative inverse).
I can then release this digital signature alongside my MATHSCOIN (represented by the data z_1 = 100). Anyone can now check with me that this MATHSCOIN was really issued by me.
Testing a digital signature
So someone has bought a MATHSCOIN direct from me – and later on wants to sell to another buyer. Clearly this new buyer needs to check whether this is a genuine MATHSCOIN. So they have check the digital signature on the data. To allow them to do this I can share all the following data (but crucially not my private key):
This gives:
To verify someone then needs to do the following:
To verify that the data z_1 has a valid digital signature we need:
So with the shared data we have:
This verifies that the data had a valid digital signature – and that the MATHSCOIN is genuine! This is basically the foundation of all digital assets 
which require some stamp of authenticity.
In real life the numbers chosen are extremely large – private keys will be 256 digits long and primes very large. This makes it computationally impossible (at current speeds) to work out a private key based on public information, but still relatively easy to check a digital signature for validity.
I have also made some simple Python code which will provide a digital signature as well as check that one is valid. You can play around with these codes here:
(1) Digital signature code, (2) Checking a digital signature for validity
So time to create your own digital currency!
Finding planes with radar
PlusMaths recently did a nice post about the link between ellipses and radar (here), which inspired me to do my own mini investigation on this topic. We will work in 2D (with planes on the ground) for ease of calculations! A transmitter will send out signals – and if any of these hit an object (such as a plane) they will be reflected and received by a receiver. This locates the object as somewhere on the ellipse formed with the receiver and transmitter as the 2 foci. When we add a second receiver as shown above then if both receivers receive a signal, then we can narrow down the location of the object as the intersection of the 2 ellipses.
So, for this mini exploration I wanted to find the equations of 2 ellipses with a shared focus so that I could plot them on Desmos. I then would be able to find the intersection of the ellipses in simple cases when both ellipses’ major axis lies on the x axis.
Defining ellipses
For an ellipse centred at the origin shown above, with foci at c and -c we have:
where c is linked to a and b by the equation:
Rotating an ellipse
Next we can imagine a new ellipse in a coordinate system (u,v)
This coordinate system is created by rotating the x and y axis by an angle of theta radians anticlockwise about the origin. The following matrix transformation achieves this rotation:
This therefore gives:
and we can substitute this into our new coordinate system to give:
When we plot this we can therefore rotate our original ellipse by any given theta value:
We can use basic Pythagoras to see that the focus point c will become the point c1 shown above with coordinates:
By the same method we can see that the point c2 will have coordinates:
Transformation
Next we want to translate this new ellipse so that it shares a focus point with our original green ellipse. To do this we need to translate the point c2 to the point c. This is given by the translation:
So we can therefore translate our ellipse:
Which becomes:
When we plot this we get:
This then gives the 2nd ellipse in blue which does indeed share a focus point at c:
Finding points of intersection
The coordinates of when the 2 ellipses intersect is given by the solution to:
This looks a bit difficult! So let’s solve an easier problem – the points of intersection when the theta value is 0 (i.e when the ellipses both lie on the x axis). This simplifies things to give:
and we can find the y coordinates by substituting this into the original ellipse equation.
So the coordinates of intersection are given by:
So – in the above case we would be able to narrow down the location of the plane to 2 locations. With a 3rd ellipse we could pinpoint the location exactly.
Proving Pythagoras Like Einstein?
There are many ways to prove Pythagoras’ theorem – Einstein reputedly used the sketch above to prove this using similar triangles. To keep in the spirit of discovery I also just took this diagram as a starting point and tried to prove this myself, (though Einstein’s version turns out to be a bit more elegant)!
Step 1: Finding some links between triangles
We can see that our large right angled triangle has sides a,b,c with angles alpha and beta. Hopefully it should also be clear that the two smaller right angled triangles will also have angles alpha and beta. Therefore our triangles will all be similar. It should also be clear that the area of the 2 small triangles will be the same as the area of the large triangle.
Step 2: Drawing a sketch to make things clearer:
It always helps to clarify the situation with some diagrams. So, let’s do that first.
Step 3: Making some equations
As the area of the 2 small triangles will be the same as the area of the large triangle this gives the following equation:
We also can make the following equation by considering that triangles 2 and 3 are similar
We can now substitute our previous result for x into this new equation (remember our goal is to have an equation just in terms of a,b,c so we want to eliminate x and y from our equations).
We can also make the following equation by considering that triangles 1 and 2 are similar:
And as before, our goal is to remove everything except a,b,c from these equations, so let’s make the substitution for y using our previous result:
And if by magic, Pythagoras’ theorem appears! Remember that the original a,b,c related to any right angled triangle with hypotenuse c, so we have proved that this equation must always be true for right angled triangles.
You can explore some other ways of proving Pythagoras here. Which is the most elegant?
Finding the average distance in a polygon
Over the previous couple of posts I’ve looked at the average distance in squares, rectangles and equilateral triangles. The logical extension to this is to consider a regular polygon with sides 1. Above is pictured a regular pentagon with sides 1 enclosed in a 2 by 2 square. The points N and O represent 2 randomly chosen points which we find the distance between. On average what is the distance between these randomly chosen points N and O?
Starting with a hexagon
It’s a little easier to start with a hexagon as we get some nicer coordinate points. So, our first challenge is to find the coordinates of a regular hexagon with sides 1. Luckily we can use the complex roots of unity to do this. We start by finding the 6th roots of unity and then converting these to coordinates in an Argand diagram:
This then allows us to plot the following:
We can then work out the inequalities which define the inside of the hexagon when we generate points within the 2×2 square centred at (0,0). This gives:
We can then run the following code to find the average distance:
This gives the following result:
We can check this result as the exact value is:
which is 0.8262589495. So we can see we are accurate here to 3 sf.
Pentagon
For the pentagon we can find the coordinates by finding the 5th roots of unity:
We then need to scale all coordinate points by a factor, because in a pentagon the distance from the centre to the points is not 1 (as is the case in roots of unity). We can find the distance from the centre to the edge of a pentagon by the following trigonometry:
So, when we scale all coordinate points by this factor we get:
And we can then do the same method as before and run the following Python code:
This gives:
n-sided polygon
We can now consider an n-sided polygon with sides 1. Let’s start with the values we’ve found for an equilateral triangle (0.364), a square (0.522), a pentagon (0.697) and a hexagon (0.826.
When we plot these they appear to follow a linear relationship:
average distance = 0.14n
We can check that this is correct by considering the fact that an n sided polygon will approximate a circle when n gets large. So an n sided polygon with sides length 1 can be approximated by a circle with circumference n. This allows us to work out the radius.
We can then substitute this into the equation for the average distance of 2 points in a circle.
So we would expect the average distance between 2 points in a regular polygon of sides 1 to approach the equation (as n gets large):
average distance = 0.144101239n
And we’ve finished! Everything cross-checks and works nicely. We’ve been able to use a mixture of complex numbers, geometry, coding and trigonometry to achieve this result.
Finding the average distance in an equilateral triangle
In the previous post I looked at the average distance between 2 points in a rectangle. In this post I will investigate the average distance between 2 randomly chosen points in an equilateral triangle.
Drawing a sketch.
The first step is to start with an equilateral triangle with sides 1. This is shown above. I sketched this using Geogebra – and used some basic Pythagoras to work out the coordinates of point C.
I can then draw a square of sides 1 around this triangle as shown above. I’m then going to run a Python program to randomly select points and then work out the distance between them – but I need to make sure that the 2 points chosen are both inside this triangle. For this I need to work out the equation of the line AC and CB.
Using basic coordinate geometry we can see that the line AC has equation y = √3x. We want the inequality y < √3x so that we are on the correct side of this line.
The line BC has equation y = -√3x + √3. Therefore the triangle must also satisfy the inequality y < -√3x + √3.
I can then run the following code on Python, with finds the average distance between points (a,c) and (b,d) both within the unit square but also subject to the 2 inequality constraints above.
When this is run it performs 999,999 trials and then finds the average distance. This returns the following value:
So we can see that the average distance is just over a third of a unit.
Finding the average distance of an equilateral triangle of length n.
We can then draw the sketch above to find the equation of lines AC and CB for an equilateral triangle with lengths n. This leads to the following inequalities:
y < √3x
y < -√3x + √3n
So we can then modify the code as follows:
This then returns the average distances for equilateral triangles of sizes 1 to 10.
And when we plot this on Desmos we can see that there is a linear relationship:
The regression line has gradient 0.36 (2sf) so we can hypothesise that for an equilateral triangle of size n, the average distance between 2 points is approximately 0.36n.
Checking the maths
I then checked the actual equation for the average distance between 2 points in an equilateral triangle of sides n:
This gives us:
So we can see that we were accurate to 2 significant figures. So this is a nice mixture of geometry, graphing and computational power to provide a result which would be otherwise extremely difficult to calculate.
Plotting Pi and Searching for Mona Lisa
This is a very nice video from Numberphile – where they use a string of numbers (pi) to write a quick Python Turtle code to create some nice graphical representations of pi. I thought I’d quickly go through the steps required for people to do this by themselves.
Firstly you can run the Turtle code on trinket.io. If you type the above code this will take the decimal digits of pi one at a time and for each one move forward 10 steps and then turn by 36 degrees times by that digit. So for example the 1 will lead to a right turn of 36 degrees and the 4 will lead to a right turn of 36 x 4 = 144 degrees.
Next it would be nice to have more digits of pi to paste in rather than type. So we can go to the onlinenumbertools website and generate as many digits of pi as we want. Select them to be comma separated and also to not include the first digit 3. You can then copy and paste this string in place of the 1,4,1 in the code above.
1000 digits of pi
If we run this program after pasting the first 1000 digits of pi we get (after waiting a while!) the above picture. There are a number of questions that they then raise in the video – if this program was ran infinitely long would the whole screen eventually be black? Would this create every possible image that can be created by 36 degree turns? Would it be possible to send this picture (say to an alien civilization) and for the recipient to be able to reverse engineer the digits of pi?
2000 digits of pi
If you increase the digits of pi to around 2000 you get the above picture. The graph spends a large time in the central region before finally “escaping” to the left. It then left my screen at the top.
3000 digits of pi
We can see that the turtle “returned” from off the top of the screen and then joined back up with the central region. This starts to look like a coastline – maybe the south of the UK!
Different bases: Base 3
We can consider the digits of pi in base three – which means that they are all equivalent to 0,1,2. This means that we can use these to specify either 0 degree, 120 degree or 240 degree turns. We can change the code as shown above to achieve this. Note the i%3 gives i mod 3. For example if the digit is 8, then 8 mod 3 is 2 (the remainder when 8 is divided by 3) and so this would turn 120 x 2 = 240 degrees.
This then creates a pattern which looks similar to the Sierpinski triangle fractal design:
Base 4
Using a similar method, we can create the following using a base 4 design:
This creates what looks like a map layout.
Base 5:
In base 5 the turtle quickly departed from my screen! With turns of 72 we don’t see the tessellating shapes that we do with base 3 and 4.
Base 6:
With a 60 degree turn we can now see a collection of equilateral triangles and hexagons.
You can explore with different numbers and different bases to see what patterns you can create!
Witness Numbers: Finding Primes
The Numberphile video above is an excellent introduction to primality tests – where we conduct a test to determine if a number is prime or not. Finding and understanding about prime numbers is an integral part of number theory. I’m going to go through some examples when we take the number 2 as our witness number. We have a couple of tests that we conduct with 2 – and for all numbers less than 2047 if a number passes either test then we can guarantee that it is a prime number.
Miller-Rabin test using 2 as a witness number:
We choose an odd number, n >2. First we need to write it in the form:
Then we have to conduct a maximum of 2 different tests:
If either of the above are true then we have a prime number.
Testing whether n = 23 is prime.
First we need to write 23 in the following form:
Next we need to check if the following is true:
Remember that mod 23 simply means we look at the remainder when we divide by 23. We can do this using Wolfram Alpha – but in this case let’s see how we could do this without a calculator:
Therefore this passes the test – and we can say that it is prime.
Testing whether 1997 is prime
For 1997 we have:
So we need to first test if the following is true:
However using Wolfram Alpha we get:
So this fails the first part of the test.
Trying the second part of the test, we need:
We have already tested the case when r=0 (this gives the earlier result), so just need to look at what happens when r=1. Again we use Wolfram Alpha to get:
This passes the 2nd part of the test and so confirms that 1997 is prime.
What happens with 2047?
2047 is not prime as we can write it as 2 x 3 x 11 x 31. However it is the first number for which the witness 2 gives a false positive (i.e we get a positive result even though it is not prime). We write 2047 as:
But we do indeed get:
So we can call 2047 a pseudoprime – it passes this prime number test but is not actually prime.
Larger primes
For numbers larger than 2047 you can combine witnesses – for example if you use both 2 and 3 as your witness numbers (and regard a positive result as at least one of them returning a positive result) then this will find all primes for n < 1,373,653.
More interestingly for extremely large numbers you can use this test to provide a probability estimate for the likelihood that a number is prime. Lots to explore here!
Maths Games and Markov Chains
This post carries on from the previous one on Markov chains – be sure to read that first if this is a new topic. The image above is of the Russian mathematician Andrey Markov [public domain picture from here] who was the first mathematician to work in this field (in the late 1800s).
Creating a maths game
Above I have created a simple maths game – based on the simplified rules of Monopoly. All players start at Go. All players roll 2 dice and add the scores and move that number of squares forward (after square 9 you move to square 1 etc). If you roll a double you get sent to Jail (square 9) – but are released on your next turn. If you land on square 5 you immediately are transported to Go (and end your turn).
The question is, if we play this game over the long run which famous mathematician will receive the most visits? (In order we have Newton (2), Einstein (3), Euler (4), Gauss (6), Euclid (7), Riemann (8)).
Creating a Markov Chain
The first task is to work out the probabilities of landing on each square for someone who is starting on any square. Using a sample space diagram you can work out the following:
p(move 2) = 0. p(move 3) = 2/36. p(move 4) = 2/36. p(move 5) = 4/36. p(move 6) = 4/36. p(move 7) = 6/36. p(move 8) = 4/36. p(move 9) = 4/36. p(move 10) = 2/36. p(move 11) = 2/36. p(move 12) = 0. p(double) = 6/36.
We can see that the only variation from the standard sample space is that we have separated the doubles – because they will move us to jail.
Matrix representation
I now need to create a 9×9 matrix which represents all the states of the game. The first subscript denotes where a player starts and the second subscript denotes where a player finishes after 1 turn. So for example m_13 denotes that a player will start on square 1 and finish on square 3, and p(m_13) is the probability that it will happen. If we do some (rather tedious!) calculations we get the following matrix:
We can note that the probability of ending up on square 5 is 0 because if you do land on it you are transported to Go. Equally you can’t start on square 5 – so the probability of starting there and arriving somewhere else is also 0. Also note that each row represents all possible states – so always adds up to 1.
Now all I need to do is raise this matrix to a large power. If I raise this to the power 100 this will give me the long term probabilities of which square people will land on. This will also give me a 9×9 matrix but I can focus on the first row which will tell me the long term probabilities of where people end up when starting at Go. This gives:
So I can see that the long term probabilities (to 3sf) show that Jail is going to be visited around 40% of the time, followed by Go (around 26.7% of the time). And the mathematician that receives the most visits will be Euclid (around 16.8%). We can logically see why this is true – if 40% of the time people are in Jail, then the next roll they are most likely to get a 7 which then takes them to this square.
Extensions
Clearly we can then refine our game – we could in theory use this to model the real game of Monopoly (though this would be quite complicated!) The benefit of Markov chains is that it is able to reduce complex rules and systems into a simple long term probability – which is hugely useful for making long term predictions.
Life on the Beach with Markov Chains
Markov chains are exceptionally useful tools for calculating probabilities – and are used in fields such as economics, biology, gambling, computing (such as Google’s search algorithm), marketing and many more. They can be used when we have the probability of a future event dependent on a current event. The image above is of the Russian mathematician Andrey Markov [public domain picture from here] who was the first mathematician to work in this field (in the late 1800s).
Beach life
The picture above is an example of a situation which can be modeled using a Markov chain. We have two states: Beach (state 1) and Home (state 2). In our happy life we spend all the hours of the day in either one of these two states. If we are on the beach then the probability we remain on the beach in one hour is 0.6 and the probability we go home in one hour is 0.4. If we are at home the probability we remain at home in one hour is 0.8 and the probability we go to the beach is 0.2. Hopefully you can see how this information is represented above.
Using matrices
First we need to represent our information in a matrix form. A general 2×2 matrix is written as:
Where the subscript tells you the row and column (e.g. a_12 tells you it is in the first row and 2nd column).
For our Markov chain we define the following matrix:
Here m_11 is the situation of starting in state 1 and moving to state 1. m_12 is the situation of starting in state 1 and moving to state 2. Therefore p(m_12) is the probability of starting in state 1 and moving to state 2. So for our beach existence we have:
The 0.6 shows that if we are already on the beach we have a 0.6 chance of still being on the beach in one hour.
Where will we be in the future?
The benefit of Markov chains is that they allow us to utilise computer power to now calculate where someone will be in the future – simply by taking the power of the matrix. To find the probabilities after 2 hours I can square my matrix:
Using the rules of matrix multiplication this then gives:
Which we can the calculate as:
I’ve used arrow notation here to represent the start and end state so p(m_1 arrow 1) means starting at 1 and ending at 1 after 2 hours. We can see that for someone who started in the beach, the chance of them being on the beach in 2 hours is 0.44. Equally the probability of someone who started in the house being on the beach in 2 hours is 0.28.
I can then carry on with matrix multiplication to work out where someone will likely be for any given number of hours in the future.
p(m_1 arrow 1) means starting at 1 and ending at 1 after n hours. So for example if I want to see where someone will be in 24 hours I simply do:
We can see that now it doesn’t actually matter (to 3sf anyway) where someone started – if they started on the beach there is a 0.333 chance they are on the beach in 24 hours, if they started in the house there is also a 0.333 chance they are on the beach in 24 hours. So I can conclude that as the number of hours increase towards infinity that the person in this scenario would spend 1/3 of their time on the beach and 2/3 of their time at home – not a bad life!
A more demanding beach life
We can see that things get much more complicated, even by adding an extra state. Now we have 3 possible states, Beach (state 1), Home (state 2) and SCUBA (state 3). This time we need a 3×3 matrix:
and as before we define our probability matrix as:
So from our diagram we have the following:
For example the 0.8 in row 2 column 2 shows that there is a 0.8 chance of starting in state 2 (Home) and ending in state 2 (Home) in one hour.
Then using our same notation we have:
Which shows that after 2 hours there is (for example) a 0.19 chance that someone who started in state 2 (Home) is now found in state 1 (Beach).
After 24 hours we have the following matrix:
So we notice the same situation as last time – as the number of hours increase it gets less important where we started from – we can see that to 3sf it doesn’t now matter where we started – the probability after 24 hours of being found on the beach is 0.407, the probability of being found at home is 0.333 and the probability of being found diving is 0.260.
Hopefully this is a quick example to demonstrate the power of Markov chains in working with probabilities. There is a lot more to explore (maybe in another post!)
Spotting fake data with Benford’s Law
In the current digital age it’s never been easier to fake data – and so it’s never been more important to have tools to detect data that has been faked. Benford’s Law is an extremely useful way of testing data – because when people fake data they tend to do so in a predictable way. Benford’s Law looks at the probability that a number in certain data set (many measurements, street address, stock prices etc.) begins with a given number (its leading digit). Whilst we might expect the leading digits (d) would be equally likely occur, in reality they follow the following equation:
So for example we can see that a leading digit of 1 is much more likely than a leading digit of a 9:
Testing some data
I wanted to test some data to see if it did indeed follow Benford’s Law. So, I downloaded an Excel file with 531 data points from the CDC website. This gave the moving 7-day average Covid cases per 100,000 people for every day from 12th March 2020 to 3rd October 2021. I then used the nice Excel techniques shown above in the video to manipulate the data into a useful form. Once this had been done I could then use Desmos to plot this data (dot plot and left aligned frequency histogram). You can see this data below:
The red curve is the continuous (rather than discrete) curve created by working out the expected frequencies for each digit. On Desmos I generated this by the following equation:
We can see that our data largely follows our expected curve – so we would not have any evidence to suggest faked data! We could conduct a Chi-Squared test to measure the goodness of fit of our data (this is also explained in the video).
Conclusion
This is a simple but effective method to test for faked data – if data fails this test it doesn’t necessarily mean it was faked (eg. data on heights of men in cm will clearly have nearly all 1s as leading digits!) but most non-random real life data measurements do follow this rule. Try to find your own data (try to do this with a large data set) and try for yourself.
IB Maths Resources from Intermathematics 
