flint-devel

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

[Peter S. <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

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

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

Holy moly!! That was quick work. I thought it would take you at least
a week to write that code. That's amazing.

I only just figured out the best hash function to use last night, and
it is precisely the one you chose. Well done!

The idea I had doesn't work I think. It was basically this:

Suppose we want 2^K mod n1, n2, ..., nr

where n1, n2, ..., nr are all relatively close together (and so in our
case coprime).

My thought was to first compute A = 2^K mod n1*n2*....*nr using
multiprecision arithmetic.

Now we get 2^K mod n1*n2*...n{r/2} and 2^K mod n{r/2+1}*...*nr

simply by reducing A modulo both of the smaller products.

We keep splitting the products into two (recusively), until we are
finally getting 2^K mod n1, n2, ...., nr.

This definitely won't work with ordinary GMP division however, since
it uses an algorithm which is asymptotically too slow (O(M(n)log(n))
where M(n) is the time taken to do a multiplication. However, FLINT
has some code for Montgomery multiplication in fmpz.c/h which gets rid
of that extra log factor in precisely this situation. I can't recall
if we already implemented reduction modulo a whole pile of n's using
montgomery multiplication yet or not. If it is there, it is exactly
what you need. If not, I have to implement it anyway.

But, I'm still not convinced my idea works anyway. We could try it I
suppose. But I think I convinced myself yesterday it will actually be
slower than computing the individual 2^K mod ni's

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
>
>

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

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

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
>

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
>>
>

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

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

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
>

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
>>
>