flint-devel — Development list for the FLINT project

[flint-devel] Counter examples to Baillie PSW test

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

Hello

As the computer room is closed today I have been doing some reading about
the Baillie-PSW test (combined 2-SPRP and Lucas test) I have found a paper
written buy Pomerance give a suggested method for finding counter examples:

www.pseudoprime.com/dopo.pdf

Unfortunatly I think it will be too slow to turn into an algorithem and even
if it was quick enough I think the numbers generated may be too big for the
current implementation. Someone has used this paper to compile a list of
primes of which some sub-product might trick the Baillie-PSW test:

http://www.pseudoprime.com/primes620.txt

The list is too long to do an exhaustive search but could prove interesting
for future projects.

Peter

Re: [flint-devel] gcc-4.3.1 installed on host-57-44

[William H. <ha...@ya...>]

Actually, after I installed it I found there was some
kind of conflict with the existing gcc (it wouldn't
build FLINT). So I tried to fix it, and managed to
kill the server. I can't restart it until some time
Monday afternoon.

Looks like we lose a day of coding. But it will give
you guys a chance to do some more research.

Bill.

--- Bill Hart <goo...@go...> wrote:

> Hi all,
> 
> I've installed gcc-4.3.1 in /usr/local on
> host-57-44. It took most of
> the day to build and used more of my problem solving
> skills than I
> would prefer, but it seems to work.
> 
> If you do:
> 
> export PATH=/usr/local/bin:$PATH
> 
> it hopefully will use the new gcc instead of the
> systemwide gcc.
> 
> I don't know if any other things need to be added to
> the path.
> 
> The big advantage of gcc-4.3.1 is that it allows you
> to build software
> using the new OpenMP standard.
> 
> I *think* sage builds with gcc-4.3.1 these days.
> 
> Bill.
> 
>
-------------------------------------------------------------------------
> 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
> 



      

[flint-devel] gcc-4.3.1 installed on host-57-44

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

Hi all,

I've installed gcc-4.3.1 in /usr/local on host-57-44. It took most of
the day to build and used more of my problem solving skills than I
would prefer, but it seems to work.

If you do:

export PATH=/usr/local/bin:$PATH

it hopefully will use the new gcc instead of the systemwide gcc.

I don't know if any other things need to be added to the path.

The big advantage of gcc-4.3.1 is that it allows you to build software
using the new OpenMP standard.

I *think* sage builds with gcc-4.3.1 these days.

Bill.

Re: [flint-devel] Updates 25/7/2008

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

An excellent book to get started on class field theory is Cox's book
Primes of the form x^2+ny^2. It should be easily accessible to an
undergrad at Warwick.

But someone already worked through that book as a 4th year project.
I'd like to see someone try to tackle the infamous Algebraic Number
Fields, J.W.S. Cassels, A. Frölich (Eds.). That's much, much harder,
and should probably be read in conjunction with a book like Cox's and
some decent books on algebra. But it is a goldmine and can take you
much further than a 4th year project. :-)

Bill.

2008/7/25  <D.C...@wa...>:
> Hi,
>
> Yes my first priority is to do the function interface. Unless you'd like
> the report done sooner rather than later, I was thinking of perhaps
> writing the report the first week after my project when I'm at home to
> free up time for research, and that way it won't be rushed at all either.
> I suppose it depends how things are going this time next week. With
> regards to class field theory, it does look very interesting and I'm going
> to look into doing my 4th year project in it.
>
> Thanks,
>
> Daniel Ellam
>
>
>
>
>> Daniel,
>>
>> That's exceptional progress. I didn't know about any
>> of those papers and they are all excellent.
>>
>> Concentrating on ramified and unramified extensions
>> sounds like a good way to spend the remainder of the
>> project.
>>
>> Of course we definitely need the function interface.
>> That's the primary goal.
>>
>> I'd really like to have a longer report with a list of
>> everything you have found all in one place. This could
>> be put on the FLINT website, and you could take your
>> URSS poster from parts of it.
>>
>> Class field theory is an exceptionally detailed topic
>> which could take many months to learn. Not to
>> discourage you at all from looking into it; it is one
>> of the most beautiful areas of mathematics. But we
>> only have a few weeks left!
>>
>> Bill.
>
>
> -------------------------------------------------------------------------
> 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] Updates 25/7/2008

