[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-devel
Subject:    Jacobi symbol  using Lehmer's algorithm.
From:       nisse () lysator ! liu ! se (Niels =?iso-8859-1?Q?M=F6ller?=)
Date:       2010-01-29 9:34:37
Message-ID: nnk4v12r0y.fsf () stalhein ! lysator ! liu ! se
[Download RAW message or body]

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.

[prev in list] [next in list] [prev in thread] [next in thread]