Apa saja aplikasi Kompleksitas Kolmogorov dalam Teori Angka dan pada bidang terkait bukti? (Monograf oleh Li & Vitanyi tidak memiliki banyak aplikasi yang terkait dengan Teori Angka.)
Salah satu bukti bagus yang saya temui adalah bukti keberadaan bilangan prima tak terbatas, menggunakan definisi Kompleksitas Kolmogorov dan faktor kompresi.
Juga, apa pentingnya Kompleksitas Kolmogorov dalam Kriptografi?
Jawaban:
Setiap integer memiliki kompleksitas Kolmogorov terkait; program terpendek yang mencetak bilangan bulat itu.
Ada bilangan prima hingga sehingga bilangan prima memiliki kompleksitas Kolmogrov yang lebih rendah daripada rata-rata komposit; vs . x≈ln(x≈ xl n ( x ) x ≈ l n ( xl n ( x )) ≈ l n ( x )
Sebagai efek samping Anda harus memiliki beberapa celah besar di antara bilangan prima; jika tidak, Anda bisa menyandikan setiap angka sebagai bilangan prima sebelumnya ditambah sejumlah kecil bit.
sumber
Teori bilangan umumnya berkaitan dengan persamaan bilangan bulat, meskipun catatan wikipedia menyatakan , lebih luas, subbranch dari teori bilangan adalah perkiraan dari real dengan rasional dan hubungan di antara mereka: "Orang juga dapat mempelajari bilangan real dalam kaitannya dengan bilangan rasional, misalnya, seperti yang diperkirakan oleh yang terakhir ( Diophantine approximation ). "
berikut adalah dua makalah yang secara umum sejalan:
Kompleksitas Kolmogorov dari bilangan real Ludwig Staiger
Karakterisasi ce acak real Cristian S. Calude
sumber
coba referensi ini
sumber