# CYG Chapter 6 Number-Theoretic Reference Problems

Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 6 Number-Theoretic Reference Problems

60
0.0 (0)

Kartei Details

Karten 60 English Informatik Universität 21.03.2017 / 23.08.2017 Keine Angabe https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems

What is the characteristic?

[motivation.number]

Basics about number theory // Useful for cryptography

What are the characteristics of ring of equivalence classes Zn?

[Zn.number, 5]

1. Zn = Z/nZ

2. Equivalence relation s~t or s equiv t (mod n) ↔ n|(s-t)

3. (Zn,+,*) forms a commutative ring

4. Multiplicative group

5. Euler phi-function

What is the definition?

[multiplicativegroup.Zn.number]

Zn* := {a in Zn| gcd(a,n)=1}

What holds?

[multiplicativegroup.Zn.number]

If Zn* is multiplicative abelian group then gcd(a,n)=1 iff ex inverse s of a with a*s equiv 1 (mod n)

What is the definition?

[eulerphifunction.Zn.number]

Phi(n) = |Zn*|

What is the characteristic?

[eulerphifunction.Zn.number]

Phi(p)=p-1 for any prime p

What is the definition?

[theorem62.Zn.number, 2]

1. If a in Zn* then aphi(n) equiv 1 (mod n)

2. If p is prime and (a,p)=1 then ap-1 equiv 1 (mod p) // Fermat’s little theorem

What are the characteristics?

[notation.Zn.number, 2]

1. (a,n) for gcd(a,n)

2. If (a,n)=1 then a and n are called relatively prime or coprime