1. NEW INFORMATION
(over 8 hours computer run time)
Complete the following activities prior to the classroom lesson.
Optimisation
RouteXL - Fastest Roundtrip Solver calculates the optimal path to visit a range of addresses. Couriers can plan the minimum travelling distance to deliver parcels.
Encryption
Secure computer communication is provided by RSA encryption, which uses prime numbers.
Watch the video Prime Numbers & Public Key Cryptography and briefly describe how prime numbers are useful in cryptography or internet security.
Watch How RSA & PKI works and the math behind it, and define the 'public key' and the 'private key'.
Note: Even though the process is complex, as shown in the video, the public key is partly the multiple of the two selected prime numbers, and the private key uses the same two prime numbers for decryption. The encryption process depends on the difficulty of factorizing very large prime numbers.
2. GOAL
Classically, some optimisation and encryption problems can only be solved through trial and error and making approximations, but this can take a very long time (potentially, millions if not billions of years). Scientists are searching for new techniques to solve these problems in a reasonable period of time.
3. ACCESS PRIOR KNOWLEDGE
Algorithms solve problems a step at a time. Visit this wikipedia page and answer the following questions. (The simulation on the website graphically illustrates the operation of the algorithm.)
1. What is the algorithm called?
2. What does the algorithm do?
3. When was it written?
3. NEW INFORMATION
Optimisation Algorithms
In class, discuss the Travelling Salesman problem and your data from the OptiMap - Fastest Roundtrip Solver.
1. What are the factors that determine the time taken for the program to calculate the optimal path?
2. What did you find in terms of calculation time as the number of locations increased?
3. At what number of locations is the calculation time likely to be in the years or centuries?
Algorithms have been designed that find approximate solutions for optimisation problems in a reasonable time, but the closer they are to the optimal solution, the longer they take. Often the approximation algorithm will state only the probability of a solution being the most efficient.
Encryption
Discuss the videos viewed prior to the lesson and the role of prime numbers in RSA encryption.
Discuss how encryption and optimisation problems demonstrate some limitations of classical computing.
Quantum Computing
Quantum computing has the potential to allow optimisation algorithms and the factoring of very large numbers to be carried out in a reasonable time, which has significant implications for internet security. To understand quantum computing, we need to first have a brief look at some quantum mechanics.
4. APPLICATION TASK
The following numbers have prime factors. Use a stopwatch to record how long it takes you to find the prime factors of these numbers.
Research some other practical uses of optimisation programs.
5. GOAL REVISITED
Discuss your findings. While quantum computing could potentially solve optimisation problems, it could possibly cause encryption problems. We need to have a brief overview of some quantum mechanics to understand the reason for this. .