Re: WAS Frobenius, so good?

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 01/12/05

  • Next message: Cristiano: "Re: WAS Frobenius, so good?" 
    Date: 12 Jan 2005 01:11:29 +0200

    "Cristiano" <cristiano.pi@NSquipo.it> writes:

    > Marcel Martin wrote:
    > > Cristiano a écrit :
    > >> The 'official' BW test says:
    > >>
    > >> 1) if N is a perfect square, then return "composite"
    > >
    > > Yes, but practically, you shouldn't perform this test first. You
    > > should first search for the Jacobi symbol. If after, say, 5000
    > > attempts, you fail to find D then, and only then, you should test
    > > whether N is a square. (Finding D such that J(D,N) = -1 does prove
    > > that N is _not_ a square)
    >
    > I changed the code as you told me; now with composites it is 0.046% faster!
    > :-)
    > But with primes it is 0.29% slower.
    > It seems that mpz_perfect_square_p() is very fast.

    I would guess that it does about a dozen jacobi tests in parallel,
    maybe more. Therefore is should be faster in both cases, unless you
    too parallelise jacobi tests.

    Phil 

    -- 
The gun is good. The penis is evil... Go forth and kill.
  • Next message: Cristiano: "Re: WAS Frobenius, so good?"