An Approach to Integer Factorisation with Sample Programs - Info and Reading Options

Snippets and Summary:

My undergraduate maths course on Number Theory was given by a particularly enthusiastic lecturer. There were about a hundred students on the course and the lecture theatre had three large blackboards across the front. This became the setting for a most memorable maths lecture. Starting on the extreme left of the first board, the lecturer invited the class to call out single numbers. As we did so, he wrote them onto the boards as one long integer. When we tired of calling out digits, the lecturer stood back and surveyed the resulting integer. Then the magic began. Without stopping for breath, and without any written working, the lecturer wrote down the prime decomposition for the enormous number. By the time the problem was reduced to the final pair of primes, there was only one student, somewhere at the back of the class, who had managed to keep pace. When tutoring maths I noticed that factorising seems to be a process which variously frightens, fascinates, or delights my students. The simple systematic rules which I have long taken for granted are a novelty to them. It is rather less than obvious to a beginner that the square root of the number sets an upper bound in the search for factors. When I tell them that they need only restrict their attention to prime divisors is as though they had been given a box of chocolates. Inspired by the responses of my students, my own curiosity became the motivation for this work. The following account is offered as my exploration of the subject of factorisation insofar as it applies to integers. I have described the application of simple algorithms which seek to accelerate the solution of the problem of factorisation, and have described some physical analogues. The work is not intended to be exhaustive. For those interested in this particular mathematical challenge, there are many avenues for development. The mathematics employed should be understandable by able senior high school pupils and amateur mathematicians. J W Cahill