Implementation of AKS primality test in Scheme or C++

Question

I was reading about the prime test algorithm and found the AKS primality test. Could this algorithm be implemented in Scheme or in C++?

Has anyone tried implementing the AKS test?

Suberin

google, first hit with "AKS c++" – Avera

You might want to rephrase your question to: "Has anyone tried implementing the AKS test?" – Villalpando

Answer 1

Scheme and C++ (and Racket and Pascal and Logo and Modula-3 and Postscript) are all Turing equivalent, meaning that they can all be used to simulate each other, and hence that they can all compute the same things.

So: yes, you can implement this in Scheme. Or any other Turing-complete language.

Vladikavkaz

Thank you. It's so frustrating when people ask if X can be implemented in language Y without realizing that the answer is always yes for any Turing-complete language. – Fokos

:D Thats a good answer. Excuse me, i'm new in this kind of things, be tolerant @pg1989. – Suberin

No worries. Everyone starts from 0. – Fokos

Answer 2

Of course it can. Google helps here.

C++ implementations

Gorgonzola

Answer 3

Yep, here is some documentation: http://ece.gmu.edu%2Fcourses%2FECE746%2Fproject%2FF06_Project_resources%2FSalembier_Southerington_AKS.pdf

Alack