bdiv vs redc
Niels Möller
nisse at lysator.liu.se
Tue Jul 17 22:20:31 CEST 2012
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.
More information about the gmp-devel
mailing list