Hello Forumites,

I have been digging around the code for roots of
unity in the rings Z_n, and have found a technique
called the "Newton/Hensel method of lifting".
Does anyone have a reference that might explain the
algorithm, proof of its validity, etc.

I also have run up against the problem that Gap
guarantees accuracy in RootsUnityMod only for
k-th roots where k is a prime number. I want to
find the (p-1)th roots of 1 in Z_(p^i) for various i.
For p > 3, then p-1 is nonprime. How can the algorithm
be extended to deal with such cases? Experiments have
shown that the algorithm works occasionally, but also
fails sometimes.

Thanks for help,

Tim Boykett