Complexity & Chaos 165 facebook.com/AlgoRythmics Intercultural Computer Science Education a[0] afl] a2) a[3] al4] af5] a[6) al{7] a[8] a[9]) ™~ f . 6 [ ye i. BN sw TAA RA AARP na a, vt fic Created at Sapientia University (in cooperation with "Maros Mivészegyiittes”) Bubble Sort Ballet The Hardest Problems You probably hope cracking the encryption used to secure the Internet is one of the hardest problems known to man but I’m sorry to tell you it is not. When you use your credit card to buy something from an online shop, your web browser changes from http to https, the ‘s’ stands for secure. The data you send to the Internet is coded using a system developed in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of MIT, which is why it is called RSA encryption. Any information you send is raised to the power of a very large number - usually around one hundred digits long. Raising something to the power simply means multiplying it by itself that many times. What makes decrypting a message hard is that division is a slow process; it is called ‘long division for a reason. It turns out there is no way to speed it up on a conventional computer so, unless you know the right number to divide by you will have to try every number. It is this that makes decrypting RSA messages hard. Although RSA messages are difficult to decipher, they are nowhere near the hardest problems. That accolade is commonly believed to go to non-deterministic polynomial problems known as ‘NP’ problems. NP problems are easy to describe but fiendishly difficult to solve. Nondeterministic means each time you come to a branch in the problem there is no way to tell which branch is the best to pursue without exploring it all the way to the end. It’s the same as a maze; at each junction in the maze you can decide which path to take, but the junction gives you no HOUSE_OVERSIGHT_015855