CYG Chapter 6 Number-Theoretic Reference Problems
Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 6 Number-Theoretic Reference Problems
Questions about the lecture 'Cryptography' of the RWTH Aachen Chapter 6 Number-Theoretic Reference Problems
Kartei Details
| Karten | 60 |
|---|---|
| Sprache | English |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 21.03.2017 / 23.08.2017 |
| Weblink |
https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Lernkarteien erstellen oder kopieren
Mit einem Upgrade kannst du unlimitiert Lernkarteien erstellen oder kopieren und viele Zusatzfunktionen mehr nutzen.
Melde dich an, um alle Karten zu sehen.
What are the characteristics?
[1996.rsachallenge.factorization.number, 2]
1. RSA-130
2. Dodson, Montgomery, Elkenbracht-Huizing, Lenstra et al.
What are the characteristics?
[1999.rsachallenge.factorization.number, 3]
1. RSA-155
2. 8500 MIPS-years
3. On 300 PCs and workstations
What are the characteristics?
[2003.rsachallenge.factorization.number, 3]
1. RSA-174
2. Franke et al
3. Distributed version of the number field sieve
What are the characteristics?
[2005.rsachallenge.factorization.number, 3]
1. RSA-193
2. Bahr, Boehm, Franke and Kleinjung
3. 30 2.2GHz-Opteron-CPU years
What are the characteristics?
[2009.rsachallenge.factorization.number, 3]
1. RSA-232
2. Kleinjung et al.
3. 2000 2.2 GHz-Opteron-CPU years
What is the idea?
[euclidean.number]
Obtain efficiently gcd d of two numbers a and b
What is the idea?
[extended.euclidean.number, 2]
1. With intermediate results of form au+bv=d
2. If gcd(a,b)=1 then au+bv=1 → au equiv 1 (mod b) // Can also be used to invert a modulo b
What are the characteristics?
[euclidean.number, 2]
1. Number of divisions is not greater than logPhi(sqrt(5)a)-2 with Phi=½(1+sqrt(5)) the golden ration and a>b
2. Least favorable case occurs if a and b are successive Fibonacci numbers
What is the definition?
[lemma.euclidean.number]
If a,b in Z then gcd(a,b) = gcd(b,a-qb) fa q in Z
What is the proof?
[lemma.euclidean.number, 2]
( i) x|a and x|b → x|b and x|a-qb
(ii) x|b and x|a-qb → b=l1x and a-qb=l2x → a=l2x+ql1x → x|a
What are the steps?
[euclidean.number, 2+2]
1. Input are integers a and b
2. Output is gcd(a,b)=d
3. While(b!=0) compute r←a (mod b), a←b and b←r
4. Return a
What are the steps?
[extended.euclidean.number, 2+4]
1. Input are integers a and b
2. Output is tuple (u,d,v) with au+bv=gcd(a,b)=d
3. Init u←1, v←0, d←a, v1←0 and v3←b
4. While(v3!=0) compute q←rounddown(d/v3), t3←d (mod v3), t1←u-qv1, u←v1, d←v3, v1←t1, v3←t3
5. v←(d-au)/b
6. Return (u,d,v)
What is an alternative description?
[theorem610.number]
Chinese remainder theorem
What is the idea?
[theorem610.number]
Provides method for solving systems of congruences
What is the definition?
[theorem610.number, 2]
1. Suppose m1,…,mr are pairwise relatively prime and a1,…,ar in N
2. System of congruences x equiv ai (mod mi) fa i in [1,r] has a unique solution modulo M=Prodi=1rmi given by x=Sumi=1raiMiyi (mod M) with Mi=M/mi and yi=Mi-1 mod mi fa i in [1,r]
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
What is the idea?
[primalitytesting.number]
Test if a given number 2<=n in N is prime
What is the definition?
[composite.primalitytesting.number]
If p not prime then we call n composite
List them!
[primalitytesting.number, 4]
1. FTP
2. Miller-Rabin
3. Deterministic
4. Finding large prime numbers
What is the characteristic?
[FTP.primalitytesting.number]
Use Fermat’s little theorem for a probabilistic primality test
What are the characteristics?
[carmichaelnumbers.FTP.primalitytesting.number, 3]
1. n is composite but an-1 equiv 1 (mod n) for all a in Zn*
2. 561,1105, 1729, 2465, 2821, 6601, 29341, 172081, 278545…
3. Infinitely many proved by Alford et al.
What holds?
[FTP.primalitytesting.number, 3]
1. P(FPT states “n composite” | n composite) >= 1/2
2. P(FPT states “n prime” | n composite) <= 1/2
3. P(FPT states “n prime” | n prime) = 1
What are the steps?
[FTP.primalitytesting.number, 3]
1. Select a in {2,…,n-1} random
2. If an-1 equiv 1 (mod n) then n prime otherwise n composite
3. If sufficiently many a indicate a composite p then high success probability can be achieved by independent repetition of the test
-
- 1 / 60
-
