Photo by Dan Cristian Pădureț on Unsplash

kth root of n (mod p)

What is the 7th root of 2 (mod 13)? Well, the answer is 11, and I will show you how we get this. In this article we will solve the kth root of n (modulo p) and find the result:

For this we need to find the value of k so that: n^k (mod p)=x, and using the Extended Euclidean method. Note, it will only work when gcd(k,p−1) is equal to 1.

Normal roots

In maths, we should know that:

and that:

But, in discrete methods, we need solve the kth root of n modulo p and find the result:

For this we need to find the value of x so that:

One of the most prominate methods is the Euclidean method, and which determines the largest common factor (gcd — greatest common denominator) between two numbers. For example:

gcd(27,9) = 3
gcd(27,13) =1

In cryptography, we often focus on making sure that two values do not share the same factor, and thus often use gcd(a,b)=1. Another widely used method is known as the Extended Euclidean method, and where we find a solution for:

a.x+b.y=gcd(a,b)

and where we know a and b and want to discover x and y. In this case gcd(a,b) defines the greatest common factor between a and b. If a and b do not share a factor, the gcd() will be 1…