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\), and using the using the Extended Euclidean method. Note, it will only work when \(gcd(k,p-1)\) is equal to 1.
kth root of n (mod p) - Using Extended Euclidean method |
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\)
Extended Euclidian method
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. For example, if \(a=5\) and \(b=6\), we can use the Extended Euclidean method (xgcd()) with:
import libnum a=5 b=6 (x,y,r) = libnum.xgcd(a,b) print (x,y,r)
This gives:
-1 1 1
In this case we have \(-1(5)+1(6) = 1\) and which is true. If we now try \(b=8\), we get a result of:
-3 2 1
This gives us \(-3(5)+2(8) = 1\) and which is true.
RSA and Extended Euclidian
One of the best usages of the Extended Euclidian method is in RSA encryption. For this, we take two prime numbers (\(p\) and \(q\)) and determine the public modulus (\(N\)):
\(N = p.q\)
Next we compute \( \varphi\):
\( \varphi= (p-1) . (q-1) \)
We then pick our encryption exponent (\(e\)) to not share a factor with \( \varphi \), then compute the decryption exponent (\(d\)) with:
\( d.e = 1 \pmod \varphi \)
and which is equivalent to:
\(d⋅e+\varphi.t=1\)
This is in the form of the Extended Euclidian method and which gives a solution of \(d\) and \(t\). We can compute the value of \(d\) with:
(d,_,r) = libnum.xgcd(e,PHI)
The code to implement this is:
>>> e=7 >>> p=97 >>> q=101 >>> N=p*q >>> PHI=(p-1)*(q-1) >>> import libnum >>> print (libnum.gcd(e,PHI)) 1 >>> (d,_,r) = libnum.xgcd(e,PHI) >>> print (d,r) 2743 1 >>> print (d*e % PHI) 1
We can now encrypt and decrypt with these values:
>>> M=5 >>> C=pow(M,e,N) >>> print (C) 9546 >>> Rec=pow(C,d,N) >>> print (Rec) 5
Determine \(k\)-th root of \(n\) (mod \(p\))
We can use the Extended Euclidian method to determine the \(k\)-th root of a value (\(n\)) modulo \(p\). With this, for \(\sqrt[k]{n} \pmod p\), and if \(gcd(k,p-1)=1\), there exists a solution of \(m\) and \(t\) for:
\(m.k + t.(p-1) = 1\)
This is in the form of the Extended Euclidian method, and the solution is then [1]:
\(n^m = \sqrt[k]{n} \pmod p \)
The code to find the value of \(m\) and the root is then:
import sys from libnum import xgcd def findnroot(n,k,p): (m,s,v) = xgcd(k,p-1) if (v==1): return(pow(n,m,p))
A few examples of these are:
2nd root of 5 (mod 11) = None 3rd root of 5 (mod 11) = 3 4th root of 5 (mod 11) = None 5th root of 5 (mod 11) = None 6th root of 5 (mod 11) = None 7th root of 5 (mod 11) = 4 8th root of 5 (mod 11) = None 9th root of 5 (mod 11) = 9 10th root of 5 (mod 11) = None
\(3^3 \pmod {11}\) gives you 5, and \(4^7 \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. This is either because there is no root, or that the gcd(k,n-1) is not equal to 1.
Some simple code which uses the Extended Euclidian method for the root is:
import sys from libnum import xgcd def findnroot(n,k,p): (m,s,v) = xgcd(k,p-1) if (v==1): return(pow(n,m,p)) 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}")
Reference
[1] kth roots in mod p arithmetic - University of Notre Dame [here ]