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