Pemeriksa Primalitas Suatu Bilangan Menggunakan Pemrograman Dinamis

Article Sidebar

pdf
Published: Sep 22, 2025
DOI: https://doi.org/10.24912/computatio.v9i1.34534
Keywords:
pemeriksaan primalitas, dynamic programming, memoization, trial division, bilangan prima
Dimensions
Altmetrics
Statistics
Read Counter : 14
Download : 8
Crossmark/ Data Version

Main Article Content

Teady Matius Surya Mulyana
Program Studi Informatika, Fakultas Teknologi Dan Desain, Universitas Bunda Mulia
Agustinus Frits Wijaya
Program Studi Informatika, Fakultas Teknologi Dan Desain, Universitas Bunda Mulia
Jusia Amanda Ginting
Program Studi Informatika, Fakultas Teknologi Dan Desain, Universitas Bunda Mulia
Francka Sakti Lee
Program Studi Sistem Informasi, Fakultas Teknologi Dan Desain, Universitas Bunda Mulia
Giovanni Alvaro
Program Studi Informatika, Fakultas Teknologi Dan Desain, Universitas Bunda Mulia

Abstract

Bilangan prima merupakan bilangan yang sangat penting dalam berbagai bidang komputasi. Sebagai bilangan yang tidak habis terbagi bilangan manapun selain 1 dan bilangan itu sendiri, sehingga sering dimanfaatkan pada pengkodean yang memerlukan bilangan unik. Salah satu masalah yang timbul sehubungna dengan keperluan bilangan prima ini adalah untuk mendapatkan suatu bilangan unik yang prima memerlukan pengujian primalitas bilangan. Pemeriksaan primalitas dapat mengintegrasikan prinsip Dynamic Programming (DP) melalui teknik memoization dan penyimpanan data persisten. Proses ini akan memanfaatkan tabel bilangan prima yang tersimpan sehingga dapat digunakan Kembali pada pengujian bilangan primalitas bilangan berikutnya. Pendekatan trial division, memungkinkan sistem untuk secara menyimpan dan menggunakan kembali hasil komputasi sebelumnya, sehingga mempercepat proses pemeriksaan bilangan prima di masa mendatang. Uji coba pembagian dioptimalkan dengan batas akar kuadrat. Melalui serangkaian pengujian kinerja, hasil menunjukkan peningkatan efisiensi yang signifikan. Waktu eksekusi berkurang drastis ketika bilangan yang diperiksa sudah ada dalam tabel memoized atau berada dalam jangkauan bilangan prima yang telah dibangun sebelumnya. Namun, penelitian ini juga mengidentifikasi keterbatasan kinerja yang substansial. Ketika program dihadapkan pada kebutuhan untuk memperluas tabel ke rentang bilangan yang sangat besar,  algoritma uji coba pembagian sekuensial yang digunakan untuk perluasan tabel menjadi tidak optimal dan memakan waktu komputasi yang sangat lama.

Article Details

Issue
Vol. 9 No. 1 (2025): Computatio: Journal of Computer Science and Information Systems
Section
Articles
Creative Commons License

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

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

References

[1] P. Doroszlai and H. Keller, “The Number of Primes,” Advances in Pure Mathematics, vol. 12, no. 02, pp. 81–95, 2022, doi: 10.4236/apm.2022.122008.

[2] J. Saputra and J. A. Ginting, “Penyembunyian Data Menggunakan Metode Overwriting Metadata,” JIKO (Jurnal Informatika dan Komputer), vol. 7, no. 2, p. 296, Sep. 2023, doi: 10.26798/jiko.v7i2.692.

[3] J. A. Ginting and I. G. G. Ngurah Suryantara, “PENGUJIAN KERENTANAN SISTEM DENGAN MENGGUNAKAN METODE PENETRATION TESTING DI UNIVERSITAS XYZ,” Infotech: Journal of Technology Information, vol. 7, no. 1, pp. 41–46, Jun. 2021, doi: 10.37365/jti.v7i1.105.

