top drag and drop web page creator

Lesson 6

Optimisation and Encryption

1. NEW INFORMATION

(over 8 hours computer run time)

Complete the following activities prior to the classroom lesson.

Optimisation

OptiMap-Fastest Roundtrip Solver calculates the optimal path to visit a range of addresses. Couriers can plan the minimum travelling distance to deliver parcels.

• Zoom into a suburban area and select 4 random addresses. Run the simulation and use a stopwatch to time how long the program takes to show the optimal path. Run the simulation for 8, 16, 20 addresses and so on. Record the time taken for each run. When you get to half an hour, run it once more with another 4 addresses. You may have to run this overnight.
• This is known as the Travelling Salesman problem, and is a classic algorithmic problem in the field of computer science.

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.

The following numbers have prime factors. Use a stopwatch to record how long it takes you to find the prime factors of these numbers.

• 21, 77, 143, 899 and 12371.