Mathematical language

Introduction

In this short note, we will see the basis of mathematical language that will be used throughout our cryptography course (RSA, elliptic curves, etc.). Understanding these conventions is essential for reading and writing rigorous mathematical statements.

1. Set Theory Basics

1.1 Set Notation

A set is a collection of distinct objects. We denote sets with capital letters and use braces to list elements.

Basic Notation:

• \(A = \{1, 2, 3, 4, 5\}\): Set \(A\) contains the elements 1, 2, 3, 4, and 5
• \(x \in A\): "\(x\) is an element of \(A\)" or "\(x\) belongs to \(A\)"
• \(x \notin A\): "\(x\) is not an element of \(A\)"
• \(\emptyset\) or \(\{\}\): The empty set (contains no elements)
• \(|A|\) or \(\#A\): The cardinality (number of elements) of set \(A\)

Set Operations:

• \(A \cup B\): Union (elements in \(A\) or \(B\) or both)
• \(A \cap B\): Intersection (elements in both \(A\) and \(B\))
• \(A \setminus B\) or \(A - B\): Difference (elements in \(A\) but not in \(B\))
• \(A \subseteq B\): \(A\) is a subset of \(B\) (every element of \(A\) is in \(B\))
• \(A \subset B\): \(A\) is a proper subset of \(B\) (\(A \subseteq B\) and \(A \neq B\))

Example:

Let \(A = \{1, 2, 3, 4\}\) and \(B = \{3, 4, 5, 6\}\)

• \(A \cup B = \{1, 2, 3, 4, 5, 6\}\)
• \(A \cap B = \{3, 4\}\)
• \(A \setminus B = \{1, 2\}\)

1.2 Standard Number Sets

In mathematics and cryptography, we frequently work with standard number sets:

• \(\mathbb{N}\): Natural numbers \(= \{0, 1, 2, 3, 4, \ldots\}\)
• \(\mathbb{Z}\): Integers \(= \{\ldots, -2, -1, 0, 1, 2, \ldots\}\)
• \(\mathbb{Q}\): Rational numbers (fractions \(\frac{p}{q}\) where \(p, q \in \mathbb{Z}\) and \(q \neq 0\))
• \(\mathbb{R}\): Real numbers (all numbers on the number line)
• \(\mathbb{C}\): Complex numbers (\(a + bi\) where \(a, b \in \mathbb{R}\) and \(i^2 = -1\))

Special Notations:

• \(\mathbb{Z}^*\) or \(\mathbb{Z} \setminus \{0\}\): Non-zero integers
• \(\mathbb{N}^*\): Positive natural numbers \(= \{1, 2, 3, \ldots\}\)
• \(\mathbb{Z}/n\mathbb{Z}\) or \(\mathbb{Z}_n\): Integers modulo \(n\) \(= \{0, 1, 2, \ldots, n-1\}\)

1.3 Set-Builder Notation

Set-builder notation allows us to define sets by specifying properties that their elements must satisfy.

General Form: \(\{x \in S \mid P(x)\}\) or \(\{x \in S : P(x)\}\)

This reads as "the set of all \(x\) in \(S\) such that property \(P(x)\) holds."

Examples:

• \(\{x \in \mathbb{Z} \mid x^2 < 10\} = \{-3, -2, -1, 0, 1, 2, 3\}\)
• \(\{n \in \mathbb{N} \mid n \text{ is even}\} = \{0, 2, 4, 6, 8, \ldots\}\)
• \(\{p \in \mathbb{N} \mid p \text{ is prime and } p < 20\} = \{2, 3, 5, 7, 11, 13, 17, 19\}\)

In cryptography, this notation is particularly useful: - \((\mathbb{Z}/n\mathbb{Z})^* = \{a \in \mathbb{Z}/n\mathbb{Z} \mid \gcd(a, n) = 1\}\)

2. Logical Propositions and Connectives

2.1 Logical Symbols

Logical connectives allow us to build complex statements from simpler ones:

• \(\neg P\) or \(\lnot P\): NOT \(P\) (negation)
• \(P \land Q\): \(P\) AND \(Q\) (conjunction)
• \(P \lor Q\): \(P\) OR \(Q\) (disjunction)
• \(P \Rightarrow Q\) or \(P \implies Q\): If \(P\) then \(Q\) (implication)
• \(P \Leftrightarrow Q\) or \(P \iff Q\): \(P\) if and only if \(Q\) (equivalence)

Example: Let \(P\): "\(n\) is even" and \(Q\): "\(n^2\) is even"

• \(P \Rightarrow Q\): "If \(n\) is even, then \(n^2\) is even" (True)
• \(Q \Rightarrow P\): "If \(n^2\) is even, then \(n\) is even" (True)
• \(P \Leftrightarrow Q\): "\(n\) is even if and only if \(n^2\) is even" (True)

2.2 Truth Tables

Truth tables show all possible combinations of truth values for logical statements.

Basic Connectives:

Important Note: The implication \(P \Rightarrow Q\) is only false when \(P\) is true and \(Q\) is false.

2.3 Logical Equivalences

Two statements are logically equivalent if they have the same truth value in all cases. We write \(P \equiv Q\).

Key Equivalences:

• Double Negation: \(\neg(\neg P) \equiv P\)
• De Morgan's Laws:
• \(\neg(P \land Q) \equiv (\neg P) \lor (\neg Q)\)
• \(\neg(P \lor Q) \equiv (\neg P) \land (\neg Q)\)
• Contrapositive: \((P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)\)
• Implication as Disjunction: \((P \Rightarrow Q) \equiv (\neg P \lor Q)\)

Example in Cryptography: The statement "If \(\gcd(a, n) = 1\), then \(a\) has a multiplicative inverse modulo \(n\)" is equivalent to its contrapositive: "If \(a\) does not have a multiplicative inverse modulo \(n\), then \(\gcd(a, n) \neq 1\)."

3. Quantifiers

Quantifiers allow us to express statements about collections of objects. The two fundamental quantifiers are:

3.1 Universal Quantifier: \(\forall\) (For all)

The symbol \(\forall\) means "for all" or "for every". It expresses that a property holds for every element in a given set.

For example, \(\forall x \in E,\ P(x)\), means "For all \(x\) in the set \(E\), the property \(P(x)\) is true"

Examples:

• \(\forall n \in \mathbb{N}, n^2 \geq 0\): For all \(n\) in \(\mathbb{N}\), \(n^2\) is greater than or equal to 0
• \(\forall a \in \{0, 1, 2, 3, 4, 5\}, a^2 \leq 25\): For all \(a\) in \(\{0, 1, 2, 3, 4, 5\}\), \(a^2\) is less than or equal to 25

3.2 Existential Quantifier: \(\exists\) (There exists)

The symbol \(\exists\) means "there exists" or "there is at least one". It expresses that at least one element satisfying a property can be found.

For example, \(\exists x \in E,\ P(x)\), means "There exists an \(x\) in the set \(E\) such that the property \(P(x)\) is true"

Examples:

• \(\exists x \in \mathbb{N}, x^2 = 25\): There is at least one element of \(\mathbb{N}\) such that its square is equal to 25 (\(x = 5\))
• \(\exists e \in \mathbb{N}, e > 2\): There is at least one element of \(\mathbb{N}\) greater than 2

3.3 Unique Existence: \(\exists!\) (There exists exactly one)

Sometimes we want to express that exactly one element satisfies a property. We use \(\exists!\) to express the uniqueness of the element.

For example, \(\exists! x \in E,\ P(x)\), means "There exists a unique element \(x\) in the set \(E\) such that the property \(P(x)\) is true"

Example:

We can revisit the example: \(\exists x \in \mathbb{N}, x^2 = 25\).

There is at least one element in \(\mathbb{N}\) whose square equals 25. But we can verify the uniqueness of the proposition:

The only correct solution in \(\mathbb{N}\) is 5 because \(-5 \notin \mathbb{N}\).

So we can say that: \(\exists! x \in \mathbb{N}, x^2 = 25\)

There is a unique \(x\) in \(\mathbb{N}\) whose square is equal to 25.

3.4 Combining Quantifiers

The order of quantifiers matters significantly. Consider these two statements:

1. \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y > x\)
2. "For every real number \(x\), there exists a real number \(y\) such that \(y > x\)"