[<D.C...@wa...>]

Hi,

Yes my first priority is to do the function interface. Unless you'd like
the report done sooner rather than later, I was thinking of perhaps
writing the report the first week after my project when I'm at home to
free up time for research, and that way it won't be rushed at all either.
I suppose it depends how things are going this time next week. With
regards to class field theory, it does look very interesting and I'm going
to look into doing my 4th year project in it.

Thanks,

Daniel Ellam




> Daniel,
>
> That's exceptional progress. I didn't know about any
> of those papers and they are all excellent.
>
> Concentrating on ramified and unramified extensions
> sounds like a good way to spend the remainder of the
> project.
>
> Of course we definitely need the function interface.
> That's the primary goal.
>
> I'd really like to have a longer report with a list of
> everything you have found all in one place. This could
> be put on the FLINT website, and you could take your
> URSS poster from parts of it.
>
> Class field theory is an exceptionally detailed topic
> which could take many months to learn. Not to
> discourage you at all from looking into it; it is one
> of the most beautiful areas of mathematics. But we
> only have a few weeks left!
>
> Bill.

Re: [flint-devel] Updates 25/7/2008

[William H. <ha...@ya...>]

Daniel,

That's exceptional progress. I didn't know about any
of those papers and they are all excellent.

Concentrating on ramified and unramified extensions
sounds like a good way to spend the remainder of the
project. 

Of course we definitely need the function interface.
That's the primary goal.

I'd really like to have a longer report with a list of
everything you have found all in one place. This could
be put on the FLINT website, and you could take your
URSS poster from parts of it.

Class field theory is an exceptionally detailed topic
which could take many months to learn. Not to
discourage you at all from looking into it; it is one
of the most beautiful areas of mathematics. But we
only have a few weeks left!

Bill.

--- D.C...@wa... wrote:

