Jacobi symbol using Lehmer's algorithm.

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I know that this does not prove anything, one should not use random
> operands, but generate some cleverly selected special values...

Yesterday, I and Torbjörn had a short discussion on the Jacobi
algorithm, including the testing issues, with Johan Håstad. We came up
with the following strategy.

Stage 1, random inputs:

Generate a dozen or so of odd primes. Then randomly select b as a
product of some of these primes (possibly with multiplicity; only primes
of odd multiplicity affects the result), and a random a. Then as a
reference implementation, compute (a | b) using the known factorization
and the Legendre symbol formula (a | p) = a^{(p-1)/2} mod p.

One could also generate a:s with predetermined values of (a | b), by
selecting squares and non-squares mod each prime and combine using CRT.
This is more complicated but probably more efficient, since we only need
to exponentiate until we find a *single* non-sqare mod each prime.
During the bulk testing we can cheaply constructs inputs with known
Jacobi symbol based on random squares and non-squares mod each prime,
without any further exponentiations.

Stage 2, large quotients (this is for left-to-right algorithm, but I
think something similar could be done for the 2-adic quotient sequence
in Brent and Zimmermann's right-to-left algorithm):

Like in the gcd testing, first generate a pair of coprime numbers with
large quotients in their continued fraction expansion, as

  r_0 = 0
  r_1 = 1
  r{j+1} = r_{j-1} + r_j q_j

with some random quotient distribution which favours large quotients.
Iterate until we have a pair r_{k-1}, r_k of the desired size. If one of
these is prime, use these as jacobi inputs, and use the Legendre formula
as reference. Otherwise, continue to iterate

  r_{j+1} = r_{j-1} + r_j

until a prime is found. This final search can be sped up by sieving
techniques, if needed.

Regards,
/Niels

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