bdiv vs redc

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I don't think a remainder is meaningful here.

Ok, so the return value should be a proper root mod B^k (B =
2^{GMP_NUMB_BITS, as usual), or an indication that no root exists.

When a square root exists (and the input is non-zero), then there are
two square roots (if I remember correctly, prime powers behave like
primes rather than general composites in this respect, for which there
exists more than two square roots). Should we have some
canonicalization?

I haven't really looked into the perfpow code or theory, but let me
think aloud...

For perfpow, I guess all roots mod B^k must be considered as candidates
for a non-modular root. So, say we want to find the positive nth root of
a, and we know the size of the root (if it exists) must be k (or
possibly k-1) limbs.

Then for all modular nth roots x such that

  x^n = a (mod B^k)

we can check if x^n = a, and if we have equality for one of the
candidates, then a is a perfect power. I imagine most candidates can be
excluded by computing the highest few limbs of the power.

Is it easy to find all nth roots mod B^k, given one of them? If I got
the number of roots correctly (and I guess we have to assume that n <
B^k...), then they differ by a primitve nth root of unity. Does there
exist a primitive nth root of unity mod B^k for any n and k, and if so,
is it easy to find?

Ah, and one more thing... Since we're working mod a power of two, I
imagine there may be some fundamental differences between odd and even
n?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.