> Hi,
> 
> Another update as to how I've got on this week.
> 
> * Here are some papers I've come across. The first
> two are both recent
> papers which look interesting but are heavy going;
> 
>
http://www.ams.org/mcom/2008-77-262/S0025-5718-07-02027-3/S0025-5718-07-02027-3.pdf
>    -- An algorithm for Computing p-adic
> Polylogarithms
> 
>
http://www.ams.org/mcom/0000-000-00/S0025-5718-08-02091-7/S0025-5718-08-02091-7.pdf
>     --  A p-adic algorithm to compute the Hilbert
> Class Polynomial
> 
> 
> Heres another paper on polynomial factorisation over
> Q_p;
> 
> http://citeseer.ist.psu.edu/291135.html -- Factoring
> Polynomials over
> P-adic Fields
> 
> 
> And heres the paper which relates to what we were
> discussing the other day;
> 
>
http://www.emis.de/journals/JTNB/2006-3/article07.pdf
>   -- Constructing
> class fields over local fields
> 
> 
> * I've been looking at how PARI calculates the
> p-adic logarithm. To
> calculate log(x) when x is real, it uses the formula
> log(x) ~=
> Pi/(2agm(1,4/s) - m*log2    where s = x*2^m. It says
> that p-adic values
> for x are accepted, but I don't know and haven't
> been able to tell yet by
> playing around if this means that the above formula
> is still used or if a
> Taylor series expansion is used or something else,
> which I hope to find
> out.
> 
> 
> 
> * I havent been able to find many algorithms as of
> yet in algebraic number
> theory which make use of p-adics apart from the
> stuff we discussed the
> other day on abelian Galois groups etc., but I could
> just be missing (lots
> of) things so I'll be looking into that again over
> the weekend and next
> week. It seems so far though that apart from basic
> arithmetic, FLINT will
> probably need to be able to deal with actual p-adic
> fields themselves and
> not just their elements when things are built into
> FLINT which use the
> p-adics.
> 
> 
> * I'll probably email you early on next week with
> any progress that I make
> on the function interface, but really I need a good
> list of algorithms
> that use p-adics before I can do this. It looks like
> when we create a
> p-adic we will want to store at least an integer,
> but sometimes maybe
> other things like the valuation.
> 
> 
> * I think I'm going to look a little closer into
> ramified extensions
> during my
> remaining weeks. Class field theory looks
> interesting from what I've been
> reading so I'd like to look into that a little also.
> 
> 
> * When I start coming to the end of my project I
> have to write a short
> report for the URSS . I was also going to write a
> separate report
> detailing everything Ive done during my project for
> yourself, basically
> give an overview of what I've found, put together
> all the papers I've
> found useful and interesting into an organised list,
> put general research
> I've done in there, combine parts of the update
> emails I've been sending
> and include the (now updated) PARI functionality
> list into it as well. Is
> there anything else that I should put into it?
> 
> 
> Thanks,
> 
> Daniel Ellam
> 
> 
> 
>
-------------------------------------------------------------------------
> 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
> 



      

[flint-devel] Updates 25/7/2008

[<D.C...@wa...>]

Hi,

Another update as to how I've got on this week.

* Here are some papers I've come across. The first two are both recent
papers which look interesting but are heavy going;

http://www.ams.org/mcom/2008-77-262/S0025-5718-07-02027-3/S0025-5718-07-02027-3.pdf
   -- An algorithm for Computing p-adic Polylogarithms

http://www.ams.org/mcom/0000-000-00/S0025-5718-08-02091-7/S0025-5718-08-02091-7.pdf
    --  A p-adic algorithm to compute the Hilbert Class Polynomial


Heres another paper on polynomial factorisation over Q_p;

http://citeseer.ist.psu.edu/291135.html -- Factoring Polynomials over
P-adic Fields


And heres the paper which relates to what we were discussing the other day;

http://www.emis.de/journals/JTNB/2006-3/article07.pdf   -- Constructing
class fields over local fields


* I've been looking at how PARI calculates the p-adic logarithm. To
calculate log(x) when x is real, it uses the formula log(x) ~=
Pi/(2agm(1,4/s) - m*log2    where s = x*2^m. It says that p-adic values
for x are accepted, but I don't know and haven't been able to tell yet by
playing around if this means that the above formula is still used or if a
Taylor series expansion is used or something else, which I hope to find
out.



* I havent been able to find many algorithms as of yet in algebraic number
theory which make use of p-adics apart from the stuff we discussed the
other day on abelian Galois groups etc., but I could just be missing (lots
of) things so I'll be looking into that again over the weekend and next
week. It seems so far though that apart from basic arithmetic, FLINT will
probably need to be able to deal with actual p-adic fields themselves and
not just their elements when things are built into FLINT which use the
p-adics.


* I'll probably email you early on next week with any progress that I make
on the function interface, but really I need a good list of algorithms
that use p-adics before I can do this. It looks like when we create a
p-adic we will want to store at least an integer, but sometimes maybe
other things like the valuation.


* I think I'm going to look a little closer into ramified extensions
during my
remaining weeks. Class field theory looks interesting from what I've been
reading so I'd like to look into that a little also.


* When I start coming to the end of my project I have to write a short
report for the URSS . I was also going to write a separate report
detailing everything Ive done during my project for yourself, basically
give an overview of what I've found, put together all the papers I've
found useful and interesting into an organised list, put general research
I've done in there, combine parts of the update emails I've been sending
and include the (now updated) PARI functionality list into it as well. Is
there anything else that I should put into it?


Thanks,

Daniel Ellam

Re: [flint-devel] Additions to long_extras

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

Excellent work!!

I'll try to integrate these functions and test code this afternoon,
and I'll try to put the right gcc on the server tomorrow.

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

[flint-devel] Additions to long_extras

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

Re: [flint-devel] polynomial factoring module

[William H. <ha...@ya...>]

No it's better off in zmod_poly, since it stores
factors in zmod_poly format (presumably).

Bill.

--- Richard Howell-Peak <ric...@gm...> wrote:

> I have written a bunch of code for storing factors
> of a polynomial and
> was thinking about starting to test it properly.
> Would it be better
> off in its own source file or just integrated into
> the zmod_poly
> module?
> 
> -- 
> Richard
> 
>
-------------------------------------------------------------------------
> 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
> 



      

[flint-devel] polynomial factoring module

[Richard Howell-P. <ric...@gm...>]

I have written a bunch of code for storing factors of a polynomial and
was thinking about starting to test it properly. Would it be better
off in its own source file or just integrated into the zmod_poly
module?

-- 
Richard

[flint-devel] Paper on prime proving

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

Hey.

I have found a paper which seems to give quite a bit of detail on prime
proving including a way to speed up Poklington and some other tests:

http://www.jstor.org/stable/2005583?seq=1

Peter

[flint-devel] Berlekamp Partial Sucess

[Richard Howell-P. <ric...@gm...>]

I have an algorithm that will factor polynomials although as far as I can
tell it doesn't really make use of the Berlekamp algebra since it always
computes a trivial basis, so It works in a sense but it is nothing more than
a brute force algorithm in fact it is probably worse than that since it
attempts to compute factors randomly.

-- 
Richard

Re: [flint-devel] Updates 18/7/2008

[William H. <ha...@ya...>]

whoops I was supposed to be in there today wasn't I.
I'll try and catch you tomorrow afternoon.

Bill.

--- D.C...@wa... wrote:

> Hi,
> 
> I should be in the Linux computer room (or the
> Windows room opposite) all
> this week from ~08:00 - 12:00 and again in the
> afternoon ~13:00 - 17:00
> (and I'm quite often in there late into the evening
> if youre still around
> then!), so I can be available whenever is suitable
> for you.
> 
> Thanks,
> 
> Daniel Ellam
> 
> 
> 
> 
> 
> > Hi Daniel,
> >
> 
> >
> > Finally we will start putting together a function
> interface for FLINT,
> > i.e. writing up a list of functions that FLINT
> should implement and
> > planning basically how the data will be passed
> around between them and
> > which algorithms should be used to implement each
> function.
> >
> > We can discuss all this on Monday anyway.
> >
> >
> > Bill.
> >
> >
>
-------------------------------------------------------------------------
> > 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] Updates 18/7/2008

[<D.C...@wa...>]

Hi,

I should be in the Linux computer room (or the Windows room opposite) all
this week from ~08:00 - 12:00 and again in the afternoon ~13:00 - 17:00
(and I'm quite often in there late into the evening if youre still around
then!), so I can be available whenever is suitable for you.

Thanks,

Daniel Ellam





> Hi Daniel,
>

>
> Finally we will start putting together a function interface for FLINT,
> i.e. writing up a list of functions that FLINT should implement and
> planning basically how the data will be passed around between them and
> which algorithms should be used to implement each function.
>
> We can discuss all this on Monday anyway.
>
>
> Bill.
>
> -------------------------------------------------------------------------
> 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] Lucas pseudoprime bug

