Article Per Year (5 Year)
p-Index From 2020 - 2025
0
P-Index
This Author published in this journals
All Journal TELKOMNIKA (Telecommunication Computing Electronics and Control)
Ardhi Wiratama Baskara Yudha
Universitas Gadjah Mada, Indonesia
Computer Science & IT

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
A Load-Balanced Parallelization of AKS Algorithm Ardhi Wiratama Baskara Yudha; Reza Pulungan
TELKOMNIKA (Telecommunication Computing Electronics and Control) Vol 15, No 4: December 2017
Publisher : Universitas Ahmad Dahlan

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.12928/telkomnika.v15i4.6049

Abstract

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. 
Co-Authors MHD. Reza M.I. Pulungan