Re: [flint-devel] Additions to long_extras

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Can you take a look at the current code and test code,
because when I use anything other than a = 1 and b =
1, it doesn't declare all primes to be pseudoprime. I
did try to fix some minor issues with the original
code, but maybe I screwed something up.

As for your question:

If I want to do a/2 mod p, then if a is even I just do
a/2, if a is odd I just do (a+p)/2. No inverse mod p
is necessary. 

Therefore all I need to do is:

1) let beg = beginning mod p
2) let s = p - beg (let s = 0 if beg = 0)
3) compute s/2 mod p.

Bill.

--- Peter Shrimpton <ps...@gm...> wrote:

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