Re: [flint-devel] Additions to long_extras

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

Hello. Sorry for the late response.

The first version should work for everything except for a=1,b=1 and a=-1,b=1
although I am not sure how 'good' it is for large values of a and b. (i.e.
how many composites get through). I noticed that the "bug" I thought was in
the code was actually me misreading the $620 problem. There appear to be two
different versions:

1) a composite congruent to 3 or 7 mod 10 which passes both a
2-Fermat-pesudoprime test and a Lucas test with parameters a=1,b=-1

2) any composite which passes a 2-Strong-pesudoprime test and the second
version of the Lucas test.

I think the first is significantly quicker especially when a and b are fixed
because we can avoid doing the gcd and issquare tests.

Also I did some more tests on the Montgomery powering that I wrote with
mixed results. I did random 2-Fermat-pesudoprime tests to numbers of various
lengths and found that it was quicker.......but only when the numbers
reached 60 bits in length. We are only dealing with numbers between 53 and
57 bits.

I am currently working on optimizing the sieve so that it only looks at odd
numbers but still factorizes the even numbers. I need to calculate the
smallest j such that:

beginning+2*j = 0  mod p

I have tried using z_invert and modular arrithmethic but it seams to be
slower then a simple while (begining+2*j mod p !=0) j++; and there is no
guarantee that they will give the smallest j which is required. Is there a
quicker way of doing it?

Peter

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

> Hi Peter,
>
> I merged you Lucas pseudoprime tests and wrote test code. However I
> don't know what values of a and b are allowed in the first version of
> the test.
>
> I removed some minor bugs, and it also seems that P was being set to 1
> in the second test and therefore not being used, so I removed it.
>
> The second version works beautifully!!
>
> Bill.
>
> 2008/7/25 Peter Shrimpton <ps...@gm...>:
> > Hello
> >
> > Attached is the code that I have written to be attached to long_extras
> along
> > with the test code. Everything is passing the tests and I am confident
> that
> > everything is working. I am fairly certain that some things can be
> optimized
> > more which I will look into. Also could I ask for gcc to be upgraded on
> the
> > server so that I can begin programing in OpenMP.
> >
> > 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
>