Algorithmic Thinking: Arithmetic and Cryptography
On January 17th, 2025, LUMS Math Circle hosted an engaging Math Circle event, "Algorithmic Thinking: Arithmetic and Cryptography," which was facilitated by Dr. Imdad ullah Khan and Dr. Malik Jahan Khan. The event was designed to introduce school-aged children to fundamental concepts in computer science and mathematics through engaging activities and discussions.
The event began with a simple addition challenge using Roman numerals (MDCCLXV + CCLXXXVI), which led to a discussion about the efficiency of positional number systems and the nature of computation itself. The definition of computation was presented as "Processing information by applying a finite set of rules," highlighting that computation is not solely about devices but rather problem-solving.
Key topics and activities included:
Addition and Algorithms: The children explored addition using paper and pencil arithmetic, counting the number of single-digit addition operations. They discovered on their own that adding two n-digit numbers requires at least n operations and at most 2n-1 operations.
Multiplication and Efficiency: The event covered different methods of multiplication, including repeated addition and long multiplication. The number of single-digit multiplication operations was shown to be n times m, where n and m are the number of digits in the two numbers. The discussion highlighted that long multiplication is more efficient than repeated addition, requiring fewer steps.
Inverse Problems: The concepts of inverse operations were introduced through problems like "If C = A + B, what are possible values of A and B?" and "If C = A × B, what are possible values of A and B?". This led to a discussion of the difficulty of factorization, which is the inverse of multiplication.
Cryptography and Coin Toss: The event concluded with an intriguing problem of a coin toss over the phone. Alice and Bob were introduced in a scenario, in which they use the difficulty of factorization to ensure fair play in a coin toss. Alice sends Bob a number which is the product of two prime numbers; the properties of these primes depend on whether Alice chooses heads or tails. This was designed to show how the difficulty of factoring large numbers is used in cryptographic applications.
The event effectively illustrated algorithmic thinking, emphasizing that the focus is not on the speed of computers, but on the efficiency of the methods. The children were introduced to the concept that even seemingly simple tasks, such as addition and multiplication, have underlying algorithms that can be analyzed for efficiency.
This event provided a valuable opportunity for students to engage with mathematical and computational concepts interactively. It successfully linked simple arithmetic to the complex world of cryptography, highlighting the fundamental role of algorithms in computer science.
The success of this session was made possible through the efforts of Dr. Imdad ullah khan, Dr. Malik Jahan Khan, and the organizational support of Ms. Noreen Sohail, Mr. Qamar Hussain, and Mr. Javaid Qayyum (the author of this email).
Here are some highlights from the event:
