Binary, algorithms, cryptography and data science

Mathematics inside the machine

Every text message, photo, bank transfer and online class is stored and sent as numbers. Computers use only two symbols, 0 and 1, because a switch inside a chip is either off or on. This lesson shows how numbers are written for computers, how computers follow exact steps, and how mathematics keeps information correct and secret.

Binary and hexadecimal

Binary uses powers of 2. 1011 is 8 + 0 + 2 + 1 = 11. To convert 25, take out powers of 2: 16 + 8 + 1, which is 11001.

Hexadecimal uses powers of 16, with A to F for 10 to 15. 2F is 2 × 16 + 15 = 47.

Our everyday system is decimal, or base 10: the places are 1, 10, 100 and so on. Binary, or base 2, works the same way with the places 1, 2, 4, 8, 16, 32, 64, … each twice the one before. The binary number 1100100 has 1s in the 64, 32 and 4 places, so it is 64 + 32 + 4 = 100.

Bits and bytes

One binary digit is a bit, and 8 bits make a byte. Each extra bit doubles the number of patterns, so n bits can represent 2ⁿ different values. One byte has 2⁸ = 256 patterns, enough for the numbers 0 to 255 or for the letters, digits and symbols of a keyboard.

Why hexadecimal

Long strings of bits are hard to read, so programmers group them in fours. Four bits have 16 patterns, exactly one hexadecimal digit. The byte 1111 0000 is F0 in hexadecimal, which is 15 × 16 + 0 = 240. Colours on web pages are written this way: #FF0000 means full red, no green and no blue.

Adding in binary

Binary addition follows four facts: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 10 (write 0 and carry 1), and 1 + 1 + 1 = 11 (write 1 and carry 1). Add the columns from the right, as in decimal. For 10110 + 1101, the columns give 1, 1, then 0 carry 1, 0 carry 1, 0 carry 1, and a final 1: the sum is 100011. As a check, 10110 is 22, 1101 is 13, and 22 + 13 = 35 = 32 + 2 + 1.

1. Algorithms

An algorithm is a finite list of exact steps that solves a problem. Binary search halves a sorted list at each step, so it needs at most 10 comparisons for 1,023 items.

A good algorithm has a few properties: it takes some input, produces an output, every step is definite so there is no guessing, and it always finishes. A cooking recipe is close to an algorithm; a computer program is an algorithm written in a language a machine can run.

Algorithms are compared by how much work they need as the input grows. Linear search checks items one by one, so a list of 1,000,000 names may need 1,000,000 comparisons. Binary search on the same sorted list needs at most 20, because 2²⁰ = 1,048,576 is more than a million. That is why search engines and phone contact lists keep their data sorted.

2. Modular arithmetic

a mod n is the remainder when a is divided by n. 23 mod 7 = 2. Check digits and ciphers both rely on it.

A clock is the everyday example. Five hours after 9 o’clock it is 2 o’clock, because 9 + 5 = 14 and 14 mod 12 = 2. Days of the week work mod 7: 100 days after a Monday, 100 mod 7 = 2, so it is a Wednesday.

Two numbers are congruent mod n when they leave the same remainder. We write 17 ≡ 5 (mod 12), since both leave 5. You can add or multiply first and take the remainder at the end, or take remainders along the way; the answer is the same. For a power, 3⁴ = 81 and 81 mod 5 = 1.

Check digits

A check digit is an extra digit added to a code so that typing errors can be caught. A 13-digit ISBN on a book uses the weights 1, 3, 1, 3, … on its first 12 digits, and the check digit makes the weighted total a multiple of 10. For 978-971-234-567, the weighted sum is 9 + 21 + 8 + 27 + 7 + 3 + 2 + 9 + 4 + 15 + 6 + 21 = 132. The next multiple of 10 is 140, so the check digit is 8. If one digit is typed wrongly, the total is no longer a multiple of 10 and the scanner rejects it. Barcodes on groceries and the numbers on bank cards use similar checks.

3. Cryptography

• Caesar cipher: shift each letter by a fixed amount. With shift 3, CAT becomes FDW.
• Public-key cryptography (RSA): anyone can encrypt with the public key, but only the holder of the private key can decrypt.

Cryptography is the study of keeping messages secret. The original message is the plaintext, the scrambled message is the ciphertext, and the secret that turns one into the other is the key.

Caesar ciphers and their weakness

Number the letters A = 0, B = 1, …, Z = 25. A Caesar cipher with key k sends each letter P to (P + k) mod 26, so letters near the end wrap around to the start. To decrypt, shift back by k. KHOOR with key 3 decrypts to HELLO. Because there are only 25 useful shifts, anyone can try them all. Even better ciphers that replace each letter with another can be broken by frequency analysis: E, T and A are the most common letters in English, so the most common ciphertext letters are probably those.

