In this case we will solve the \(k\)th root of \(n\) (modulo \(p\)) and find the result (\(x= \sqrt[k]{n} \pmod p \). For this we need to find the value of \(k\) so that : \( n^k \pmod p = x\)).
kth root of n (mod p) |
Outline
In public key cryptography we typicall use prime numbers and the modulus operation. Basically, we can perform any maths operation we want, and then reverse it. So we could add:
\(c = a + b \pmod p\)
and which has the same result as:
\(c = (a \pmod p) + (b \pmod p) \pmod p\)
We could then multiply and reverse it with a divide (which is known as an inverse mod). Basically, we have a ring caused by the prime number (p), and where the values go between 0 and p-1. The laws that we then create are the Identity, Associated and Commutative laws:
Identity Law a + 0= 5 0 + a= 5 Associate Law a+(b+c)= 15 (a+b)+c= 15 Commutative Law a+b= 27 b+a= 27 Identity Law a * 1= 6 1 * a= 6 Associate Law a*(b*c)= 13 (a*b)*c= 13 Commutative Law a*b= 24 b*a= 24
These laws are normal in our maths, and where a*b is the same as b*a. You can learn more [here].
If you don’t know it, the (mod) operation is the remainder from an integer division, and in cryptography, we are typically only interested in the remainder.
Finding the root (mod p)
In maths, we should know that:
\(2^3 = 8\)
and that:
\( \sqrt[3]{8} =2 \)
But, in discrete methods, we need solve the \(k\)th root of \(n\) modulo \(p\) and find the result:
\(x= \sqrt[k]{n} \pmod p \)
For this we need to find the value of \(x\) so that:
\( x^k \pmod p = n\)
A few examples of these are:
2nd root of 5 (mod 11) = 4 3rd root of 5 (mod 11) = 3 4th root of 5 (mod 11) = 2 5th root of 5 (mod 11) = None 6th root of 5 (mod 11) = 5 7th root of 5 (mod 11) = 4 8th root of 5 (mod 11) = 3 9th root of 5 (mod 11) = 9 10th root of 5 (mod 11) = None
Thus \(4^2 \pmod {11}\) is \(16 \pmod {11}\) and gives you 5. \(3^3 \pmod {11}\) gives you 5, and \(2^4 \pmod {11}\) you get 5. Notice, there are a few that do not give any roots, as there is no basic solution for that root.
Some simple code which searches for the root is:
import sys def findnroot(x,n,p): for k in range(1,p): if (pow(k,n,p)==x): return(k) p=17 n=2 if (len(sys.argv)>1): n=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) for root in range(2,p): if (root>50): break v=findnroot(n,root,p) if (root==2): print(f"{root}nd root of {n} (mod {p}) = {v}") elif (root==3): print(f"{root}rd root of {n} (mod {p}) = {v}") else: print(f"{root}th root of {n} (mod {p}) = {v}")