I am trying to solve an rsa problem where we only know the public key (n,e) and the ciphertext c.
The modulus n is actually a prime number, so we can easily compute phi as phi = n-1.
But the problem is that e shares a common factor with phi, where gcd(e,phi) = 8 , where gcd = greatest common divisor. So this means we can't get the private key d. Also e is a power of 2 (e = 16).
In my research I found that this problem has to do with something called "roots of unity modulo n". So basically if I compute all roots of unity I can get all possible plaintexts. But i can't seem to be able to understand the concept of "roots of unity mod n" and how this helps find all possible plaintexts.
Could someone please explain to me this ?