On Wed, 2022-02-23 at 09:53 +1100, David Harvey wrote: > On Tue, 2022-02-22 at 23:23 +0100, Marco Bodrato wrote: > > Ciao David, > > > > Il Mar, 22 Febbraio 2022 10:55 pm, David Harvey ha scritto: > > > On Tue, 2022-02-22 at 22:39 +0100, Marco Bodrato wrote: > > > > > E.g, in this case we could try a top-level B^66 - 1 product, split > > > > > in > > > > > B^33+1 and B^33-1; then the former suits your new algorithm well, > > > > > but > > > > > the former can't be recursively split (at least not on a B > > > > > boundary). > > > > > > I fully agree. > > > > > What about > > > > > > B^33 - 1 = (B^11 - 1)(B^22 + B^11 + 1)? > > > > Actually, B is a number. > > > > And if B is a power of 4 (there is an even number of bits in a limb, as > > usually happens, e.g. 32, or 64) then (B^n-1) and (B^2n+B^n+1) are not > > coprime, because both are divisible by 3. And we can not use CRT. > > Yes good point. > > But (N-1) and (N^2+N+1)/3 are relatively prime, where N = B^n, because > > (N^2+N+1)/3 - (N-1) (N+2)/3 = 1. > > So at least you can use CRT to get the answer mod (N^3-1)/3. Unfortunately > this is still not good enough, because N^3-1 is divisible by 9.
While N^2+N+1 is always divisible by 3, it is never divisible by 9. So maybe you could use the factorisation N^3 - 1 = (N^2+N+1)/3 * (3N-3). I think (?) the two factors on the right are always coprime. This would require a multiplication mod 3N-3 = 3 B^n - 3. If you are just calling a general multiplication routine then this shouldn't be too much trouble. But I guess it becomes more complicated if you want to use the idea recursively. david _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
