> < ^ From:

> ^ Subject:

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

> < [top]