mpz_jacobi

[Torbjorn Granlund]

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

  I've pushed in the new mpz_jacobi now.
  
Nice!

  I also enabled the large quotient tests in t-jac.c, which makes testing
  slower. I reduced the sizes used for testing a bit to make it more
  tolerable. Feel free to tweak further if testing takes too much time
  (currently t-jac takes 2.6 s on my x86_32 laptop and 1.1 s on x86_64
  shell).
  
These numbers should be OK.

  I wonder if nextprime and nextprime_step (in t-jac.c) shouldn't use a
  larger prime table; the Handbook of Applied Cryptography recommends a
  table of about 10000 small primes but I haven't done any relevant
  benchmarks recently.
  
This should be tuned after the speed of a division compared to the speed
of a full prp test.  I assume the decision for the current prime table
was made when a n-limb by 1-limb divide took ~15n+O(1) cycles.  Now it
takes 3n+O(1) cycles.  (Numbers for Athlon.)

It should not be hard to tune, actually.  The question we need to answer
is Should we divide N by p?  Assume n=log(N)/log(B), i.e., the word
count of N.  Plain trial division will take time kn+C (k = 3 for Athlon,
4.25 for Core i) and reject N with probability 1/p.  A prime test will
reject N with approximate probability 1-1/log(N) [we here use the
natural logarithm].  We could divide the time for each operation with
its probability of rejection to get some effectiveness comparison
numbers.  We then keep trial division until its number gets larger than
the prp comparison numbers.

-- 
Torbjörn