Friday, 24 May 2013

Wednesday, 22 May 2013

A Tally Font

Another short link. At the bottom of this page, there is a TrueType font for tally marks, and a font for calculator buttons.

Very useful for example worksheets.

Saturday, 18 May 2013

RSA Two-Key Encryption

So everything in the last seven posts has lead up to this.
The RSA Encryption Algorithm is a mathematical method of generating two encryption keys. You then encrypt a message with one key, and decrypt it using the other key.
This allows you to keep one key private, and publish the other key to the entire world.

Then there are two ways you can use these keys:
  1. You look up the public key of your friend, and encrypt a message using their public key. You have guaranteed that no-one can read the message except your friend.
  2. You encrypt a message using your private key. Everyone can read it, but no-one else but you could have sent it.
So the same technology can be used to keep secrets, and prove identity. Cool.

The Euclidean Algorithm and the Extended Euclidean Algorithm

This is the last trick needed to understand the RSA method. The first algorithm is a quick(-ish) method to find the greatest common divisor between two numbers (a and b). The second algorithm also calculates values of x and y that satisfies the following equation:
$ax + by = gcd(a,b)$

Euler-Fermat Theory and Prime-testing

As mentioned in the last post, Euler-Fermat's Theory states that for any element m in a group:
$m^{\varphi(n)} = 1 \text{ mod } n$
where $\varphi(n)$ is the totient of n.
The totient of a number is simply the number of Integers that are smaller, and coprime (i.e. no common factors).

This allows us to come up with a simple (though not foolproof) test for prime numbers.
If n is a prime number p, then the number of smaller Integers that are coprime, are all of them. Thus $\varphi(p) = p-1$ for a prime number, and $m^{(p-1)} = 1 \text{ mod } p$ should be true for all the numbers m, smaller than p.

Lagrange's Theory of Finite Groups and the Euler-Fermat Theorem.

In my Group Theory post, I stated that once a Set of mathematical elements and a mathematical operation have been proven to satisfy some basic properties, all theories, proofs and facts from the mathematical discipline of Group Theory, would automatically apply.

 Lagrange's Theory of Finite Groups states that any group can only be divided up into subgroups of the same size.

Euler-Fermat's Theorem is an application of this, that says that any number (coprime to n), rasied to a special power (called the totient of n) will give 1 mod n.

The coprime and totient properties of the second theory are a consequence of the structure of the Multiplicative Group of Integers Modulo n.

Euler's Totient Function

As mentioned in the last post, when multiplying Integers mod n, there are some Integers that can't have an inverse. My example was, that it was impossible to multiply 2 by anything, that once divided by 10, gave you a remainder of 1. Likewise for 5. And if an element doesn't have an inverse with respect to some mathematical operation, then that element can't be a member of a Group.

The Power of an Example – Modular Mathematics

Recently I took a class of students on a Physics excursion. On the trip there, I observed some of them working a Maths C assignment on modular multiplication. I knew a bit of mod mathematics from my programming experience, and was able to help them on some of the tougher concepts, but something a student said, instantly cleared up some aspects of Group Theory that I had been struggling with for years.

Group Theory and the RSA Encryption Algorithm

This is another large group of postings, focusing on the culmination of three year's private study – I finally understand the RSA Encryption Algorithm. I'm one of those people that finds mathematical concepts baffling and confusing unless I understand all aspects of it. If there's any vagueness or ambiguity anywhere, it niggles at my mind and drives me up the wall. No I don't have Aspergers', I'm just very pedantic. :-)

Anyway, I will be presenting my understanding of RSA in the following sections:

Group Theory

I'm currently reading S. Sternberg's “Group theory and physics”. I bought it about four years ago. I have notes written in it up to page 66, but only really understand about ¾ of pages 1-15 and 48-60. It's hard going, but the book does have the advantage that nearly everything important about Group Theory seems to be included.
But the basics are:
A mathematical Group consists of:
  • a Set of mathematical elements (numbers, matrices, rotations, etc.) that, in the abstract, we shall refer to here-on in by pronumerals (e, a, m ...) and
  • an operator (addition, multiplication, matrix multiplication, etc.) that we shall represent with the $\cdot$ symbol.
The Set of elements can be finite in size, or infinite. An example of this would be the (infinite Set of) Integers, and the addition operator. I will be showing an example of each Group property using this group.

Wednesday, 15 May 2013

Manual: GeoGebra 4.2 in a Nutshell - GeoGebraTube

Whoop, just what a math teacher wants, a free manual for the opensource program Geogebra (.org)
I've learnt a few new features just by having a skim through this.

Manual: GeoGebra 4.2 in a Nutshell - GeoGebraTube

Sunday, 12 May 2013

Friday, 3 May 2013

Simulating Heat and Energy

Quite recently I've found a lovely little java application on the Internet.

It's a heat simulator that allows you to investigate conduction, convection and radiation.