[William H. <ha...@ya...>]

Peter,

z_mulmod2_precomp will definitely allow the product to
be any size (even way bigger than 64 bits). The only
restriction is the things you are multiplying must be
reduced mod n, which is presumbably the case in your
code.

I don't see any obvious reason for the code below to
fail. That is, the first version will fail, but the
second should not.

Perhaps there is a bug somewhere else.

Have you inspected the output from these computations
to see at which point the error is being made. You can
use pari to do the computations by hand and check that
each line is giving the correct result.

Bill.



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

> Hey
> 
> I think I have found the bug in the lucas
> pseudoprime test I have been
> wrighting. When I was calculating the binary chain I
> was doing operations
> like old.x*old.y-a. As old.x and old.y were both
> about 10^10 giving answer
> about 10^20 which is bigger then 2^64.
> 
> I replaced the line:
> current.x=z_mod2_precomp(old.x*old.y+n-a,n,ninv)
> 
> with
> xy=z_mulmod2_precomp(old.x,old.y,n,ninv);
> xy=z_mod2_precomp(xy-a+n,n,ninv);
> 
> 
> However it still dosn't seam to work. Looking at the
> source for
> z_mulmod2_precomp it appears that on a 64 bit
> computer it just calls
> z_mulmod_precomp which still tries to multiply the
> numbers together which
> won't work. Will I have to use the gmp or fmpz to do
> this?
> 
> 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
> 



      

[flint-devel] Lucas pseudoprime bug

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

Hey

I think I have found the bug in the lucas pseudoprime test I have been
wrighting. When I was calculating the binary chain I was doing operations
like old.x*old.y-a. As old.x and old.y were both about 10^10 giving answer
about 10^20 which is bigger then 2^64.

I replaced the line:
current.x=z_mod2_precomp(old.x*old.y+n-a,n,ninv)

with
xy=z_mulmod2_precomp(old.x,old.y,n,ninv);
xy=z_mod2_precomp(xy-a+n,n,ninv);


However it still dosn't seam to work. Looking at the source for
z_mulmod2_precomp it appears that on a 64 bit computer it just calls
z_mulmod_precomp which still tries to multiply the numbers together which
won't work. Will I have to use the gmp or fmpz to do this?

Peter

[flint-devel] Lucas pseudoprimes

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

Hey.

There appears to be a bug in my Lucas pseudoprime code which means it stops
working at about 10^11. I have tested the combined test for strong and Lucas
pseudoprimes and it took approximately 10 seconds to test 10^7 random odd
numbers which is about 10^-6 seconds per number. Interestingly it found a
number 611812321 which passed both the 2-SPRP test and Lucas test but is
composite. I suspect this is related to the bug in my Lucas pseudoprime code
because according to a paper there are no numbers below 10^15 which should
pass both and be composite. However this is not imposable as the paper used
a different method. They found a delta satisfying (delta/n)=-1 and then
calculated a and b such that a*a-4b=delta. I don't think this number is
worth any money as one prize requires using their method to find a and b and
the other requires that the number is congruent to 2 or 3 mod 5.

Peter

[flint-devel] Square Free

[Richard Howell-P. <ric...@gm...>]

   I have worked out why the square-free algorithm was dropping factors of
x. It was dividing by the gcd of two polynomials to save time but then
didn't multiply by the gcd again when it returned the answer. As it happens
this was often a linear polynomial.
   It now works in two special cases, firstly when the input has first
derivative zero, the second when there is no factor whose derivative is
zero. When I have an input that is a product of these two types of
polynomial the answer is out by a constant factor. I think this is either to
do with the fact that when the recursion is called it might not be a monic
polynomial being input which is required although I haven't checked if this
is possible or not. Alternatively I had trouble with the gcd not always
being monic which I changed but that might be dropping a constant factor at
some point. These are the only things I can think of but I don't see why
they should be a problem so it may well be something else.
   As a quick fix I was thinking of just calling make_monic right at the
end.

-- 
Richard

Re: [flint-devel] Progress

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

Peter,

I found the bug in my z_isprime code. Basically it needs a to be
reduced mod n when you are doing an a-SRPR test. But when using a
31-SRPR test on n = 31, this isn't the case. So I fixed it by adding a
2-SRPR test for numbers below 2047. This means the test for small
primes can be taken out.

I've made these changes and committed them to svn. Can you check that
this still works for you.

Bill.

2008/7/16 Bill Hart <goo...@go...>:
> Excellent work. The figures you are giving look quite promising.
>
> I'll commit the changes you've made to pocklington to the FLINT repository soon.
>
> Currently I'm working on some code for a collaborator which computes
> theta functions (essentially power series like Sum q^{ax^2+bx+c} for
> various values of a,, b, c). As soon as I've got somewhere with it,
> I'll put some more time into the primality testing code.
>
> Bill.
>
> 2008/7/16 Peter Shrimpton <ps...@gm...>:
>> Hello.
>>
>> I think I have pretty much finished the pocklington test. The partial
>> factorization is done by adjusting the code for the z_factor function that
>> was already there. This seams to be pretty quick. Also I have combined it
>> with the SPRP test already in flint and the results seam quite promising. I
>> have checked the numbers between 10^16 and 10^16+10^9 and the combined SPRP
>> and Pocklington tese took on average about 2*10^-6 seconds per number to
>> check with 100 iterations of the pocklington test. The number of iterations
>> in the pocklington seams to affect the number of potential SPRP's we get
>> quite a bit:
>>
>> number of iterations           number of primes proved        number of
>> 2-SPRP's       number of 2-SPRP's that we couldn't prove are prime
>> 200
>> 1033994                                   1033994                       0
>> 130
>> 1033986                                   1033994                       8
>> 120
>> 1033982                                   1033994                       12
>> 100
>> 1033938                                   1033994                       56
>> 90
>> 1033897                                   1033994                       97
>>
>> As the number of composite SPRP's found was 0 in this sample the amount of
>> time taken to execute the code was affected very little by the number of
>> iterations of the Pocklington test. This is because quite often the first
>> few numbers are enough to find a b such that gcd(b^((n-1)/p),n). However I
>> am not sure if this trend will continue. The code for this is attached.
>>
>>
>> I am now working on the Lucas psudoprime test. I have implemented a slow
>> version that works up to about 100 but then the numbers in the lucas chain
>> get too big. There is an algorithm in the book "Prime Numbers. A
>> Computational perspective" (one of the authors is in fact Carl Pomerance)
>> which keeps everything reduced mod n and should be quite quick but I am
>> having difficulty in implementing it.
>>
>> 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] Updates 18/7/2008

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

