Re: [flint-devel] Simultaneous Sieving and Trial factoring or Pocklington

[Peter S. <ps...@gm...>]

Hello

I think I have found the problem. The problem with the Pocklington-Lehmer
test is that if you want to prove somthing is composite then you have to
show that no b between 2 and n-1 satisfies

1) n is a b-fermat-psudoprime and
2) gcd(b^((n-1)/p)-1,n)=1

My code searched through all of the b's until it found one that worked or
reached _iterations_ whereupon it returned -1. I realized that as we are
doing a fermat-psudoprime test we can return 0 if it fails any of these
tests. This is far from fool proof because of Carmichael numbers but it will
help alot. I think proving that numbers are composite using the
Pocklington-Lehmer test may be a lost cause.

There are currently two different algorithms for doing the
Pocklington-Lehmer test implemented in my code. One simply searches through
the b's from 2 to iterations and checks conditions 1 and 2. The other uses
the ideas from http://www.jstor.org/stable/2005583?seq=4 to reduced the
number of gcd calculations. I have done some quick tests to see which is
quicker and I think the second one is but im not sure if this will still be
the case when we use the code.

Peter


2008/8/6 Bill Hart <goo...@go...>

> Peter,
>
> I merged your Pocklington-Lehmer code, but some kind of obscure bug
> exists. For n = 449*479 it returns -1 (I changed the return values by
> swapping your -1 and -2, since eventually -2 won't be needed).
>
> I set the number of iterations to 1000 and it runs out of iterations.
> This is pretty suspicious, since this is a pretty small number. It
> should be able to rule that it is composite pretty easily. Something
> seems to be wrong. Do you want to have a look and see if you can
> figure it out.
>
> You have to check out flint/trunk and do make long_extras-test then
> run long_extras-test
>
> Bill.
>
> 2008/8/5 Peter Shrimpton <ps...@gm...>:
> > Hello Bill
> >
> > I have written some code to sieve and factor simultaneously
> >
> > sievefact.c sieves a chunk of numbers and uses the trial devision to
> factor
> > n-1 for all n that get through the sieve. It uses a hash table to reduce
> the
> > storage space required with the hash function being the 2nd to last 4
> bits.
> > (The last bit is alway the same). This seams to work very well indeed.
> >
> > sievfact2.c simultaneously sieves and checks to see if it can find a b
> such
> > that gcd(b^((n-1)/p)-1,n)=1. It uses the same code as sievefact.c but it
> > doesn't store the factors, only the cofactor. This could be useful if the
> > Pocklington test is quicker then the pseudoprime tests the only trouble
> > being to then decide which numbers to do the pseudoprime tests on to find
> a
> > counter example to the Baillie-PSW test.
> >
> > Would it be possible for you to explain your idea about calculating
> powers
> > of 2 mod N for lots of different numbers at once again? I can't quite
> > remember exactly how it was to be done or how we could go about splitting
> > the powers up once we had calculated the power of the product. An
> > explanation in an email should suffice.
> >
> > I have also written a program that uses the list I emailed you before to
> > look for counter examples to the Baillie-PSW test below 2^63.
> Unfortunately
> > there weren't that many products in the list that were less then2^63 and
> I
> > didn't find any counter examples. Maybe it could be worth implementing a
> > Baillie-PSW test in fmpz's and having another go?
> >
> >
> > Peter
> >
> > -------------------------------------------------------------------------
> > This SF.Net email is sponsored by the Moblin Your Move Developer's
> challenge
> > Build the coolest Linux based applications with Moblin SDK & win great
> > prizes
> > Grand prize is a trip for two to an Open Source event anywhere in the
> world
> > http://moblin-contest.org/redirect.php?banner_id=100&url=/
> > _______________________________________________
> > flint-devel mailing list
> > fli...@li...
> > https://lists.sourceforge.net/lists/listinfo/flint-devel
> >
> >
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's
> challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>