CYG Chapter 6 Number-Theoretic Reference Problems

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

0.0 (0)

R. B.

Lernen

R. B.

Über diese Lernkartei

This flashcard set delves into advanced number-theoretic concepts at the university level, focusing on algorithms for factorization, primality testing, and modular arithmetic. It covers key topics like the Euclidean algorithm, the Chinese Remainder Theorem, and the Miller-Rabin primality test, along with their proofs, characteristics, and applications. The set is particularly useful for computer science students and researchers interested in cryptography and number theory, providing a comprehensive overview of essential theorems and computational methods.

Karten

Lernende

Sprache

Englisch

Kategorie

Informatik

Stufe

Universität

Erstellt / Aktualisiert

21.03.2017 / 23.08.2017

Ähnliche Karteien

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/³ (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 log_Phi(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=l₁x and a-qb=l₂x → a=l₂x+ql₁x → 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, v₁←0 and v₃←b

4. While(v₃!=0) compute q←rounddown(d/v₃), t₃←d (mod v₃), t₁←u-qv₁, u←v₁, d←v₃, v₁←t₁, v₃←t₃

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 m₁,…,m_r are pairwise relatively prime and a₁,…,a_r in N

2. System of congruences x equiv a_i (mod m_i) fa i in [1,r] has a unique solution modulo M=Prod_i=1^rm_i given by x=Sum_i=1^ra_iM_iy_i (mod M) with M_i=M/m_i and y_i=M_i^-1 mod m_i fa i in [1,r]

What is the characteristic?

[motivation.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Basics about number theory // Useful for cryptography

What are the characteristics of ring of equivalence classes Z_n?

[Z_n.number, 5]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. Z_n = Z/nZ

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

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

4. Multiplicative group

5. Euler phi-function

What is the definition?

[multiplicativegroup.Z_n.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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

What holds?

[multiplicativegroup.Z_n.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

If Z_n* 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.Z_n.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Phi(n) = |Z_n*|

What is the characteristic?

[eulerphifunction.Z_n.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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

What is the definition?

[theorem62.Z_n.number, 2]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

1. If a in Z_n* then a^phi(n) equiv 1 (mod n)

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

What are the characteristics?

[notation.Z_n.number, 2]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Test if a given number 2<=n in N is prime

What is the definition?

[composite.primalitytesting.number]

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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 a^n-1 equiv 1 (mod n) for all a in Z_n*

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 a^n-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

What is the characteristic?

[lemma.FTP.primalitytesting.number]

Consider cardinality of the set of all a indicating composite p

What is the definition?

[lemma.FTP.primalitytesting.number]

If n is composite and a in Z_n/Z_n* then a^n-1notequiv 1 (mod n)

What is the proof?

[lemma.FTP.primalitytesting.number, 3]

1. Suppose a^n-1 equiv 1 (mod n)

2. a^-1 =a^n-2 exists

3. a in Z_n* // Contradiction to assumption that a in Z_n/Z_n*

What is the definition?

[proposition63.FTP.primalitytesting.number]

If n composite, odd, no Carmichael number then |{a in Z_n\{0}| a^n-1 notequiv 1 (mod n)}| >= n/2

What is the proof?

[proposition63 .FTP.primalitytesting.number, 6]

1. Consider set K_n-1 := {a in Z_n| a^n-1 equiv 1 (mod n)}

2. K_n-1 subseteq Z_n* as all a in K_n-1 have multiplicative inverses

3. Futhermore K_n-1 is a subgroup of Z_n*

4. It holds that |K_n-1| divides |Z_n*| // Lagrange’s theorem

5. |K_n-1|<=1/2|Z_n*|<=(n-2)/2

6. |Z_n\{0}\K_n-1|>=n-1-(n-2)/2 = n/2

1 / 60

Lernkarten

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/³ (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 log_Phi(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=l₁x and a-qb=l₂x → a=l₂x+ql₁x → 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, v₁←0 and v₃←b

4. While(v₃!=0) compute q←rounddown(d/v₃), t₃←d (mod v₃), t₁←u-qv₁, u←v₁, d←v₃, v₁←t₁, v₃←t₃

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 m₁,…,m_r are pairwise relatively prime and a₁,…,a_r in N

2. System of congruences x equiv a_i (mod m_i) fa i in [1,r] has a unique solution modulo M=Prod_i=1^rm_i given by x=Sum_i=1^ra_iM_iy_i (mod M) with M_i=M/m_i and y_i=M_i^-1 mod m_i fa i in [1,r]

Lernen

CYG Chapter 6 Number-Theoretic Reference Problems

Lernkarteien erstellen oder kopieren

Lernkarten

Bitte melde dich an

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog