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

[Bill H. <goo...@go...>]

Great!

Bill.

On 06/08/2008, Peter Shrimpton <ps...@gm...> wrote:
> 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
>>
>