Sejarah singkat obsesi kita dengan bilangan prima – dan ke mana perburuan berikutnya

Pecahan tulang halus yang terukir dengan tanda tidak teratur yang berasal dari 20.000 tahun yang telah membingungkan para arkeolog sampai mereka melihat sesuatu yang unik – etsa, garis seperti tanda penghitungan, mungkin telah mewakili bilangan prima. Demikian pula, tablet tanah liat dari 1800 SM yang tertulis dengan nomor Babilonia menggambarkan sistem angka yang dibangun di atas bilangan prima.

Sebagai tulang Ishango, tablet Plimpton 322 dan artefak lainnya di seluruh tampilan sejarah, bilangan prima telah memesona dan memikat orang sepanjang sejarah. Saat ini, bilangan prima dan sifat -sifatnya dipelajari dalam teori angka, cabang matematika dan bidang penelitian aktif saat ini.

ADVERTISEMENT

SCROLL TO RESUME CONTENT

Sejarah bilangan prima

Secara informal, angka penghitungan positif yang lebih besar dari satu adalah prima jika jumlah titik itu hanya dapat diatur ke dalam array persegi panjang dengan satu kolom atau satu baris. Sebagai contoh, 11 adalah bilangan prima karena 11 titik membentuk hanya array persegi panjang ukuran 1 dengan 11 dan 11 dengan 1. Sebaliknya, 12 tidak prima karena Anda dapat menggunakan 12 titik untuk membuat array 3 dengan 4 titik, dengan beberapa baris dan beberapa kolom. Buku teks matematika mendefinisikan bilangan prima sebagai bilangan bulat lebih besar dari yang hanya pembagi positif hanya 1 dan dirinya sendiri.

Sejarawan matematika Peter S. Rudman menyarankan bahwa ahli matematika Yunani kemungkinan adalah yang pertama memahami konsep bilangan prima, sekitar 500 SM

Sekitar 300 SM, ahli matematika Yunani dan ahli logika Euler membuktikan bahwa ada banyak bilangan prima. Euler mulai dengan mengasumsikan bahwa ada sejumlah bilangan prima yang terbatas. Kemudian dia datang dengan prima yang tidak ada dalam daftar asli untuk membuat kontradiksi. Karena prinsip dasar matematika secara logis konsisten tanpa kontradiksi, Euler kemudian menyimpulkan bahwa asumsi aslinya harus salah. Jadi, ada banyak bilangan prima tak terhingga.

Argumen tersebut menetapkan adanya banyak bilangan prima yang tak terbatas, namun itu tidak terlalu konstruktif. Euler tidak memiliki metode yang efisien untuk mendaftar semua bilangan prima dalam daftar naik.

Pada Abad Pertengahan, ahli matematika Arab memajukan teori bilangan prima orang Yunani, yang disebut sebagai bilangan hasam selama waktu ini. Matematikawan Persia Kamal al-Din al-Farisi merumuskan teorema mendasar aritmatika, yang menyatakan bahwa bilangan bulat positif yang lebih besar dari yang dapat diekspresikan secara unik sebagai produk bilangan prima.

Dari pandangan ini, bilangan prima adalah blok bangunan dasar untuk membangun bilangan bulat positif menggunakan perkalian – mirip dengan atom yang digabungkan untuk membuat molekul dalam kimia.

Bilangan prima dapat diurutkan menjadi berbagai jenis. Pada 1202, Leonardo Fibonacci diperkenalkan dalam bukunya “Liber Abaci: Book of Calculation” Jumlah Prime Formulir (2^P – 1) Di mana P juga prima.

Hari ini, bilangan prima dalam bentuk ini disebut primes Mersenne setelah bhikkhu Prancis Marin Mersenne. Banyak bilangan prima terbesar yang diketahui mengikuti format ini.

Beberapa ahli matematika awal percaya bahwa sejumlah formulir (2^P – 1) adalah yang utama setiap kali P adalah prima. Tetapi pada 1536, ahli matematika Hudalricus Regius memperhatikan bahwa 11 adalah prima tetapi tidak (2¹¹ – 1), yang sama dengan 2047. Angka 2047 dapat dinyatakan sebagai 11 kali 89, menyangkal dugaan.

Meskipun tidak selalu benar, ahli teori angka menyadari bahwa (2^P – 1) Pintasan sering menghasilkan bilangan prima dan memberikan cara sistematis untuk mencari bilangan prima besar.

Pencarian bilangan prima besar

Angka (2^P – 1) jauh lebih besar relatif terhadap nilai P dan memberikan peluang untuk mengidentifikasi bilangan prima besar.

Saat angka (2^P – 1) menjadi cukup besar, jauh lebih sulit untuk memeriksa apakah (2^P – 1) adalah prima – yaitu, jika (2^P – 1) Titik -titik hanya dapat diatur ke dalam array persegi panjang dengan satu kolom atau satu baris.

