> we can still recover mᵉ = m⁶⁵⁵³⁷, but finding m would be much harder, if possible at all<p>On my (low-end) machine, I can compute 65537th power of a 4096-bit message in ~4 seconds. So just throwing binary search at the problem would give me the answer in 5 hours or so. There are more sophisticated root-finding algorithms that would be likely much faster.