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.

Étudier

R. B.

À propos de ce fichier

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.

Cartes-fiches

Utilisateurs

Langue

Anglais

Catégorie

Informatique

Niveau

Université

Créé / Mis à jour

21.03.2017 / 23.08.2017

Fichiers de cartes similaires

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Basics about number theory // Useful for cryptography

What are the characteristics of ring of equivalence classes Z_n?

[Z_n.number, 5]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

What holds?

[multiplicativegroup.Z_n.number]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Phi(n) = |Z_n*|

What is the characteristic?

[eulerphifunction.Z_n.number]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

What is the definition?

[theorem62.Z_n.number, 2]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

What is the definition?

[composite.primalitytesting.number]

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Cartes-fiches

What is the characteristic?

[motivation.number]

Basics about number theory // Useful for cryptography

What are the characteristics of ring of equivalence classes Z_n?

[Z_n.number, 5]

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]

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

What holds?

[multiplicativegroup.Z_n.number]

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]

Phi(n) = |Z_n*|

What is the characteristic?

[eulerphifunction.Z_n.number]

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

What is the definition?

[theorem62.Z_n.number, 2]

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]

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 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

What holds for K_n-1 as subgroup of Z_n*?

[proof.proposition63 .FTP.primalitytesting.number, 5]

1. Closed under multiplication

2. Multiplication is associative

3. 1 in K_n-1

4. Inverse of a is a^n-2 in K_n-1 as (a^n-2)^n-1= (a^n-1)^n-2 equiv 1 (mod n)

5. a in Z_n* with a notin K_n-1// a is not a Carmichael number

List them?

[tools.strongwitness.MRPT.primalitytesting.number, 2]

1. n = 1+q*2^k with q odd // Any odd n has unique representation

2. a in [2,n-1] or in W(n)

What holds?

[strongwitness.MRPT.primalitytesting.number, 2]

( i) a^q notequiv 1 (mod n)

(ii) a^{q*2^i} notequiv -1 (mod n) for all I in [0,k-1]

What is the definition?

[proposition65.strongwitness.MRPT.primalitytesting.number]

If a in W(n) then n is composite

What is the proof?

[proposition65.strongwitness.MRPT.primalitytesting.number, 9]

1. Suppose a in W(n) and n prime

2. a^n-1 = a^{q*2^k} equiv 1 (mod n) // By theorem 6.2

3. Consider successive squares

4. a^q notequiv 1 (mod n),…, a^{q*2^k} equiv 1 (mod n)

5. Let j be the maximal number for which b=a^{q*2^j}notequiv 1 (mod n) holds

6. b notequiv 1 (mod n) but b² equiv 1 (mod n)

7. Because n prime we know that Z_n is a field and hence b=1 or b=-1

8. Because b notequiv 1 (mod n) we know b=-1

9. b=-1 is a contradiction to the definition of the strong witness

What is the definition?

[theorem66.strongwitness.MRPT.primalitytesting.number]

|{a| a in [2,n-1] and a notin W(n)}| <= n/4

What holds?

[MRPT.primalitytesting.number, 3]

1. P(MRPT states “n composite” | n composite) >= 3/4

2. P(MRPT states “n prime” | n composite) <= (1/4)^M // For M many independently different a

3. P(MRPT states “n prime” | n prime) = 1

What are the steps?

[MRPT.primalitytesting.number, 3+3]

1. Compute n = 1+q^{2^k} with q odd

2. Choose a in [2,n-1] uniformly distributed at random

3. Compute y = a^q mod n

4. If (y=1 or n-1) then return “n prime”

5. If for any I in [1,k] y² mod n is n-1 then return “n prime”

6. Otherwise return “n composite”

What are the characteristics?

[deterministic.primalitytesting.number, 3]

1. Since August 6, 2002

2. Polynomial time deterministic algorithm

3. Much slower than MRPT // That is why MRPT is still used in most applications

What is the characteristic?

[large.primalitytesting.number]

Presented algorithms can be used to find large prime numbers

What are the steps?

[large.primalitytesting.number, 2]

1. Choose large, odd n in N

2. Iterate over n←n+2 until a prim number is found

What is an alternative description?

[theorem67.large.primalitytesting.number]

Prime Number Theorem

What is the definition?

[theorem67.large.primalitytesting.number]

|{p|p<=n, p prime}| ~ n/ln(n) // Reasonable period of time

What would be an example?

[large.primalitytesting.number]

For n=2⁵¹² we get 2/ln(2⁵¹²)~1/177.4

What are the characteristics?

[problem.factorization.number, 2+2]

1. Detecting whether n is prime or composite is computationally “easy”

2. Much harder is prime factorization for given integer

3. “Trial-division” // Naive algorithm and much too inefficient

4. Advanced algorithms as the quadratic sieve and the number field sieve are based on proposition 6.8

What is the definition?

[proposition68.factorization.number]

If x notequiv +-y (mod n) and x² equiv y² (mod n) then gcd(x-y, n) is a nontrivial factor of n

What is the proof?

[proposition68.factorization.number, 4]

1. x² equiv y² (mod n) with n|x²-y²

2. n|(x-y)(x+y)

3. But by assumption n!|(x+-y)

4. Hence factor s of n must be “shared” between (x-y) and (x+y)

What are the characteristics?

[algorithm.factorization.number, 3]

1. Find x and y fulfilling the conditions of proposition 6.8

2. p is smallest prime factor of n

3. Can be considered as a one-way function

What are the characteristics?

[oneway.algorithm.factorization.number, 2]

1. Computing n is easy

2. Factorization into p and q is computationally infeasible

List them!

[algorithm.factorization.number]

1. Quadratic Sieve

2. Elliptic Curve Factoring

3. Number Field Sieve

Étudier

CYG Chapter 6 Number-Theoretic Reference Problems

Créer ou copier des fichiers d'apprentissage

Cartes-fiches

Veuillez vous connecter

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog