Number theory for Public key Cryptography Flashcards

1
Q

What is the chinese remainder theorem?

A

Pairwise relatively prime: d1, d2,…,dr
n = d1d2…*dr

Given any integer ci there exist a unique integer x (0 <= x < n) such that
x ≡ c1 (mod d1)
x ≡ c2 (mod d2)

x ≡ cr (mod dr)

x ≡Sum(n/di) yi ci (mod n)

yi ≡ (n/di)^-1 (mod di)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does it mean to be pairwise relatively prime?

A

When two integers have gcd = 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Define the Euler function

A

Euler function Q(n) denotes the number of positive integers less than n and relatively prime to n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the residue clss Z_n^*

A

Set of positive integers less than n and relatively prime to n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are some properties of the Euler function?

A
  1. Ø(p) = p-1 for a prime p
  2. Ø(pq) = (p-1)(q-1), for distinct primes
  3. See notebook: way to find Ø(n) when prime factoring a number
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is Fermat theorem?

A

a^(p-1) mod p = 1

p: prime
a: integer 1 < a < p-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Eulers theorem?

A

a^Ø(n) mod n = 1,

if gcd(a,n) = 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the Fermat primality test?

A

if p is prime: a^(p-1) mod p = 1
for all a with gcd(a,p) = 1

If we examine a number n and find that a^n-1 mod n is not 1 -> a is not a prime

Fermat primality test: Check if a number satisfies Fermat’s equation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the inputs of Fermat primality test?

A

n: value to test for primality

k: parameter that determines number of times to test for primality

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the outputs of Fermat primality test?

A

Composite: If n is composity
Otherwise, probably prime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the Fermat primality test algorithm?

A

Repeat k times:

  1. pick a value of a randomly in the range 1 < a < n-1
  2. If a^n-1 mod n is not 1, return composite, if = 1 return probable prime
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does it mean when n is a pseudoprime?

A

When fermat test output probable prime when n is actually a composite

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are Carmichael numbers?

A

Compmosite numbers that satisfies:

b^n-1 ≡ 1 mod n

Composite numbers that will always output probable prime from the fermat test.

For every b with gcd(b,n) = 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the Miller-Rabin test?

A

Can guarantee to detect composites if run sufficiently many times.

Widely used to generate large primes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a modular square root of 1?

A

x^2 mod n = 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How does the Miller-Rabin test use square roots to find composite numbers?

A

n = pq gives 4 square roots of 1,

2 trivial: 1, -1

2 non-trivial

If x is non-trivial square root of 1, then gcd(x-1, n) is a non-trivial factor of n

An existence of a non-trivial square root of 1, implies that n is composite

17
Q

When n = pq, how many square roots are there of 1?

A

4

18
Q

What are trivial square roots of 1?

A

1, -1

19
Q

What is the Miller-Rabin algorithm?

A

n, u is odd
u,v such that n - 1 = (2^v)*u

  1. Pick a value for a randomly in 1 < a < n-1
  2. Set b = a^u mod n
  3. if b == 1 -> return probable prime
  4. for j = 0 to v-1
    - b == 1 -> return probable prime
    - else set b = b^2 mod n
  5. return composite
20
Q

Define the effectiveness of Miller-Rabin

A

Return composite -> n is composite

Return probable prime -> n may be composite

n is composite: test return probable prime with probability of 1/4. Because of this, repeate the algorithm 4 times while output is probable prime

k-times algorithm output probable prime when n is composite with probability (1/4)^k

21
Q

How can Miller-Rabin be used to generate large primes?

A
  1. Choose odd integer r, same number of bits as required prime
  2. Test if r is divisible of any list of small prime
  3. Apply Miller-Rabin with 5 random bases
  4. If r fails, set r = r + 2 and return to step 2

This does not generate completely random primes, to do so, go back to step 1 instead of 2

22
Q

What are the two aspects of computational complexity?

A

Algorithm complexity

Problem complexity

23
Q

What is algorithm complexity?

A

How long it takes to run an algorithm

24
Q

What is problem complexity?

A

What is the best (known) algorithm to solve a particular problem

25
Q

How do you measure algorithm complexity?

A

Measured by its time and space requirements as functions of the size of the input m

A positive function is expressed as an “order of magnitude” of the form O(g(m)), where g(m) is another positive function

26
Q

What is big O notation?

A

f(m) = O(g(m))

if a constant c>0 and m_0 such that f(m)<c*g(m) for m>=m_0

g is an upper bound for f

27
Q

What is a polynomial time function?

A

f(m) = O(m^t), t integer > 0

problems with polynomial time functions are efficient

28
Q

What is an exponential time function?

A

f(m) = O(b^m)

b>1,

problems with exponential time functions are hard

29
Q

How are problem complexity classified?

A

According to the minimum time and space needed to solve the hardest instances of the problem

30
Q

What are sub-exponential problems?

A

Slower than exponential but faster than any polynomial

31
Q

What is integer factorisation?

A

Find an integers prime factors

32
Q

What is the discrete logarithm problem?

A

Given a prime p and an integer y, 0 < y < p, find x such that:

y = g^x mod p

33
Q

What is the best known method of integer factorisation?

A

The number field sieve (sub-exponential algorithm)

34
Q

Describe discrete logarithm problem (DLP)

A

G: cyclic group, generator g

The discrete log problem in G is:

y in G, find x with y = g^x

35
Q

What happens if x is a non-trivial square root of n?

A

gcd(x-1, n) is a non-trivial factor of n

The existence of a non-trivial square root implies that n is composite