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

[Bill H. <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
>>
>