Riassunto esame Cryptography, Prof. Pavese Francesco, libro consigliato Appunti di matematica discreta, Stefano Capparelli

Cryptography

Arithmetic & number theory

Natural number

One of the main properties of ℕ is the induction principle:

A property, p(n) is true for all n ≥ 1 if:

• P(1) is true.
• If p(1), …, p(k) are true then p(k+1) holds as well.

Examples

∑_k=1ⁿ k = n(n + 1) / 2

HP: ∑_k=1ⁿ k² = n(n + 1)(2n + 1) / 6

TH: 1² + 2² + ⋯ + n² = (n(n + 1)(2n + 1)) / 6

HP: ∑_k=1ⁿ k³ = (n(n + 1) / 2)²

TH: 1³ + 2³ + ⋯ + n³ = (n(n + 1) / 2)²

Def

Set a, b ∈ ℤ, where b ≠ 0. We say that b divides a, and we denote it with b|a, if a/b ∈ ℤ. In other words, b/a is equivalent to say ∃ c ∈ ℤ such that a = b⋅c.

Set a, b ∈ ℤ, where b ≠ 0, if b|a and b ≠ a, b is a proper divisor of a.

Examples

n ∈ ℕ, ∃ x,y ∈ ℕ s.t. 1 ≤ y ≤ n.

HP: ∑_k=1ⁿ 1⋅b

Theorem

Set a, b ∈ ℤ where b ≠ 0, there are uniquely determined q, r ∈ ℤ s.t. a = bq + r, where 0 ≤ r < |b|. We know q as quotient and r as remainder.

Set a, b ∈ ℤ. d > 0 is called greatest common divisor of a and b if:

• D is a common divisor of a and b (d|a and d|b).
• ∀ e ∈ ℤ, e is a common divisor of a and b, then d|e.

∀ a, b ∈ ℤ and b ≠ 0, then d = gcd(a,b) exists and is unique and can be determined with the Euclid's algorithm.

Exercises

gcd (12,9) = 3

gcd (106,100) = … = gcd (6,4) = 2

gcd (732,128) = 4

gcd (399,331) = 19

321 = 321⋅4 + 68

4 = 238; 684 = 366; 366 = …

Arithmetic & number theory

Natural number

One of the main properties of N is the induction principle: A property, p(n) is true for all n ∈ I if:

• P(1) is true.
• If p(1), ..., p(k) are true then p(k+1) holds as well.

Examples

• ∑ⁿ_k=1 2 = 1 + 4 + 9 + 3 = (m_n+1+2)(m_n+1)/6
• ∑ⁿ_k=1 k⁴
• HP: ∑⁴_i=1 i³ = (m_n+1²)(m_n+1⁴)(m_n+1)/4
• TH: ∑⁴_k=1 n_k^1/n = (m_n+1⁴ + ∑⁴_i=1 m_n+1ⁱ) = (m_n+1⁴)(m_n+1)(2^n-1)/(2^n-1)
• M₀!/m_n = (m_n+1)((m_n+1)(2^n-1)/(2ⁿ⁺¹))(2ⁿ⁺¹ - 1)/4

Def

Set a,b ∈ Z, where b ≠ 0. We say that b divides a, and we denote it with b|a, if a/b ∈ Z. In other words, b|a is equivalent to say ∃c ∈ Z such that a = b·c.

Set a,b ∈ Z, where b ≠ 0. If b|a and b≠a, b is a proper divisor of a.

Examples

• ∀ n ∈ N, ∃ k ∈ Z

HP: x = 3y, 1b = 3

Theorem

Set a,b ∈ Z, where b ≠ 0. There exist a uniquely determined q,r ∈ N s.t. a = bq + r, where 0 ≤ r <

Def

A common divisor d>0 is called greatest common divisor of a and b if:

• D is a common divisor of a and b (d|a and d|b).
• ∀ d' ∈ Z is a common divisor of a and b. Then d'|d.

b|a+ro_d=0

Theorem

∀a,b ∈ Z, and b ≠ 0, then d = gcd(a,b) exists and is unique and can be determined with the Euclid's algorithm.

Exercises: Determine the gcd with the Euclid alg.

gcd (42,72) = 6

gcd (12,30) = 6

gcd (36342, 78956)

gcd (5432, 352)

gcd (...)

Bézout identity

Let a,b∈ℤ where a,b≠0 ˘ m,m∈ℤ s.t. gcd(a,b)=ma+mb

Examples

m=527 and n=341 ˘ 341=1·186 + 155 ˘ 186=(341-186)=341-1·186 ˘ 186=3-341 + 2·527

m=a(523-341)

gcd(527, 341)

527= 3·341-188

527=2·341+(527-341)

341(3+2)

Fundamental theorem of arithmetic

Every natural number has a unique prime number decomposition. In other words, ∀n∈N, n can be written as n = p₁^x ∙ p₂^y ∙ ... such that p_i are prime numbers and

Examples

2=2

3=3

12=2²∙3

655=5∙2∙2∙13

111=11

Prime numbers

Defs

If gcd(a,b)=1 then a,b are called coprime.

b is said to be prime if 0⩽p⩽p⩾1

Properties

• Let a,b,c,z,t∈ℤ, t|c⟹c|b then t|(ax+by).
• Set a,b,c,z,t∈ℤ, t|cab and gcd(a,c)=1, then c|b.
• From Bézout identity we know that ∃n,m∈ℤ̸= 1 form:am and x·c·b(m+a+c)=mab+mbct + (n-1·t)=ab ∨ t =ab.
• Let p be a prime and a,b,z∈ℤ st. if a|b then either q|a or q|b.

Note

Assume, by contrast, that p₁,...,p₁ are all the primes numbers. Let n:=1+(p₁·...·p_k). By the F.T.A, there is a prime P dividing n. But p≠p₁,...,p_k that means π(p₁ ...p_k)=