How to find primitive roots of prime number | Application of Primitive roots in cryptography

In this post I have explain two methods: 1. Primitive roots for short prime number 2. Primitive roots for large number.

How to find primitive roots for short prime number?

Step – 1: If ‘a’ is a primitive root of ‘q’. Where, q is prime number. Where a=1 to q-1.

Step – 2: aⁿ mod q. Where, n = 1 to q-1. It produces each integer from 1 to q-1 exactly once.

 

How to find primitive roots for large prime number?

Step – 1: Express Ø(q) = as possible powers of prime number (say a^x, b^y, etc.…)

Step – 2: Find A = Ø(q)/a, B = Ø(q)/b, … Let it be A, B, C, ….

Step – 3: Choose any number X. If n1 = X^A mod q, n2 = X^B mod q, ...      Where, n1 & n2 … ≠ 1, then X is a primitive root of q.

 

Application of Primitive roots in cryptography

Primitive root concepts are used in Diffie-Hellman key exchange algorithm.

Click here to watch video of How to find primitive roots of prime number

Watch more videos click here.