AKS Primality Test
Opened this issue · 5 comments
I've examined some of the literature on this and while the algorithm is simple enough, a number of steps require some fast arithmetic operations. This is going to require some work to get these operations up and running when they are needed. For now I plan to just do a few of the steps that don't require these algorithms, and then implement the algorithms when they are necessary.
Just a warning, that there is a huge difference between checking
congruences in a polynomial ring vs. checking congruences over Z/mZ, and
the polynomial version is needed for AKS.
On Fri, Oct 3, 2014 at 12:20 AM, Aaron W. Hsu notifications@github.com
wrote:
I've examined some of the literature on this and while the algorithm is
simple enough, a number of steps require some fast arithmetic operations.
This is going to require some work to get these operations up and running
when they are needed. For now I plan to just do a few of the steps that
don't require these algorithms, and then implement the algorithms when they
are necessary.—
Reply to this email directly or view it on GitHub
#28 (comment).
I'm using the AKS algorithm given by https://math.dartmouth.edu/~carlp/aks041411.pdf, which is a modified algorithm from the original. I haven't specifically examined the congruence checking, but the algorithms in the document there seem straightforward enough.
It looks to me like the congruence checking is similar. I'm sure you are
proficient with the programming, but if you have questions about the
mathematics, do not hesitate to ask.
-Erik
On Fri, Oct 3, 2014 at 6:55 PM, Aaron W. Hsu notifications@github.com
wrote:
I'm using the AKS algorithm given by
https://math.dartmouth.edu/~carlp/aks041411.pdf, which is a modified
algorithm from the original. I haven't specifically examined the congruence
checking, but the algorithms in the document there seem straightforward
enough.—
Reply to this email directly or view it on GitHub
#28 (comment).
Thanks, I will probably have some questions about the math soon, as I'm running into concepts that I'm quite rusty at.