[4] T. M. S. Mulyana, “PENGGUNAAN NILAI SKALA KEABUAN DARI CITRA WATERMARK SEBAGAI SEBAGAI CETAK BIRU DARI VISIBLE WATERMARKING Teady,” Seminar Nasional Informatika, vol. 2013, no. semnasIF, pp. 23–30, 2013, [Online]. Available: http://jurnal.upnyk.ac.id/index.php/semnasif/article/view/976

[5] M. S. Dairi, M. Setiani Asih, and corespondent author, “Implementasi Algoritma Kriptografi RSA Dalam Aplikasi Sistem Informasi Perpustakaaan Implementation Of RSA Cryptographic Algorithms in Library Information System Applications,” 2022. [Online]. Available: https://jurnal.unity-academy.sch.id/index.php/jirsi/index98

[6] N. P. Utomo, N. Fahriani, and M. Amirul, “Implementasi Kriptografi Dengan Metode RSA Untuk Keamanan Data Pada Email Berbasis PHP,” 2023.

[7] J. Maghfiroh, T. Turmudi, and E. Susanti, “Pengamanan Pesan Menggunakan Algoritma One Time Pad dengan Linear Congruential Generator sebagai Pembangkit Kunci,” Jurnal Riset Mahasiswa Matematika, vol. 2, no. 3, pp. 122–131, Mar. 2023, doi: 10.18860/jrmm.v2i3.16770.

[8] H. Gunawan, A. Setia Budi, and R. Primananda, “Penerapan Algoritma Diffie Hellman Key Exchange dalam Komunikasi Data Antarnode pada Wireless Sensor Network,” 2022. [Online]. Available: http://j-ptiik.ub.ac.id

[9] M. Pundir, A. Kumar, and S. Choudhary, “Efficient Diffie Hellman Two Round Secret Key Agreement Protocol,” in 2023 1st International Conference on Innovations in High Speed Communication and Signal Processing (IHCSP), 2023, pp. 7–10. doi: 10.1109/IHCSP56702.2023.10127113.

[10] G. A. Onggo, D. E. Herwindiati, and J. Hendryli, “Analisis Security Voice Authentication pada Sistem Login 2-FA,” Computatio : Journal of Computer Science and Information Systems, vol. 5, no. 1, p. 1, Sep. 2021, doi: 10.24912/computatio.v1i1.10915.

[11] J. Fernandes Andry et al., “KEBIJAKAN KEAMANAN TEKNOLOGI INFORMASI PADA PERANGKAT KERAS DI PERUSAHAAN DISTRIBUTOR SEPATU IT Security Policy of Hardware at A Shoe Distributor Company.” [Online]. Available: http://journal.ubm.ac.id/

[12] A. Milson, D. E. Herwindiati, and N. J. Perdana, “Penerapan Klasifikasi Suara Sebagai Autentikasi Keamanan Sistem Login Menggunakan Gaussian Mixture Models,” Computatio : Journal of Computer Science and Information Systems, vol. 8, no. 1, pp. 104–109, Apr. 2024, doi: 10.24912/computatio.v8i1.16229.

[13] F. An, J. Ye, and Z. Yang, “Data Transmission Error Detection and Correction with Cyclic Redundancy Check and Polar Code Integration with Successive Cancellation Decoding Algorithm,” Applied Sciences, vol. 15, no. 3, p. 1124, Jan. 2025, doi: 10.3390/app15031124.

[14] A. Fanani, “PENGACAKAN SOAL PADA SISTEM COMPUTER BASED TEST (CBT) DENGAN METODE LINEAR CONGRUENTIAL GENERATOR (LCG) DI SMA NEGERI JOGOROTO,” SUBMIT (Jurnal Ilmiah Teknologi Informasi dan Sains), vol. I No. I, pp. 50–56, 2021, [Online]. Available: http://ejurnal.unim.ac.id/index.php/submit

