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
Set of flashcards Details
| Flashcards | 60 |
|---|---|
| Language | English |
| Category | Computer Science |
| Level | University |
| Created / Updated | 21.03.2017 / 23.08.2017 |
| Weblink |
https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems
|
| Embed |
<iframe src="https://card2brain.ch/box/20170321_cyg_chapter_6_numbertheoretic_reference_problems/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
What is the time complexity?
[quadratic.algorithm.factorization.number]
O(exp((1 + o(1)) sqrt(ln n ln ln n) ))
What is the time complexity?
[elliptic.algorithm.factorization.number]
O(exp((1 + o(1)) sqrt(2 ln p ln ln p) ))
What is the time complexity?
[number.algorithm.factorization.number]
O(exp((1.92 + o(1))(ln n)1/3 (ln ln n)2/3 ))
What are the characteristics?
[rsachallenge.factorization.number, 3]
1. Numbers of form n=p*q
2. Published by RSA company // rsasecurity.com
3. Naming convention changed from RSA-d to RSA-b with d number of digits and b number of bits of n // Here all in digits
What are the characteristics?
[1994.rsachallenge.factorization.number, 3]
1. RSA-129
2. Atkins, Groff, Lenstra, Leyland
3. Distributed quadratic sieve factoring method on 600 workstations
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]