3. This is true (we can always find a larger number)

4. \(\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, y > x\)

5. "There exists a real number \(y\) such that for all real numbers \(x\), \(y > x\)"
6. This is false (no single number is greater than all real numbers)

Cryptographic Example:

This expresses the homomorphic property of certain encryption schemes.

3.5 Negating Quantifiers

Understanding how to negate quantified statements is essential in mathematical proofs.

Negation Rules:

• \(\neg(\forall x \in E, P(x)) \equiv \exists x \in E, \neg P(x)\)

  • "Not all elements satisfy \(P\)" means "At least one element does not satisfy \(P\)"

• \(\neg(\exists x \in E, P(x)) \equiv \forall x \in E, \neg P(x)\)

  • "There does not exist an element satisfying \(P\)" means "All elements do not satisfy \(P\)"

Examples:

• \(\neg(\forall n \in \mathbb{N}, n^2 \geq n) \equiv \exists n \in \mathbb{N}, n^2 < n\)
• \(\neg(\exists x \in \mathbb{R}, x^2 = -1) \equiv \forall x \in \mathbb{R}, x^2 \neq -1\)

Complex Example:

The negation of \(\forall x \in E, \exists y \in F, P(x, y)\) is \(\exists x \in E, \forall y \in F, \neg P(x, y)\)

Notice how the quantifiers flip (\(\forall\) becomes \(\exists\) and vice versa) and move inward.

4. Additional Mathematical Notations

4.1 Divisibility and Modular Arithmetic