How RSA works

RSA builds its keys from two prime numbers. Here is a toy version with small primes.

• Choose primes p = 7 and q = 11, so n = 77. Also find (p − 1)(q − 1) = 60.
• Choose e = 7, which shares no factor with 60. The public key is (n, e) = (77, 7).
• Find d with e × d ≡ 1 (mod 60). Since 7 × 43 = 301 = 5 × 60 + 1, d = 43. The private key is d = 43.
• To send the message m = 2, compute c = m^e mod n = 2⁷ mod 77 = 128 mod 77 = 51.
• To read it, compute c^d mod n = 51⁴³ mod 77, which gives back 2.

Anyone may know n = 77, but finding d needs the factors 7 and 11. Real RSA uses primes hundreds of digits long, and no known method can factor their product in a reasonable time. That is what protects online banking, e-wallets and the padlock symbol on secure websites.

4. Data science

Data science draws conclusions from data. In supervised learning, a model trains on examples with known answers. Its results are only as good as the data behind it.

A data science project usually follows the same cycle: collect the data, clean it by fixing errors and gaps, explore it with statistics and graphs, build a model, and communicate the findings. A model that learns to spot spam from thousands of emails already labelled spam or not spam is supervised learning. In unsupervised learning there are no labels; the model looks for groups on its own, such as customers with similar buying habits.

If the training data are biased, the model is biased too. A hiring model trained on past decisions can repeat past unfairness. Data about people must also be protected: in the Philippines, the Data Privacy Act of 2012 (Republic Act 10173) requires that personal information be collected for a clear purpose, kept secure, and used only with proper consent.

Solved examples

Follow each one line by line. The steps stay the same when the numbers change, so cover the steps and try it yourself.

Example 1: Decimal to binary

Question: What is 37 in binary?

1. Write the place values. 32, 16, 8, 4, 2, 1.
2. Take out the largest that fits, and repeat. 37 − 32 = 5, then 5 − 4 = 1, then 1 − 1 = 0.
3. Write 1 for each one used and 0 for the rest. 32 yes, 16 no, 8 no, 4 yes, 2 no, 1 yes.
4. Check. 32 + 4 + 1 = 37.

Answer: 37 is 100101 in binary.

Example 2: Modular arithmetic

Question: What is 58 mod 9?

1. Find the largest multiple of 9 that fits. 9 × 6 = 54, since 9 × 7 = 63 is too big.
2. Subtract to get the remainder. 58 − 54 = 4.

Answer: 58 mod 9 = 4.

Example 3: Caesar cipher

Question: Encode MATH with a Caesar cipher using a shift of 5.

1. Count forward 5 letters for each one. M to R, A to F, T to Y, H to M.
2. Write the letters together. RFYM.
3. Check by shifting back 5. R to M, F to A, Y to T, M to H.

Answer: MATH becomes RFYM.

Common mistakes

• Reading binary places from the left. The rightmost place is 1, then 2, 4, 8 going left.
• Writing 2 in binary addition. 1 + 1 is 10: write 0 and carry 1.
• Treating hexadecimal places like decimal ones. Each place is 16 times the one to its right, and A to F stand for 10 to 15.
• Giving the quotient instead of the remainder. 23 mod 7 is the remainder, 2, not 3.
• Forgetting to wrap around in a Caesar cipher. With shift 3, Y becomes B.
• Using binary search on an unsorted list. It only works when the list is in order.

Where you will meet this

• Computing. File sizes, memory and IP addresses are counted in bits and bytes.
• Security. Passwords, e-wallets and online banking rely on encryption.
• Retail and libraries. Barcodes and ISBNs use check digits.
• Work and research. Data analysis and machine learning drive recommendations, forecasts and research findings.

Key terms

Bit

A single binary digit, 0 or 1; 8 bits make a byte.

Algorithm

A finite list of exact steps that solves a problem.

a mod n

The remainder when a is divided by n.

Check digit

An extra digit that lets a code detect typing errors.

Public key

The key anyone may use to encrypt a message for its owner.

Supervised learning

Training a model on examples whose answers are already known.

Summary

• Binary uses powers of 2 and hexadecimal powers of 16; one hex digit is 4 bits.
• n bits represent 2ⁿ values; a byte has 256.
• Binary search needs far fewer steps than linear search, but only on sorted data.
• a mod n is a remainder; clocks, calendars and check digits use it.
• A Caesar cipher is easy to break; RSA is safe because large numbers are hard to factor.
• Data science learns from data, so results depend on good, fairly collected and protected data.