search

Co-dfns / mystika

High-end Cryptographic Library
GNU Affero General Public License v3.0
43 stars 26 forks source link

AKS Primality Test #28

Open arcfide opened 9 years ago

arcfide commented 9 years ago

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.

Tikhon03 commented 9 years ago

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 https://github.com/arcfide/mystika/issues/28#issuecomment-57710633.

arcfide commented 9 years ago

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.

Tikhon03 commented 9 years ago

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 https://github.com/arcfide/mystika/issues/28#issuecomment-57815416.

arcfide commented 9 years ago

Thanks, I will probably have some questions about the math soon, as I'm running into concepts that I'm quite rusty at.