mpz_trial_div

[Torbjorn Granlund]

"Paul Leyland" <pleyland@microsoft.com> writes:

  > From: Torbjorn Granlund [mailto:tege@swox.com] 
  > "Paul Leyland" <pleyland@microsoft.com> writes:
  > 
  >   > Possible , although I think it is unneccessairy (as we have 
  >   > the mpz fn mpz_remove_ui) , consider
  >   > 
  >   > d=mpz_trial_div(N,1,10000);
  >   > m=mpz_remove_ui(N,N,d);
  >   > 
  >   > to cover the multiplicity case
  >   
  >   Fair point.  Thanks.
  > 
  > Not sure that would work.  Assume our number has the factor 3^2*5.
  > mpz_trial_div might find 3*5 and return that.  mpz_remove_ui
  > would then typically leave one factor 3.
  > 
  > Since some usages of mpz_trial_div will only care if any factor is
  > found, we don't want to slow it down by having it figure out any
  > factor multiplicity.
  
  I thought we'd agreed, wrongly it appears, that mpz_trial_div would
  return only prime factors and would always return the smallest such
  (perhaps in the range start--end if those arguments are present).

I haven't yet had time to read all messages in this thread (so I
suppose I should actually keep quiet...).

Is returning just prime factors worth making it slower?
I wrote code for this, for GMP 4.2, about half a year ago
(not yet committed to the cvs repo).

I found that accumulating groups of divisors mod m before
trying trial division (by means of gcd) was an efficient way
of implementing mpz_trial_div.  But of course we may return
non-prime factors.

-- 
Torbjörn