Trial-division interface

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> I've been thinking a little about what an mpz-level interface for trial
> division should look like. One fairly natural interface would be
> something like
>
>   int
>   mpz_small_factor_p(unsigned int *f, const mpz_t n, unsigned int b);

Here's an simple implementation of a related function, using
mpn_trialdiv:

  unsigned long
  mpz_trialdiv (mpz_srcptr n, unsigned long nprimes)
  {
    mp_srcptr np = PTR (n);
    mp_limb_t factor;
    int where = 0;
  
    ASSERT (nprimes > 0);
  
    /* Must handle the prime 2 specially. */
    if ( (np[0] & 1) == 0)
      return 2;
    if (nprimes == 1)
      return 0;
  
    factor = mpn_trialdiv (np, ABSIZ (n), nprimes-1, &where);
    if (factor > 0)
      binvert_limb (factor, factor);
  
    return factor;  
  }

It returns the smallest prime factor of n, if that factor is included in
the compiled in list. First question: Do I use the mpn_trialdiv function
correctly?

There is one serious problem with this interface, and that is that the
caller has no way of knowing if the search is limited by the caller's
nprimes, or by the size of the compiled in prime list. So one needs
either a way to get the size of that list, or some way to grow it as
needed, or a special return value to indicate that the compiled in list
was exhausted before the caller's bound was reached.

And then the interface should be generalized to take a prime size
(rather than a prime count) as a limit, and preferably even a range
rather than a single bound.

Regards,
/Niels

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