Mathematics

This is our Mathematics page with links to various topics we've written up. We'll keep adding to this.

The Euclidean Algorithm and the Extended Euclidean Algorithm

We look at the Euclidean algorithm and how to use it. We solve typical exam questions and show how to do the calculations by hand. We then look at how it can be adapted to find the modular inverse of a number and the extended Euclidean algorithm.

The Chinese Remainder Theorem (CRT) and Gauss's algorithm

We look at the Chinese Remainder Theorem (CRT), Gauss's algorithm to solve simultaneous linear congruences, a simpler method to solve congruences for small moduli, and an application of the theorem to break the RSA algorithm when someone sends the same encrypted message to three different recipients using the same exponent of e=3.

Using the CRT with RSA

We look at how the Chinese Remainder Theorem (CRT) can be used to speed up the calculations for the RSA algorithm. We show how the CRT representation of numbers in Z_n can be used to perform modular exponentiation about four times more efficiently using some extra values pre-computed from the prime factors of n, and how Garner's formula is used.

Elementary Number Theory

These useful principles of elementary number theory are helpful in understanding the theory behind the RSA algorithm.

Dirichlet character table generator

This page generates a table of non-zero values for Dirichlet characters modulo k up to k=62.

Coding Theory: transforming a generator matrix to standard form

This page uses the techniques described in Chapters 5 and 7 of Raymond Hill's A First Course in Coding Theory (OUP, 1986) to transform a generator matrix or parity-check matrix of a linear [n,k]-code into standard form. It works over GF(q) for q = 2,3,4,5,7,11.

Undirected Graphs and Networks

Some notes we prepared in 2003 for students doing Further Maths in the Victorian Certificate of Education (VCE).

To comment or provide feedback, please Send us a message.

This page last updated 4 January 2012