Hello there,

my book is asking to do the following problem :

Isn't there a typo in the last word, because I know about ways to take roots over when is a prime, which is not the case here, and as I looked over the internet, it seems a "hard" problem to take roots if is a composite ?Quote:

Given , design an algorithm to find in polynomial time know and , and given that the modulus is composite.

And also, if I know that , then the following must be true : , by dividing both sides by . However, if I take an example, say , and , we have alright, but and is not equal to one, however . Anyone know what I messed up here ?