3 ms·
Thank you. Yeah, it's going to take me a bit to work through all that. (I'm thinking about this in my evenings, and when tests are running at work.) On the l
by AnimalMuppet 7y ago
Thank you.
Yeah, it's going to take me a bit to work through all that. (I'm thinking about this in my evenings, and when tests are running at work.)
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?
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.
- 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.