View Single Post
Old 2014-12-27, 18:22   #24
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

72×31 Posts

Originally Posted by TeknoHog View Post
Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case r|y, but it's still a considerable speedup.
Yes, you are right, but it is still better to check that r|(x^n-1) is true or not. These methods just working, for a recent similar problem see this is even a harder problem since there half of the input is a perfect power.
R. Gerbicz is offline   Reply With Quote