3 ms·
> Thank you. You're welcome > Yeah, it's going to take me a bit to work through all that. It does go stage by stage, so get a good feel for the proof of Wils
by ColinWright 7y ago
> Thank you.
You're welcome
> Yeah, it's going to take me a bit to work through all that.
It does go stage by stage, so get a good feel for the proof of Wilson's theorem first. That gives you most of the necessary tools for the insight in the next step.
> On the last paragraph: I had thought (assumed?) that, in the integers mod p, (a * b)/b was hard if p was large. Is there an algorithm better than O(p) for this?
You can find the multiplicative inverse in Z_p by using an extended Euclidean Algorithm, which works in O(log p), and hence is trivial.
> My group was the complex integers modulo p. Now to do (a * b)/b, you have to find both the real and imaginary components of a.
Probably similarly efficient, as the Euclidean Algorithm works in the Gaussian Integers, but I haven't checked it.
My contact details are in my profile.