Probability

Question 1

Consider the following:

• You have a random variable $X$, which is just a number (or a set of numbers) that is randomly chosen. In this case, $X$ is a string of n bits (where each bit is either 0 or 1), and each bit is chosen completely at random.
• You also have another random variable $Y$, which is also an n-bit string. However, $Y$ doesn’t have to be random in the same way as $X$—it can follow any pattern. But $X$ and $Y$ are independent, meaning knowing $Y$ doesn’t tell us anything about $X$.
• Now, we define a new random variable $Z$ by taking $X$ and $Y$ and combining them using something called the ”bitwise XOR operation” (written as $\oplus$). XOR works like this for each bit: – If the two bits are the same (both 0 or both 1), the result is 0. – If the two bits are different (one is 0 and the other is 1), the result is 1.

So, assuming we define $Z = X \oplus Y$, we apply this rule to each bit in the string separately.

Primes are of great theoretical and practical value in cryptography. A primality test is an algorithm for determining whether an input number is prime or not.

Naive but deterministic

The simplest primality test is trial division: given an input number, $n$, check whether it is divisible by any prime number between 2 and $\sqrt{n}$. If so, then $n$ is composite. Otherwise, it is prime.

The prime number theorem: the distribution of primes is $π(n) \sim n/\log(n)$ where $π(n)$ is the prime-counting function (the number of primes less than or equal to $n$) and $\log(n)$ is the natural logarithm of $n$.