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
Fichier Détails
| Cartes-fiches | 60 |
|---|---|
| Langue | English |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 21.03.2017 / 23.08.2017 |
| Lien de web |
https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems
|
| Intégrer |
<iframe src="https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Créer ou copier des fichiers d'apprentissage
Avec un upgrade tu peux créer ou copier des fichiers d'apprentissage sans limite et utiliser de nombreuses fonctions supplémentaires.
Connecte-toi pour voir toutes les cartes.
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
-
