Torbjorn Granlund <t...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel