Primality testing in Flint: the APR-CL algorithm

[Jasdeep Singh]

I have gone through the this project Idea and I believe I can implement it if provided with a little help from mentors.I had number theory as my high school subject and I am currently pursuing B.tech 2ND year.Therefore different implementations of primality test have always fascinated me.I have solved various competitive problems regarding primality tests on spoj .I have gone through the paper

http://www.cs.toronto.edu/~vinodv/COURSES/MAT302-S13/pomerance.pdf  and I believe I can implement this algorithm.

So what do I have to do in order to get this gsoc project do you guys have a competency test and could I talk to the mentors regarding this project.

-Thank you

[Bill Hart]

Hi Jasdeep,

That paper is actually just some prereading. It doesn't contain the APR-CL algorithm, which is actually very involved, though it does mention in passing the test of Adleman-Pomerance-Rumely, which was a (slower) precursor.

This will be the hardest of the GSoC projects to get into this year, since we will require two competency tests, one on the maths side and one on the computing side.

1) A written (mathematical) description of the p+1 primality testing algorithm described *in terms of finite fields*.

2) A piece of code to demonstrate your competence in writing C code and working with the flint project.

Because this is primality *proving*, the code will need to be pretty close to faultless to be accepted.

Number (1) should be a short document written by the student demonstrating understanding of that much simpler algorithm. One of the mentors will send out a document on finite fields to read beforehand, which should make this easier for people who haven't studied them. We'll get prospective students to email (1) privately to one of the mentors to ensure originality.

Bear in mind that participating mentoring organisations aren't announced by Google until 2nd March, and I really and truly don't know until then whether Lmonade will be accepted. So there is no point in doing (1) before then, unless you have an independent interest in this algorithm for some reason.

If you want to contribute a patch to flint in the mean time to get started on (2), that would have independent usefulness even if Lmonade is not accepted. We always welcome Open Source contributions to flint. 

But that is entirely up to you. You might prefer to wait until March 2nd before starting (2) as well.

Best Wishes,

Bill.

--

---
You received this message because you are subscribed to the Google Groups "flint-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jasdeep Singh]

Thank you for your response Bill Hart.
As I said primality tests fascinate me and I would like to contribute regardless lmonade gets accepted or not.I will try to implement p+1 primality  testing algorithm.

[Bill Hart]

We already have an implementation of the p+1 algorithm, but by all means implement that as a competence test or warmup.

Bill.

On 25 February 2015 at 14:53, Jasdeep Singh <singhja...@gmail.com> wrote:

Thank you for your response Bill Hart.
As I said primality tests fascinate me and I would like to contribute regardless lmonade gets accepted or not.I will try to implement p+1 primality  testing algorithm.

--