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?

You might want to rephrase your question to: "Has anyone tried implementing the AKS test?" — Jacob, Jun 27 '11 at 18:48

score 5 · Answer 1 · answered Jun 27 '11 at 19:42

5

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.

answered Jun 27 '11 at 19:42

John Clements

16,895
3
37
52

3

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. – pg1989 Jun 27 '11 at 20:51
1

:D Thats a good answer. Excuse me, i'm new in this kind of things, be tolerant @pg1989. – Carlochess Jun 28 '11 at 03:13
1

No worries. Everyone starts from 0. – pg1989 Jun 28 '11 at 12:35

score 2 · Answer 2 · answered Jun 27 '11 at 18:47

2

Of course it can. Google helps here.

C++ implementations

answered Jun 27 '11 at 18:47

Peter Alexander

53,344
14
119
168

score 1 · Answer 3 · edited Mar 11 '16 at 08:40

1

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

edited Mar 11 '16 at 08:40

jellies

639
1
5
17

answered Jun 27 '11 at 18:47

Mikola

9,176
2
34
41

Implementation of AKS primality test in Scheme or C++

3 Answers3