Hi Daniel,

2008/7/18  <D.C...@wa...>:
> Hi,
>
> Another update of how I've got on over the last week.
>
>
> * I've been looking through the Magma website. I came across the following
> paper which is interesting and may be of use at a later date if you
> haven't already seen it:
>
>
> http://citeseer.ist.psu.edu/621833.html -- A Fast Algorithm for Polynomial
> Factorisation over Q_p
>

No I haven't seen that. Thanks for the link. If you have any more like
that, please let me know so I can add them to the website.

>
> It turns out that PARI now probably uses this algorithm. There's a few
> similar papers I've come across on factorising polynomials over p-adic
> fields but I haven't had a proper look at them yet.
>
>
> * A quick thought on how, if we're to store elements of Z_p as integers,
> then how we should consider elements of Q_p? I don't see any reason why we
> can't write x = (p^k)*u + O(p^n) where k is the p-adic valuation of x and
> u is a p-adic unit in Z_p and perform arithmetic on this representation -
> it also seems this is how Magma treats elements of Q_p.
>

It seems logical to do what you suggest. This is similar to how we
store polynomials over the rationals. We store the polynomials as an
element of Z[x] and an integer representing the denominator.

>
> * I've written (and attached) a word document outlining p-adic
> functionality in PARI. I haven't quite finished it yet, but hopefully it
> will be of some use to you. If I make any alterations (which I most likely
> will) I can send it through again.
>

This is looking good so far. You might like to add a section for basic
p-adic arithmetic, e.g. addition, subtraction, multiplication,
division, powering, square root, n-th root, etc.

PARI also has recursive data types, e.g. it will deal with matrices
over the p-adics, and polynomials with matrices over the p-adics as
coefficients, and so on. It just uses generic algorithms for all this
stuff though, nothing specific to the p-adics.

I think you are probably right about all those transcendental
functions. It might just use the power series expansion of the
transcendental function and basic p-adic arithmetic. But the note on
the fact that PARI seems to know something about the radius of
convergence is interesting.

>
> * What direction do you think I should be going in now? I haven't seen you
> for a little while so if you'd like me to drop in some day that won't be a
> problem.
>

It might be a good idea to meet up with you on Monday if you are
around. I see the other guys from time to time in the computer room on
the ground floor of mathematics. Do you want to go in there after
lunch some time on Monday and I'll wander in there some time.

>
> * I have a quick question on the duration of my project. I thought that it
> was to be 6 weeks so I booked 6 weeks of accommodation beforehand, but I
> think I remember you saying that it was 8 weeks during our first meeting.
> It doesn't matter if it is to be 8 weeks but I'll have to extend my
> accommodation if I'm to be on campus.
>

Yep, according to the application form we pay you for six weeks.
There's definitely no need to hang around Warwick after that. The same
is true for Richard HP. I only remembered that Peter has longer. In
fact Peter has 8 weeks and you guys have 6.

That does mean we need to get a move on though. We need to get a plan
of action together for FLINT. In particular we need to work out a
function interface.

