On Sat, Apr 6, 2013 at 11:05 AM, Sushant Hiray <hiraysush...@gmail.com>wrote:
> Dear All, > > I am Sushant a sophomore from Indian Institute of Technology, Bombay > pursuing Computer Science. > I am very much interested in number theory and my trysts with number > theory goes way back since I was in school. I have participated in Maths > Olympiads and number theory has always been my strong point. Here in IIT I > have already taken an introductory course and planning to take some more > advanced courses in number theory. > > Having said that I was taking a look at the number theory module of sympy. > Obviously starting from the primality tests! > I saw that sympy has implemented Miller-Rabin strong pseudo-prime test for > primality checking! > Miller-Rabin returns False if n is definitely composite, True if n is > probably prime, with a probability greater than 3/4 , as mentioned in the > comments. > Well so we can surely do better than this! > Have you looked at what nzmath has for this? It is also BSD licensed and written in pure python. > > I tried finding out a better probabilistic algorithm and found out about > Baillie-PSW. > Baillie-PSW is just a combination of (as I understand it) a single > Rabin-Miller-Test followed by a strong Lucas-Selfridge test. > > Pros of using Baillie-PSW : [1] > It has been determined that no psuedo prime exists for N < 10^15 which is > in itself quite amazing. > O((log n)^3) bit operations : Not exactly a pro though Miller Rabin offers > the same. > > Apart from Baillie-PSW we can surely keep our sights on deterministic > algorithms. Ain't we? > So then there's is our AKS algorithm! (Agarwal-Kayal-Saxena Primality > Test) [2] > There's nothing much to say about AKS. It is deterministic and has O((log > n)^6). > It is much better for areas like cryptography where we need to determine > exact primes which are way bigger than our normal numbers. > Though I haven't heard of any library implementing AKS, probably because > of its order, but why not sympy take a lead! :) > > Or even much better, we can extend the current Miller-Rabin to Baillie-PSW > and also provide an alternate usage of AKS, so people interested in > deterministic answers can use the AKS version. > > I was thinking of creating a patch in improving the current primality test. > I would surely love to hear your views about it. > Possibly some implementation issues too. > > Regards, > Sushant > > [1] http://www.trnicely.net/misc/bpsw.html > [2] http://en.wikipedia.org/wiki/AKS_primality_test > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy?hl=en-US. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy?hl=en-US. For more options, visit https://groups.google.com/groups/opt_out.
