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

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Yea I didn't have it returning 0 when it failed a pesudoprime test. But I
changed that and it now passes the test.

Peter

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

> Right, we can't use it to prove compositeness, but that number isn't a
> charmichael number is it?
>
> It just seems like a very small composite number to pass 1000
> different Fermat pseudoprime tests.
>
> Bill.
>
>
> On 06/08/2008, Peter Shrimpton <ps...@gm...> wrote:
> > 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
> >>
> >
>
> -------------------------------------------------------------------------
> 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
>