COMS W4995 Introduction to Cryptography September 2, 2003

Lecture 0: L^{A}TEX introduction

Lecturer: Tal Malkin Scribes: Ariel Elbaz

Summary

This is an example latex file. You should use this file (ITC0.tex) as a template for scribing the lecture notes. Start by modifying the lecture number and details. If you’re scribing lecture n, submit your edited file as (ITCn.tex).

1 Theorems, Proofs, etc.

Definition 1

Theorem 1 text of a theorem …

Proof: starting a proof … and ending it

Claim 2 text of a claim

Proof sketch: text of a proof sketch

We can also emphasize parts of the text

1.1 A subsection on primes

Definition 2 p is a prime if p is an integer that has no integral factors but itself and 1.

More examples

Lemma 3 text of a lemma

Example 1 text of an example

2 Mathematical Equations

Math equations can either be mixed with text,, such as y = x + 2 or 2^{2^{13}} or \frac{17!}{2^{34}} , or else they can be in a sepeate line

P r[x ≥ y] ≤ \frac{1}{3}

or on an automatically numbered equation

{x : x ≤ y ⇒ y ≥ 0}  (1)

We can refer to a specific equation by labelling them. Equation 1 defines the set of values x, such that if x is smaller than y, it must be the case that y is at most 0. Note: you will have to compile the LaTeX file twice for equation references to appear correctly.

More advanced equations

V_{s,0}^{{q_{0},q_{1}}} = V_{s,0}^{{q_{0}}} ∪ V_{s,1}^{{q_{0}}} ∘ (V_{1,1}^{{q_{0}}})^{∗} ∘ V_{1,0}^{{q_{0}}}
V_{s,2}^{{q_{0},q_{1}}} = V_{s,2}^{{q_{0}}} ∪ V_{s,1}^{{q_{0}}} ∘ (V_{1,1}^{{q_{0}}})^{∗} ∘ V_{1,2}^{{q_{0}}} = V_{s,1}^{{q_{0}}} ∘ (V_{1,1}^{{q_{0}}})^{∗} ∘ V_{1,2}^{{q_{0}}}

3 Itemizing

• First item

• Second item

⇒ You can define the bullet shape that appears to the left.

1. Items can also be numbered

2. And they can be nested (a) Just another item.

4 Writing text

The L^{A}TEXcompiler does it’s own pagesetting. It converts any number of spaces to a single space, and concatantes sentences to fill the paragraph. You can spread one sentence over as many lines as you want, it will continue as if it was written in a single line. If you want to break a paragraph you need to leave an empty line.

When you want to verify some text not being spread across two lines, e.g. ”1 2 3 … 4 5 6 … 7 8 9”, you can enclose it in mbox. LaTeX treats it as a single letter and will never cut it in the middle.

Same text, without mbox: When you want to verify some text not being spread across two lines, e.g. ”1 2 3 … 4 5 6 … 7 8 9”, you can enclose it in mbox. LaTeX treats it as a single letter and will never cut it in the middle.

5 Some Symbols

Encryption scheme : (GEN, ENC, DEC).

pair : ⟨a,b⟩

Big O, small o : k = O(n), ϵ = o(1)

complexity classes : L, RL, NL, P, NP, coNP, RP, BPP, ZPP, coNL, coRP, EXP, PSPACE, AC^{0}, IP, AM, coAM

Number sets : ℕ, ℝ, ℤ, ℂ, ℚ, ℤ, ℤ_{p}, ℤ_{n}, ℤ_{p}^{∗}

Logical operators : ∧, ∨, ¬, ⟺ , ⟹

Theorem 4 (Fermat’s little theorem) If p is a prime, then for any a ∈ ℤ_{p}^{∗}, a^{p−1} ≡ 1 (mod p)

Definition 3 A function f: {0, 1}^{n} → {0, 1}^{n+1} is a pseudo random generator …

Tal’s Note: If the lecturer feels there are things to be added on some topic, they might appear as a note inside the scribes. This does not necessarily mean that the scribes are not good; Sometimes these notes may refer to topics that are beyond the scope of the course.