I think once you are done with the basic functionality that Pari has,
the next step should be to find other algorithms that use p-adics. You
might need to use mathscinet for that. In particular we need to look
at algorithms in algebraic number theory. For example do any of the
algorithms for ideal arithmetic, computing the class number or the
unit group use p-adics. What about algortithms for computing
decomposition groups, inertia groups. What about algorithms for
determining which primes split in a number field. Maybe they do, maybe
they don't, I don't know.

Certainly there are algorithms that use v-adic arithemetic, where v is
an ideal in an algebraic number field, though that doesn't interest me
quite as much at this point.

Is there any way to tell from the source code of pari which other
algorithms in pari use p-adic arithmetic. Basically we need a list of
higher level algorithms that use p-adic arithmetic somewhere so we can
start planning what our p-adics need to be able to do.

Finally we will start putting together a function interface for FLINT,
i.e. writing up a list of functions that FLINT should implement and
planning basically how the data will be passed around between them and
which algorithms should be used to implement each function.

We can discuss all this on Monday anyway.

Thanks for all your hard work. I can see you've put quite a bit of
work into the list of Pari functions, and it will be very helpful.

Bill.

[flint-devel] Updates 18/7/2008

[<D.C...@wa...>]

Hi,

Another update of how I've got on over the last week.


* I've been looking through the Magma website. I came across the following
paper which is interesting and may be of use at a later date if you
haven't already seen it:


http://citeseer.ist.psu.edu/621833.html -- A Fast Algorithm for Polynomial
Factorisation over Q_p


It turns out that PARI now probably uses this algorithm. There's a few
similar papers I've come across on factorising polynomials over p-adic
fields but I haven't had a proper look at them yet.


* A quick thought on how, if we're to store elements of Z_p as integers,
then how we should consider elements of Q_p? I don't see any reason why we
can't write x = (p^k)*u + O(p^n) where k is the p-adic valuation of x and
u is a p-adic unit in Z_p and perform arithmetic on this representation -
it also seems this is how Magma treats elements of Q_p.


* I've written (and attached) a word document outlining p-adic
functionality in PARI. I haven't quite finished it yet, but hopefully it
will be of some use to you. If I make any alterations (which I most likely
will) I can send it through again.


* What direction do you think I should be going in now? I haven't seen you
for a little while so if you'd like me to drop in some day that won't be a
problem.


* I have a quick question on the duration of my project. I thought that it
was to be 6 weeks so I booked 6 weeks of accommodation beforehand, but I
think I remember you saying that it was 8 weeks during our first meeting.
It doesn't matter if it is to be 8 weeks but I'll have to extend my
accommodation if I'm to be on campus.


Thanks,

Daniel Ellam

Re: [flint-devel] improved differentiation function

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

Hi Richard,

Actually, you assume the user passes you an initialised polynomials,
but that doesn't mean memory is allocated for it by then, it just
means the zmod_poly_t struct has been initialised.

You want to call zmod_poly_fit_length somewhere to allocate the
correct amount of memory (if necessary) for this already initialised
polynomial. Check any of the existing functions in zmod_poly without
leading underscores to see how this is done.

I think David is also right about j not necessarily being reduced mod
p. You need to reduce it mod p (perhaps as I described yesterday)
before multiplying by it.

By the way, yesterday I sent an email to the list about how to
implement the derivative function and also asked about whether you had
written some test code. I didn't check if the mail got to the list.
Sometimes there seems to be a delay for no apparent reason.

Bill.

2008/7/16 Richard Howell-Peak <ric...@gm...>:
> Come to think of it, is the initialisation done prior to calling the
> function? If it was then It'd be up to the user to pre-allocate memory.
>
> --
> Richard
> -------------------------------------------------------------------------
> 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] improved differentiation function

[David H. <dmh...@ma...>]

On Jul 16, 2008, at 11:14 AM, Richard Howell-Peak wrote:

> Come to think of it, is the initialisation done prior to calling  
> the function? If it was then It'd be up to the user to pre-allocate  
> memory.

I don't really understand the semantics of the function you are  
trying to write, so I should probably just keep my mouth shut.  
Perhaps Bill will have an opinion.

david

[flint-devel] improved differentiation function

[Richard Howell-P. <ric...@gm...>]

Come to think of it, is the initialisation done prior to calling the
function? If it was then It'd be up to the user to pre-allocate memory.

-- 
Richard