|
From: Peter S. <ps...@gm...> - 2008-08-06 10:52:16
|
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 > |