[15] N. Khairina, “The Comparison of Methods for Generating Prime Numbers between The Sieve of Eratosthenes, Atkins, and Sundaram,” SinkrOn, vol. 3, no. 2, p. 293, Apr. 2019, doi: 10.33395/sinkron.v3i2.10129.

[16] K. Banerjee, S. Nath Mandal, and S. Kumar Das, “Improved Trial Division Technique for Primality Checking in RSA Algorithm,” International Journal of Computer Network and Information Security, vol. 5, no. 9, pp. 51–57, Jul. 2013, doi: 10.5815/ijcnis.2013.09.07.

[17] A. Elhakeem Abd Elnaby and A. H. El-Baz, “A new explicit algorithmic method for generating the prime numbers in order,” Egyptian Informatics Journal, vol. 22, no. 1, pp. 101–104, Mar. 2021, doi: 10.1016/j.eij.2020.05.002.

[18] I. G. A. W. Wardhana and A. Abdurahim, “SUBMODUL PRIMA, PRIMA LEMAH DAN HAMPIR PRIMA DARI MODUL MATRIKS BILANGAN BULAT MODULO,” Jurnal Riset dan Aplikasi Matematika (JRAM), vol. 8, no. 2, pp. 136–141, Oct. 2024, doi: 10.26740/jram.v8n2.p136-141.

[19] I. D. Shkredov, I. E. Shparlinski, and A. Zaharescu, “On the distribution of modular square roots of primes,” Mathematische Zeitschrift, vol. 306, no. 3, p. 43, Mar. 2024, doi: 10.1007/s00209-024-03436-5.

[20] H.-L. Li, S.-C. Fang, and W. Kuo, “The Periodic Table of Primes,” Advances in Pure Mathematics, vol. 14, no. 05, pp. 394–419, 2024, doi: 10.4236/apm.2024.145023.

[21] A. Tarek, H. Elsayed, M. Rashad, M. Hassan, and P. el kafrawy, “Dynamic Programming Applications: A Suvrvey,” in 2020 2nd Novel Intelligent and Leading Emerging Sciences Conference (NILES), 2020, pp. 380–385. doi: 10.1109/NILES50944.2020.9257968.

[22] N. Islamov, Dynamic programming: Explore the concepts of dynamic programming, memoization, and tabulation, and apply these techniques to optimize solutions to problems like the knapsack problem, edit distance, and longest common subsequence. 2023. doi: 10.13140/RG.2.2.29569.43369.

[23] D. Llorens and J. M. Vilar, “Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms,” Softw Pract Exp, vol. 50, no. 12, pp. 2193–2211, Dec. 2020, doi: 10.1002/spe.2887.

[24] S. S. Skiena, “Dynamic Programming,” in The Algorithm Design Manual, S. S. Skiena, Ed., Cham: Springer International Publishing, 2020, pp. 307–353. doi: 10.1007/978-3-030-54256-6_10.

[25] M. ERWIG and P. KUMAR, “Explainable dynamic programming,” Journal of Functional Programming, vol. 31, p. e10, May 2021, doi: 10.1017/S0956796821000083.

[26] T. Guo, “Using Larger Wheel to Accelerate the Trial Division Algorithm in Integer Factorization Method ToolBox,” in 2024 7th International Conference on Computer Information Science and Application Technology (CISAT), 2024, pp. 136–139. doi: 10.1109/CISAT62382.2024.10695357.

[27] I. D. Shkredov, I. E. Shparlinski, and A. Zaharescu, “On the distribution of modular square roots of primes,” Mathematische Zeitschrift, vol. 306, no. 3, Mar. 2024, doi: 10.1007/s00209-024-03436-5.

[28] F. Yuwono, V. Noviantri, A. A. S. Gunawan, and H. Ngarianto, “ANALISIS NUMERIK MODEL SEIQRS-V UNTUK PENYEBARAN VIRUS PADA JARINGAN KOMPUTER,” Computatio : Journal of Computer Science and Information Systems, vol. 2, no. 2, p. 126, Oct. 2018, doi: 10.24912/computatio.v2i2.2347.