A Load-Balanced Parallelization of AKS Algorithm

Ardhi Wiratama Baskara Yudha, Reza Pulungan


The best known deterministic polynomial-time algorithm for primality testing right now is due to Agrawal, Kayal, and Saxena. This algorithm has a time complexity O(log^{15/2}(n)). Although this algorithm is polynomial, its reliance on the congruence of large polynomials results in enormous computational requirement. In this paper, we propose a parallelization technique for this algorithm based on message-passing parallelism together with four workload-distribution strategies. We perform a series of experiments on an implementation of this algorithm in a high-performance computing system consisting of 15 nodes, each with 4 CPU cores. The experiments indicate that our proposed parallelization technique introduce a significant speedup on existing implementations. Furthermore, the dynamic workload-distribution strategy performs better than the others. Overall, the experiments show that the parallelization obtains up to 36 times speedup.



primality testing; AKS algorithm; parallelization; load balancing; high-performance computing;

Full Text:


DOI: http://dx.doi.org/10.12928/telkomnika.v15i4.6049

Article Metrics

Abstract view : 125 times
PDF - 87 times


  • There are currently no refbacks.

Copyright (c) 2018 Universitas Ahmad Dahlan

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus, 9th Floor, LPPI Room
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120 ext. 4902, Fax: +62 274 564604

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.