Untungnya, Édouard Lucas mengembangkan tes bilangan prima pada tahun 1878, yang kemudian dibuktikan oleh Derrick Henry Lehmer pada tahun 1930. Pekerjaan mereka menghasilkan algoritma yang efisien untuk mengevaluasi potensi bilangan prima Mersenne. Menggunakan algoritma ini dengan perhitungan tangan di atas kertas, Lucas menunjukkan pada tahun 1876 bahwa angka 39 digit (2¹²⁷ – 1) sama dengan 170.141.183.460.469.231.731.687.303.715.884.105.727, dan nilai itu adalah yang utama.

Juga dikenal sebagai M127, angka ini tetap menjadi prime terbesar yang diverifikasi oleh perhitungan tangan. Itu memegang rekor untuk Prime terbesar yang diketahui selama 75 tahun.

Para peneliti mulai menggunakan komputer pada 1950 -an, dan laju menemukan bilangan prima besar baru meningkat. Pada tahun 1952, Raphael M. Robinson mengidentifikasi lima bilangan prima New Mersenne menggunakan komputer otomatis barat standar untuk melakukan tes bilangan Lucas-Lehmer.

Ketika komputer membaik, daftar bilangan prima Mersenne tumbuh, terutama dengan kedatangan Cray Superkomputer pada tahun 1964. Meskipun ada banyak bilangan prima tak terbatas, para peneliti tidak yakin berapa banyak yang sesuai dengan jenisnya (2^P – 1) dan merupakan bilangan prima Mersenne.

Pada awal 1980 -an, para peneliti telah mengumpulkan cukup data untuk percaya bahwa ada banyak bilangan prima Mersenne. Mereka bahkan bisa menebak seberapa sering bilangan prima ini muncul, rata -rata. Matematikawan belum menemukan bukti sejauh ini, tetapi data baru terus mendukung tebakan -tebakan ini.

George Woltman, seorang ilmuwan komputer, mendirikan The Great Internet Mersenne Prime Search, atau GIMPS, pada tahun 1996. Melalui program kolaboratif ini, siapa pun dapat mengunduh perangkat lunak yang tersedia secara bebas dari situs web GIMPS untuk mencari bilangan prima Mersenne di komputer pribadi mereka. Situs web berisi instruksi khusus tentang cara berpartisipasi.

Gimps sekarang telah mengidentifikasi 18 bilangan prima Mersenne, terutama pada komputer pribadi menggunakan chip Intel. Program ini rata -rata penemuan baru tentang setiap satu hingga dua tahun.

Prime terbesar yang diketahui

Luke Durant, seorang pensiunan programmer, menemukan catatan saat ini untuk prime terbesar yang diketahui, (2^136.279.841 -1), pada Oktober 2024. Disebut sebagai M136279841, angka 41.024.320-digit ini adalah Mersenne Prime ke-52 yang diidentifikasi dan ditemukan dengan menjalankan GIMP pada jaringan komputasi berbasis cloud yang tersedia untuk umum.

Jaringan ini menggunakan chip NVIDIA dan berlari di 17 negara dan 24 pusat data. Chip canggih ini menyediakan komputasi yang lebih cepat dengan menangani ribuan perhitungan secara bersamaan. Hasilnya adalah waktu berjalan yang lebih pendek untuk algoritma seperti pengujian bilangan prima.

Electronic Frontier Foundation adalah kelompok kebebasan sipil yang menawarkan hadiah uang tunai untuk mengidentifikasi bilangan prima besar. Ini memberikan hadiah pada tahun 2000 dan 2009 untuk bilangan prima 1 juta digit dan 10 juta yang diverifikasi pertama.

Dua tantangan besar penggemar bilangan prima adalah untuk mengidentifikasi 100 juta digit pertama dan 1 miliar dua digit. Hadiah EFF US $ 150.000 dan $ 250.000, masing -masing, menunggu individu atau kelompok pertama yang sukses.

Delapan dari 10 bilangan prima terbesar yang diketahui adalah bilangan prima Mersenne, sehingga gimps dan komputasi awan siap untuk memainkan peran penting dalam pencarian bilangan prima yang memecahkan rekor.

Bilangan prima yang besar memiliki peran penting dalam banyak metode enkripsi dalam keamanan siber, sehingga setiap pengguna internet mendapat manfaat dari pencarian bilangan prima yang besar. Pencarian ini membantu menjaga komunikasi digital dan informasi sensitif tetap aman.

Jeremiah Bartz, Associate Professor Matematika, Universitas North Dakota. Artikel ini diterbitkan ulang dari percakapan di bawah lisensi Creative Commons. Baca artikel asli.