These concepts are fundamental in cryptography, particularly in RSA and other number-theoretic algorithms.

Divisibility:

• \(a \mid b\): "\(a\) divides \(b\)" (there exists an integer \(k\) such that \(b = ka\))
  • Example: \(3 \mid 12\) because \(12 = 3 \times 4\)
• \(a \nmid b\): "\(a\) does not divide \(b\)"
  • Example: \(3 \nmid 10\)

Modular Arithmetic:

• \(a \equiv b \pmod{n}\): "\(a\) is congruent to \(b\) modulo \(n\)"
  • This means \(n \mid (a - b)\), or equivalently, \(a\) and \(b\) have the same remainder when divided by \(n\)
  • Example: \(17 \equiv 5 \pmod{12}\) because \(17 - 5 = 12\)

Greatest Common Divisor and Least Common Multiple:

• \(\gcd(a, b)\): The greatest common divisor of \(a\) and \(b\)

  • The largest positive integer that divides both \(a\) and \(b\)
  • Example: \(\gcd(12, 18) = 6\)
  • In RSA: \(\gcd(e, \phi(n)) = 1\) ensures \(e\) has a multiplicative inverse

• \(\text{lcm}(a, b)\): The least common multiple of \(a\) and \(b\)

  • The smallest positive integer that is divisible by both \(a\) and \(b\)
  • Example: \(\text{lcm}(12, 18) = 36\)
  • Relationship: \(\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b\)

Key Properties:

• \(a \equiv b \pmod{n} \implies (a + c) \equiv (b + c) \pmod{n}\)
• \(a \equiv b \pmod{n} \implies (a \cdot c) \equiv (b \cdot c) \pmod{n}\)
• \(a \equiv b \pmod{n} \implies a^k \equiv b^k \pmod{n}\) for any \(k \in \mathbb{N}\)

4.2 Functions

Functions are mappings between sets and are essential in defining encryption and decryption operations.

Basic Notation:

• \(f: A \to B\): Function \(f\) from set \(A\) to set \(B\)

  • \(A\) is the domain (input set)
  • \(B\) is the codomain (potential output set)

• \(f(x)\): The image of \(x\) under function \(f\) (the output when input is \(x\))

• \(\text{Im}(f)\) or \(f(A)\): The image (or range) of \(f\)

  • The set of all actual outputs: \(\text{Im}(f) = \{f(x) \mid x \in A\}\)
  • Note: \(\text{Im}(f) \subseteq B\)

• \(f^{-1}\): The inverse function (when it exists)

  • \(f^{-1}: B \to A\) such that \(f^{-1}(f(x)) = x\) for all \(x \in A\)
  • Only exists when \(f\) is bijective (both injective and surjective)

Function Properties:

• Injective (one-to-one): \(\forall x_1, x_2 \in A, f(x_1) = f(x_2) \implies x_1 = x_2\)

  • Different inputs produce different outputs

• Surjective (onto): \(\forall y \in B, \exists x \in A, f(x) = y\)

  • Every element of \(B\) is an output for some input
  • Equivalently: \(\text{Im}(f) = B\)

• Bijective: Both injective and surjective

  • Establishes a one-to-one correspondence between \(A\) and \(B\)
  • Only bijective functions have inverses

Cryptographic Examples:

• Encryption function: \(E: \mathcal{M} \to \mathcal{C}\) (from message space to ciphertext space)
• Decryption function: \(D: \mathcal{C} \to \mathcal{M}\) where \(D = E^{-1}\)
• In RSA:
  • \(E(m) = m^e \bmod n\)
  • \(D(c) = c^d \bmod n\)

5. Summary

This note has introduced the fundamental mathematical language necessary for studying cryptography:

1. Set Theory: We learned how to describe and manipulate collections of objects using standard notation, operations (union, intersection, difference), and set-builder notation. Understanding sets like \(\mathbb{Z}_n\) and \((\mathbb{Z}/n\mathbb{Z})^*\) is crucial for modular arithmetic in cryptographic algorithms.

2. Logical Connectives: We explored how to build complex logical statements using AND (\(\land\)), OR (\(\lor\)), NOT (\(\neg\)), implication (\(\Rightarrow\)), and equivalence (\(\Leftrightarrow\)). Truth tables and logical equivalences help us reason about the correctness of cryptographic protocols.

3. Quantifiers: The universal quantifier (\(\forall\)) and existential quantifier (\(\exists\)) allow us to make precise statements about properties that hold for all or some elements. Understanding quantifier negation and ordering is essential for proving security properties.

Mastering this mathematical language will enable you to:

• Read and understand cryptographic papers and textbooks
• Write rigorous proofs of security properties
• Communicate mathematical ideas clearly and precisely
• Understand the theoretical foundations of algorithms like RSA and elliptic curve cryptography

As you progress through the cryptography course, refer back to these notations whenever you encounter unfamiliar symbols or need to verify your understanding.