mpz_nextprime

[Seth Troisi]

Another small patch for nextprime.

I've fairly sure moduli is allocating extra space.

eights:~/Projects/git-gmp$ grep -ri TMP_SALLOC_TYPE
gmp-impl.h:#define TMP_SALLOC_TYPE(n,type) ((type *) TMP_SALLOC ((n) *
sizeof (type)))
gmp-impl.h:#define TMP_SALLOC_LIMBS(n)     TMP_SALLOC_TYPE(n,mp_limb_t)
gmp-impl.h:#define TMP_SALLOC_MP_PTRS(n)   TMP_SALLOC_TYPE(n,mp_ptr)
mpz/nextprime.c:  moduli = TMP_SALLOC_TYPE (prime_limit * sizeof moduli[0],
unsigned short);

I ran t-nextprime and attached a patch, happy to be wrong for some silly
reason



On Wed, Sep 4, 2019 at 11:00 AM Niels Möller <nisse at lysator.liu.se> wrote:

> paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>
> > with a small base, no need of k-ary modexp. In the REDC domain, instead
> of
> > computing a'*b'/r mod n, where  b' = r*b mod n is the REDC encoding of
> the
> > base b, just compute a'*b mod n.
>
> Right, since the montgomery/redc mapping a <-> a' is linear, the needed
> multiply operation is simply
>
>    x --> x * b (mod m)
>
> no matter if x is in montgomery representation or not. The easy way to
> do that is x * b followed by euclidean division with a single-limb
> quotient. One could perhaps also do x * b / B (mod m), with a
> single-limb hensel quotient. One then has to keep track of those powers
> of B^-1, and it's unclear to me if they can be handled efficiently
> enough to make Hensel-division useful here.
>
> Another trick (I think Marco already mentioned this) may be to find the
> largest k such that c = b^k fits in one limb, and compute
>
>   b^e = c^{floor(e/k)] * b^{e mod k}
>
> (and if we handle b = 2 as a special case, one could take k =
> GMP_NUMB_BITS, even if c then doesn't quite fit in one limb)).
>
> That will save log_2(k) squarings, so will make a nticable difference
> only when the exponent is few limbs. But could be relevant for
> millerrabin tests of numbers of a hundred bits or so.
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fix_overalloc.patch
Type: text/x-patch
Size: 663 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20190904/e13a0282/attachment.bin>