
Problem with SolovayStrassen primality test
Hi There,
I have a problem with the above primality test.
This probabilistic test is given as:
* Choose a random a < p
* If GCD(a, p) not equal to 1, p is composite
* Calculate j = a^((p1)/2) mod p
* Calculate the Jacobi symbol J(a, p)
* If j not equal to J(a; p), then p is not prime
* If j = J(a, p), probability p prime > 50%
where a is a random integer, and p is the number we are testing for
primality.
However, how do I calculate J(a,p), where J(a,p) is the Jacobi
symbol? According to wikipedia (http://en.wikipedia.org/wiki/
Jacobi_symbol#Definition), we have to determine all the factors of n,
which defies the purpose of the exercise  we want to avoid the
factorization of the number. Should we rather then determine the
Legendre symbol for p and compare p with the Euler identity a^((p1)/
2)?
In the Legendre Symbol, how do we calculate if a is a quadratic
residue mod p?
Your time, effort and suggestions will be greatly appreciated
Jaco
_______________
Jaco Versfeld
http://dept.ee.wits.ac.za/~versfeld
"It is not the best team that wins, but the team that gets along best
that wins" John C. Maxwell

Re: Problem with SolovayStrassen primality test
On Mar 8, 11:17 pm, jaco.versf...@gmail.com wrote:
> However, how do I calculate J(a,p), where J(a,p) is the Jacobi
> symbol? According to wikipedia (http://en.wikipedia.org/wiki/
> Jacobi_symbol#Definition), we have to determine all the factors of n,
> which defies the purpose of the exercise  we want to avoid the
> factorization of the number. Should we rather then determine the
> Legendre symbol for p and compare p with the Euler identity a^((p1)/
> 2)?
>
You can compute Jacobi symbols quickly using Jacobi's extension to
quadratic reciprocity for Legendre symbols.
> In the Legendre Symbol, how do we calculate if a is a quadratic
> residue mod p?
>
The Legendre symbol is defined only for primes p, so trying to prove
primality by evaluating it is circular. The Jacobi symbol is defined
for all numbers and can be used to test for primality. In any case,
the formula for the Legendre symbol is a**((p1)/2) mod p. So
basically, the SolovayStrassen test checks to see if the formula for
the Legendre symbol applied to n matches the value of the Jacobi
symbol at n.
You might want to be aware that the de facto standard test is the
MillerRabin test. It misses far fewer composites for a given set of
bases; indeed every strong (MillerRabin) pseudoprime is an Euler
(SolovayStrassen) pseudoprime, but not vice cersa. It is also
slightly faster and there is a deterministic variant conditional on
GRH.

Re: Problem with SolovayStrassen primality test
On Sat, 8 Mar 2008 07:17:17 0800 (PST), jaco.versfeld@gmail.com
wrote:
>However, how do I calculate J(a,p), where J(a,p) is the Jacobi
>symbol?
Have a look at Algorithm 2.3.5 in Crandall and Pomerance.
rossum

Re: Problem with SolovayStrassen primality test
jaco.versfeld@gmail.com writes:
> Hi There,
>
> I have a problem with the above primality test.
>
> This probabilistic test is given as:
>
> * Choose a random a < p
> * If GCD(a, p) not equal to 1, p is composite
> * Calculate j = a^((p1)/2) mod p
> * Calculate the Jacobi symbol J(a, p)
> * If j not equal to J(a; p), then p is not prime
> * If j = J(a, p), probability p prime > 50%
>
> where a is a random integer, and p is the number we are testing for
> primality.
>
> However, how do I calculate J(a,p), where J(a,p) is the Jacobi
> symbol? According to wikipedia (http://en.wikipedia.org/wiki/
> Jacobi_symbol#Definition), we have to determine all the factors of n,
> which defies the purpose of the exercise  we want to avoid the
> factorization of the number.
Why don't you just read the rest of the information on that
page  it's all there?
Phil

Dear aunt, let's set so double the killer delete select all.
 Microsoft voice recognition live demonstration