# Problem with Solovay-Strassen primality test - DSP

This is a discussion on Problem with Solovay-Strassen primality test - DSP ; Hi There, I have a problem with the above primality test. This probabilistic test is given as: * Choose a random a &lt; p * If GCD(a, p) not equal to 1, p is composite * Calculate j = a^((p-1)/2) ...

1. ## Problem with Solovay-Strassen 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^((p-1)/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^((p-1)/
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

2. ## Re: Problem with Solovay-Strassen 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^((p-1)/
> 2)?
>

You can compute Jacobi symbols quickly using Jacobi's extension to

> 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**((p-1)/2) mod p. So
basically, the Solovay-Strassen 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
Miller-Rabin test. It misses far fewer composites for a given set of
bases; indeed every strong (Miller-Rabin) pseudoprime is an Euler
(Solovay-Strassen) pseudoprime, but not vice cersa. It is also
slightly faster and there is a deterministic variant conditional on
GRH.

3. ## Re: Problem with Solovay-Strassen 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

4. ## Re: Problem with Solovay-Strassen 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^((p-1)/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