6 - Number THeory Part 2

Question 1

Discrete Logarithm:

Computing it and is there an efficient algorithm to crack it?

Answer 1

Given n, g,h compute log g (h) mod n

No efficient algorithm for this

Question 2

Diffie Hellman Key Exchange basis

Answer 2

It is easy to compute the exponent of something but difficult to comput the discrete logarithm.

Question 3

Quantum Computers, can they compute discrete logarithm efficiently (in polynomial time)

Answer 3

Yes

Question 4

Fermat’s Little Theorem to find/verify primitive element

Answer 4

p is a prime and g is an integer in {1,2,…,p-1} which is a primitive element:
we have g^(p-1) mod p = 1

Direct definition: a^p mod p = a mod p

Question 5

Primitive Root/element

Answer 5

g is a primitive root mod p if g^0,g^1,..,g^(p-2) are all different

Also:
- log g h exists for all h except 0
- the seq only repeats after p-1 elements and not earlier

Question 6

Is 2 a primtive modulo 7?

Answer 6

No, log2(3) does not exist in Z7

2^0=1
2^1=2
2^2= 4
2^3 = 1
2^4 =2

Question 7

For any prime p, there are _____ elements modulo p

Answer 7

primitive

Question 8

Why does normal logarithm work easily but the discrete logarithm is hard?

Answer 8

Normal is always increasing so you can easily approxmiate the upper and lower bound and then trial within that

Discrete does not necessarily have any order