Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Challenges (Java)

We will be working on these challenges in the lab session for this topic.

You do not have to complete these in advance. However you may choose to get started on them in advance if you wish. You still need to attend the lab even if you have completed the challenges! If you do not complete them in the lab it is recommended that you finish them in your own time.

Decoding the Affine Cypher

Update: There is a model answer available for this practical here.

The goal is to write a function decodeAffine(String c, int a, int b) that takes a string encrypted using an affine cypher (i.e. the cypher text), and values for a and b and returns the decrypted string (the plain text). For example, it might take the string jollg kgblh, and values a = 7, b = 12 and return the string hello world. Leave any character not in a-zA-Z (i.e. non-alphabetic characters) unmodified. You may use the .toLowerCase() method on your string and work with only lower case strings.

The decryption function for an affine cypher is D(X) = a^-1(X - b) mod 26. Here, because we are working under modulus, a^-1 is the modular (multplicative) inverse of a.

Part 1

In order to calculate a^-1, you will have to write a modular inverse function. One way to do this is using a brute force method. That means you try every possible value until you find the right one. You know that a * a^-1 mod n = 1. You also know that the modular inverse, a^-1, must be an integer value between 0 and n-1.

Write a function int modInverse(int a, int m) that takes two integers and returns the inverse of a under modulus n. If there is no modular inverse for a under modulo n, the function should return -1.

Part 2

Write a int decodeValue(int v, int a, int b) function that takes a numerical value v for a letter (e.g. 3) and returns the decoded value, using affine keys a and b.

Part 3

You’ll need to write a function int charToPosition(char c) to convert characters from your string to numerical values and another char positionToChar(int p)to convert them back again. If you’re only working with lower case, this would convert a to 0, b to 1, and so on.

Part 4

Write a char decodeChar(char v, int a, int b) function to:

Check if the character is alphabetic (if not, return it)
Convert a character into a numerical value
Find the decoded value
Convert back to a character and return it

Part 5

Put it all together in your String decodeAffine(String c, int a, int b) function. This function should take a string and a value for the two affine cypher keys a and b, and return a decrypted string.

In this function you will need to loop through the string, and for each character run your decodeChar() function.

Part 6 (Optional)

If you get this far and you really want a challenge, try writing a program to crack an affine cypher using a known-plaintext attack. Assume you know the correct values for the first two characters of the encrypted string. Your function should take a cyphertext string and the first two plaintext characters and return the decrypted string.

Repl.it Project

The following Replit project has functions for you to fill in and tests to check your answers. Make sure you write your code in the provided functions in the Main.java file. You can change file by using the file icon on the left side of the frame. You might find this online tool helpful for checking your work.

Improve this page

Getting Started

Introducing Mathematics