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 < p * If GCD(a, p) not equal to 1, p is composite * Calculate j = a^((p-1)/2) ...

+ Reply to Thread
Results 1 to 4 of 4

Problem with Solovay-Strassen primality test

  1. Default 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. Default 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
    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**((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. Default 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. Default 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

+ Reply to Thread