Beberapa orang berkata sebagai berikut:

Siapa pun yang berusaha menghasilkan angka acak dengan cara deterministik, tentu saja, hidup dalam keadaan berdosa.

Itu selalu berarti bahwa Anda tidak dapat menghasilkan angka acak benar hanya dengan komputer. Dan dia mengatakan bahwa ketika komputer adalah ukuran yang setara dengan mikroprosesor Intel 8080 tunggal (~ 6000 katup). Komputer menjadi semakin kompleks, dan saya percaya bahwa pernyataan von Von Neumann mungkin tidak lagi benar. Pertimbangkan bahwa algoritma perangkat lunak yang diimplementasikan saja tidak mungkin. Mereka berjalan pada perangkat keras fisik. Generator nomor acak sejati dan sumber entropi mereka juga terbuat dari perangkat keras.

Fragmen Java ini dimasukkan ke dalam lingkaran:

      file.writeByte((byte) (System.nanoTime() & 0xff));

dapat membuat file data yang saya wakili sebagai gambar:

Anda dapat melihat struktur, tetapi dengan banyak keacakan juga. Yang menarik adalah bahwa file PNG ini berukuran 232KB, namun mengandung 250.000 piksel skala abu-abu. Level kompresi PNG maksimum. Itu hanya rasio kompresi 7%, yaitu. cukup tidak kompresibel. Yang juga menarik adalah bahwa file tersebut unik. Setiap generasi dari file ini adalah pola yang sedikit berbeda dan memiliki kompresibilitas yang sama ~ 7%. Saya menyoroti ini karena ini penting untuk argumen saya. Itu ~ 7bits / byte entropy. Itu akan mengurangi tentu saja pada penggunaan algoritma kompresi yang lebih kuat. Tetapi tidak mengurangi menjadi mendekati 0 bit / byte. Kesan yang lebih baik dapat diperoleh dengan mengambil gambar di atas dan mengganti peta warnanya dengan yang acak: -

Sebagian besar struktur (di bagian atas) menghilang karena hanya urutan nilai yang sama tetapi sedikit berbeda. Apakah ini sumber entropi sejati yang dibuat dengan hanya menjalankan program Java pada sistem operasi multi pengambilan? Bukan generator nomor acak yang terdistribusi secara merata, tetapi sumber entropi untuk satu? Sumber entropi yang dibangun dari perangkat lunak yang berjalan pada perangkat keras fisik yang kebetulan merupakan PC.

Tambahan

Untuk mengkonfirmasi bahwa setiap gambar menghasilkan entropi segar tanpa pola tetap yang sama untuk semua, 10 gambar berurutan dihasilkan. Ini kemudian digabungkan dan dikompresi dengan pengarsipan terkuat yang bisa saya kompilasi (paq8px). Proses ini akan menghilangkan semua data umum, termasuk korelasi otomatis hanya menyisakan perubahan / entropi.

File gabungan dikompresi menjadi ~ 66%, yang mengarah ke tingkat entropi ~ 5,3 bit / byte atau 10,5Mbits / gambar. Entropi mengejutkan$\smile$

Tambahan 2

Ada komentar negatif bahwa entropi saya dengan metodologi uji kompresi cacat, hanya memberikan perkiraan batas atas yang longgar. Jadi sekarang saya telah menjalankan file gabungan melalui tes penilaian kriptografi entropi resmi NIST, SP800-90B_EntropyAssessment . Ini sama baiknya dengan pengukuran entropi non IID. Ini adalah laporannya (maaf pertanyaan ini semakin lama, tetapi masalahnya rumit): -

Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag 

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

Hasilnya adalah bahwa NIST percaya bahwa saya telah menghasilkan 5,6 bit / byte dari entropi. Perkiraan kompresi DIY saya menempatkan ini pada 5,3 bit / byte, sedikit lebih konservatif.

-> Bukti tampaknya mendukung anggapan bahwa komputer yang baru saja menjalankan perangkat lunak dapat menghasilkan entropi nyata. Dan von Neumann itu salah (tapi mungkin benar untuk zamannya).

Saya menawarkan referensi berikut yang mungkin mendukung klaim saya: -

Apakah ada model stokastik determinisme non dalam tingkat pelaksanaan program?

Analisis WCET dari Sistem Real-Time Sulit Probabilistik

Apakah ada algoritma perangkat lunak yang dapat menghasilkan pola kekacauan non-deterministik? dan relevansi efek kacau.

Paralel dengan prinsip ketidakpastian entropik Quantum

Entri blog Aleksey Shipilёv tentang perilaku kacau nanoTime (). Plot sebarnya tidak berbeda dengan milikku.

Hanya karena Anda tidak dapat melihat suatu pola tidak berarti tidak ada pola. Hanya karena algoritma kompresi tidak dapat menemukan pola, bukan berarti tidak ada pola. Algoritma kompresi bukan peluru perak yang secara ajaib dapat mengukur entropi sebenarnya dari suatu sumber; semua yang mereka berikan adalah batas atas jumlah entropi. (Demikian pula, tes NIST juga memberi Anda hanya batas atas.) Kekacauan bukanlah keacakan.

Diperlukan analisis dan pemeriksaan yang lebih rinci untuk mulai mendapatkan kepercayaan pada kualitas keacakan yang diperoleh dengan cara ini.

Ada yang alasan untuk berpikir bahwa kita mungkin dapat memperoleh beberapa jumlah keacakan dengan memanfaatkan jam jitter dan drift antara dua jam hardware , tapi itu halus dan rumit, sehingga Anda harus berhati-hati. Saya tidak akan merekomendasikan mencoba menerapkan Anda sendiri. Sebaliknya, saya sarankan Anda menggunakan sumber entropi berkualitas tinggi (biasanya diterapkan di sebagian besar sistem operasi modern). Untuk perincian lebih lanjut, lihat juga Wikipedia , tempa , dan /crypto//q/48302/351 (yang tampaknya sudah Anda sadari).

Terakhir, komentar tentang pembuka Anda:

"Siapa pun yang mencoba menghasilkan angka acak dengan cara deterministik, tentu saja, hidup dalam keadaan berdosa."

Itu selalu berarti bahwa Anda tidak dapat menghasilkan angka acak benar hanya dengan komputer.

Tidak, bukan seperti itu biasanya diambil, dan bukan itu yang dikatakan. Itu mengatakan Anda tidak dapat menghasilkan angka acak benar dengan cara deterministik . Apakah Anda dapat melakukannya di komputer tergantung pada apakah komputer itu deterministik atau tidak. Jika komputer bersifat deterministik, atau program Anda hanya menggunakan operasi deterministik, Anda tidak bisa. Namun, banyak komputer mengandung elemen non-deterministik, dan jika program Anda menggunakannya, diperlukan analisis yang lebih terperinci sebelum Anda dapat memutuskan apakah mereka dapat digunakan untuk menghasilkan angka acak. Dalam kasus Anda nanoTime()adalah non-deterministik.

Jika Anda menggunakan beberapa sumber perangkat keras dari entropi / keacakan, Anda tidak "berusaha menghasilkan keacakan dengan cara deterministik " (penekanan saya). Jika Anda tidak menggunakan sumber perangkat keras dari entropi / keacakan, maka komputer yang lebih kuat hanya berarti Anda dapat melakukan lebih banyak dosa per detik.

Saya selalu memahami kutipan yang berarti bahwa algoritma deterministik memiliki jumlah entropi yang tetap, dan meskipun output dapat tampak "acak", ia tidak dapat memuat lebih banyak entropi daripada yang diberikan input. Dari perspektif ini, kami melihat bahwa algoritma Anda menyelundupkan dalam entropi melalui System.nanoTime()- kebanyakan definisi dari algoritma "deterministik" akan melarang pemanggilan fungsi ini.

Kutipan - sementara bernas - pada dasarnya tautologi. Tidak ada yang bisa dibantah dan tidak ada evolusi perangkat keras yang dapat membuatnya tidak lagi benar. Ini bukan tentang perangkat keras, ini tentang definisi algoritma deterministik. Dia hanya mengamati bahwa determinisme dan keacakan tidak cocok. Untuk algoritma deterministik apa pun, seluruh perilakunya diprediksi oleh kondisi awalnya. Jika Anda merasa telah menemukan pengecualian, Anda salah memahami apa artinya menjadi deterministik.

Memang benar bahwa proses yang berjalan pada komputer bersama dengan serangkaian cache yang kompleks dan yang menerima berbagai input jaringan dan perangkat keras memiliki akses ke lebih banyak entropi daripada proses yang berjalan pada perangkat keras khusus, terisolasi, dan berdedikasi. Tetapi jika proses itu mengakses entropi itu tidak lagi deterministik dan kutipan tidak berlaku.

Siapa pun yang berusaha menghasilkan angka acak dengan cara deterministik, tentu saja, hidup dalam keadaan berdosa.

Ketika Anda menafsirkan "hidup dalam keadaan berdosa" sebagai "melakukan omong kosong", itu tidak benar.

Apa yang Anda lakukan adalah menggunakan metode yang agak lambat System.nanoTime()untuk menghasilkan keacakan yang agak lemah. Anda mengukur beberapa

... tingkat entropi ~ 5,3 bit / byte ...

tetapi ini hanya batas atas. Yang bisa Anda dapatkan adalah batas atas. Entropi nyata mungkin pesanan besarnya lebih kecil.

Coba alih-alih mengisi array menggunakan hash kriptografis seperti MD5. Hitung urutan seperti md5(0), md5(1), ...(dari setiap nilai yang diambil satu atau lebih byte, ini tidak masalah). Anda tidak akan mendapatkan kompresi sama sekali (ya, MD5 rusak, tetapi masih cukup baik untuk menghasilkan data yang tidak dapat dimampatkan).

Kita dapat mengatakan, bahwa tidak ada entropi sama sekali, namun Anda akan mengukur 8 bit / byte.

Ketika Anda benar-benar membutuhkan sesuatu yang acak, Anda tidak hanya harus menggunakan sumber HW, Anda juga harus mengetahui batas bawah yang pasti tentang berapa banyak entropi yang sebenarnya dihasilkannya. Meskipun ada kemungkinan besar ada keacakan nanoTime(), saya tidak mengetahui adanya batas bawah non-sepele di atasnya.

Ketika Anda membutuhkan keacakan untuk kriptografi, maka Anda benar-benar harus menggunakan sesuatu yang disediakan oleh OS Anda, bahasa Anda atau perpustakaan yang baik. Penyedia tersebut mengumpulkan entropi dari berbagai sumber dan / atau HW yang berdedikasi dan beberapa pekerjaan telah dimasukkan ke dalam estimasi entropi tersebut.

Perhatikan bahwa Anda biasanya hampir tidak memerlukan entropi apa pun. PRNG yang baik (deterministik) diinisialisasi dengan beberapa byte acak dapat digunakan untuk kriptografi, dan karenanya juga untuk semua yang lain.

Saya pikir saya akan berpegang pada arti "acak". Sebagian besar jawaban di sini berbicara tentang output dari proses acak , dibandingkan dengan output dari proses deterministik. Itu arti yang sangat baik dari "acak", tetapi itu bukan satu-satunya.

Satu masalah dengan output dari proses acak adalah bahwa mereka sulit untuk dibedakan dari output dari proses deterministik: mereka tidak mengandung "catatan" tentang seberapa acak sumbernya. Contoh ekstrem dari ini adalah komik XKCD yang terkenal di mana generator nomor acak selalu kembali 4, dengan komentar kode yang mengklaim bahwa itu acak karena berasal dari die roll.

Pendekatan alternatif untuk mendefinisikan "keacakan", yang disebut kompleksitas Kolmogorov , didasarkan pada data itu sendiri, terlepas dari bagaimana itu dihasilkan. Kompleksitas Kolmogorov dari beberapa data (misalnya urutan angka) adalah panjang dari program komputer terpendek yang menampilkan data itu: data "lebih acak" jika memiliki kompleksitas Kolmogorov yang lebih tinggi.

Penggunaan algoritma kompresi seperti PNG, dan membandingkan panjang sebelum dan sesudah kompresi, mirip dengan gagasan kompleksitas Kolmogorov. Namun, kompleksitas Kolmogorov memungkinkan data untuk dikodekan sebagai program dalam bahasa pemrograman Turing-complete, daripada format terbatas seperti PNG; "dekompresi" pengkodean (program) semacam itu dilakukan dengan menjalankannya, yang mungkin membutuhkan waktu dan memori yang sewenang-wenang (mis. lebih dari yang tersedia di alam semesta kita yang lemah).

Teorema Rice memberi tahu kita bahwa kita secara umum tidak dapat membedakan antara program yang berulang selamanya dan program yang menghasilkan data kita. Oleh karena itu sangat sulit untuk menemukan kompleksitas Kolmogorov dari beberapa data: jika kita menulis sebuah program yang menghasilkan data itu, mungkin sebenarnya ada program yang lebih pendek (yaitu kompleksitas yang lebih rendah), tetapi kami tidak menemukannya karena kami tidak dapat menemukannya. membedakannya dari loop tak terbatas. Karenanya, kompleksitas Kolmogorov tidak dapat dihitung, meskipun jika kita tahu angka Sibuk-Berang-berang kita dapat menghitungnya dengan menggunakan angka-angka itu untuk mengikat jumlah waktu yang kita periksa setiap program.

Dalam hal data contoh Anda, untuk menemukan kompleksitas Kolmogorovnya (yaitu "keacakan intrinsik"), kita perlu menemukan program deterministik terpendek yang menghasilkan urutan byte yang sama, dan mengambil panjangnya.

Sekarang kami dapat menjawab pertanyaan Anda dari sudut pandang kompleksitas Kolmogorov, dan kami menemukan bahwa kutipan itu benar: kami tidak dapat menghasilkan angka acak (kompleksitas Kolmogorov tinggi) dengan cara deterministik.

Kenapa tidak? Mari kita bayangkan bahwa kita menulis sebuah program komputer kecil dan kita menggunakannya untuk menghasilkan urutan angka acak. Salah satu situasi berikut harus berlaku:

• Kami menghasilkan sejumlah besar output. Namun, karena kita tahu bahwa output ini dihasilkan oleh sebuah program kecil, output (menurut definisi) memiliki kompleksitas Kolmogorov yang rendah, dan karenanya ini bukan "acak" dalam pengertian ini.
• Kami menghasilkan angka yang sangat sedikit sehingga menuliskan semuanya akan membutuhkan waktu yang sama, atau bahkan lebih sedikit, daripada menuliskan program penghasil singkat kami. Dalam hal ini, jumlahnya relatif tidak dapat dimampatkan, yang menunjukkan bahwa mereka cukup acak dalam arti Kolmogorov. Namun, karena jumlah output sebanding dengan apa yang kami masukkan (kode sumber untuk program), wajar untuk mengatakan bahwa program tidak "menghasilkan" keacakan, kami lakukan dengan memilih program itu. Bagaimanapun, dalam hal ini program pembangkit kami mungkin juga hanya daftar angka-angka yang tepat ini (misalnya print([...])).

Dalam kedua kasus tersebut, kami tidak "menghasilkan" lebih banyak keacakan daripada yang kami masukkan ("keacakan" dari kode sumber program penghasil kami). Kami mungkin mencoba mengatasinya dengan menggunakan program pembangkit yang lebih lama, untuk menghindari keluaran yang memiliki generator pendek, tetapi hanya ada dua cara untuk melakukannya:

• Secara sistematis "mengasapi" kode dengan beberapa cara. Namun, kompleksitas Kolmogorov tidak peduli dengan program tertentu yang kami gunakan untuk menghasilkan data: hanya peduli tentang program mana saja yang menghasilkan terkecil. Mengasapi sistematik tidak menambah kompleksitas Kolmogorov, karena pola-pola dalam kode itu sendiri dapat dihasilkan dengan jumlah kode yang sangat kecil. Sebagai contoh jika kita mengambil run(shortGenerator)dan menambahkan seluruh beban mengasapi sistematis untuk mendapatkan run(bloatedGenerator), generator pendek masih ada bentuk run(addBloat(shortGenerator)).
• Tambahkan mengasapi non-sistematis , yaitu tanpa pola, sehingga suatu addBloatfungsi harus berakhir menjadi sama kembung seperti kode itu sendiri. Namun, menjadi begitu tanpa pola adalah apa yang membuat sesuatu menjadi acak (kompleksitas Kolmogorov tinggi). Oleh karena itu menggembungkan program pembangkit dengan cara ini memang meningkatkan keacakan (kompleksitas Kolmogorov) dari output, tetapi juga meningkatkan jumlah keacakan (kompleksitas Kolmogorov) yang harus kami berikan dalam bentuk kode sumber. Oleh karena itu masih kita yang menyediakan "keacakan" dan bukan programnya. Dalam contoh di atas hanya menulis print([...]), menambahkan mengasapi non-sistematis setara dengan hanya menulis lebih banyak angka "acak" dalam daftar kode keras itu.

Kompresi bukanlah tes keacakan yang akurat, dan juga tidak melihat gambar dan mengatakan "itu terlihat acak".

Keacakan diuji dengan metode empiris . Sebenarnya ada rangkaian perangkat lunak / algoritma yang dirancang khusus untuk menguji keacakan, misalnya TestU01 dan tes Diehard .

Terlebih lagi, gambar Anda sebenarnya adalah string angka 1D yang dipetakan pada spasi, dan karenanya bukan representasi yang baik dari pola tertentu yang dapat muncul.

Jika Anda memeriksa pixel gambar Anda dengan pixel, kemungkinan besar Anda akan menemukan banyak pola pendek nilai meningkat sebelum penurunan tiba-tiba. Jika Anda membuat grafik dengan nilai x sebagai jumlah sampel dan nilai y menjadi nilai yang diperoleh dari fungsi 'acak', Anda kemungkinan besar akan menemukan bahwa data Anda sebenarnya terlihat seperti gelombang gigi gergaji:

Ini adalah pola yang dibuat oleh nilai-nilai yang meningkat di bawah aritmatika modular (yang perhitungan Anda adalah contoh dari: peningkatan waktu pada laju konstan dekat, dan & 0xFFbertindak sebagai mod 256).

Anda membingungkan konsep angka acak dari "angka yang tampaknya acak."

Untuk memahami kutipan von Neumann, kita harus memahami apa artinya "menghasilkan angka acak." Jawaban Warbo ini menghubungkan sangat baik XKCD untuk tujuan ini:

Ketika kita berbicara tentang angka acak, kita tidak berbicara tentang nilai itu sendiri. Jelas angka 4 tidak lebih acak dari angka 3. Kita berbicara tentang kemampuan kemampuan pihak ketiga untuk memprediksi nilai ini lebih baik daripada peluang acak. Angka acak adalah nomor yang tidak dapat diprediksi. Terkadang kami akan menambahkan kondisi ini. Pseudo-random number generator (CSPRNG) yang aman secara Cryptographically menghasilkan angka yang tidak dapat diprediksi lebih baik daripada peluang acak jika penyerang tidak mengetahui seed / kunci, tetapi jika kita berbicara tentang angka yang benar-benar acak (bukan pseudo-acak), biasanya didefinisikan sebagai angka yang tidak dapat diprediksi, bahkan dengan pengetahuan lengkap tentang sistem, termasuk kunci apa pun.

Sekarang, teladan Anda, sebagaimana telah banyak ditunjukkan, tidak bersifat deterministik. Program tidak menentukan nilai apa yang keluar System.nanoTime(). Jadi itu tidak di kelas yang sama dengan menggunakan CSPRNG untuk menghasilkan angka acak semu. Yang pertama mungkin nondeterministic sedangkan yang terakhir bersifat deterministik jika nilai kunci adalah deterministik. Yang pertama berisi operasi yang tidak didefinisikan memiliki nilai deterministik.

Namun, Anda akan perhatikan bahwa saya mengatakan mungkin tidak deterministik. Sadarilah bahwa System.nanoTime()ini tidak dirancang untuk memberikan nilai untuk tujuan ini. Ini mungkin atau mungkin tidak cukup tidak deterministik. Aplikasi mungkin menyesuaikan jam sistem sedemikian rupa sehingga panggilan untuk System.nanoTime()semua terjadi pada kelipatan 256 nanodetik (atau tutup). Atau Anda mungkin bekerja di Javascript, di mana eksploitasi Specter baru-baru ini telah mengarahkan browser utama untuk secara sengaja mengurangi resolusi timer mereka. Dalam kasus ini, "angka acak" Anda dapat menjadi sangat dapat diprediksi di lingkungan yang tidak Anda rencanakan.

• Jadi menghasilkan angka acak dengan proses deterministik ... dosa.
• Menghasilkan angka acak dengan perangkat keras acak khusus ... bukan dosa.
• Menghasilkan angka acak dengan aspek komputer yang tidak ditentukan ... mungkin berdosa.

Itu semua tergantung pada apa yang Anda inginkan. Jika Anda mengenkripsi surat cinta Anda ke Sponge Bob sehingga saudari Anda tidak bisa membacanya, permintaan yang disebut pada angka acak Anda cukup rendah. System.nanoTime()digunakan seperti yang Anda lakukan mungkin cukup baik. Jika Anda melindungi rahasia nuklir dari negara asing maju yang secara aktif mencari mereka, Anda mungkin ingin mempertimbangkan untuk menggunakan perangkat keras yang dirancang untuk menghadapi tantangan.

Saya pikir Anda tidak memahami klaim itu. Intinya adalah jika ada prosedur deterministik untuk menghasilkan seri angka 'acak' (atau apa pun, sungguh), maka menemukan polanya hanyalah tugas menemukan prosedur ini!

Oleh karena itu, selalu ada metode deterministik untuk memprediksi integer berikutnya. Inilah tepatnya yang tidak kita harapkan terjadi jika kita menganggap keacakan!

Setiap deterministik yang cukup kompleks tidak dapat dibedakan dari stokastik.

--Dari halaman pengguna Wrzlprmft

Oleh karena itu, bahkan jika sesuatu terlihat acak, mengapa kita memodelkannya sebagai 'acak' jika kita memiliki prosedur deterministik untuk menghasilkannya?

Ini, saya pikir, adalah masalah utama. Anda hanya menunjukkan beberapa bentuk PRNG yang tidak bisa dibedakan dan 'keacakan yang sebenarnya'.

Namun, konsep-konsep ini karenanya sama tidak mengikuti. Secara khusus, keacakan adalah konsep matematika, teoretis . Kami telah menunjukkan di atas, bahwa dalam teori, menganggap PRNG sebagai 'keacakan sejati' mengarah pada kontradiksi. Karenanya, mereka tidak bisa sama.

Saya pikir orang lain sudah menunjukkannya, tapi itu tidak terlalu menekankan, jadi izinkan saya juga menambah diskusi.

Seperti yang sudah ditunjukkan orang lain, ada masalah mengukur entropi. Algoritma kompresi mungkin memberi tahu Anda sesuatu, tetapi mereka agnostik-sumber. Karena Anda tahu lebih banyak tentang bagaimana data dihasilkan, Anda mungkin dapat membatasi algoritma yang lebih baik untuk mengompresnya, dan itu berarti entropi yang sebenarnya jauh lebih rendah.

Selain itu, Anda agak salah mengartikan makna frasa "di komputer" dan "deterministik". Anda tentu dapat melakukan operasi nondeterministic di komputer.

Lebih jauh lagi, pada kenyataannya, Anda baru saja melakukannya , tetapi tidak begitu jelas pada pandangan pertama.

Algoritma deterministik tipikal untuk pembuatan bilangan acak adalah. PRNG seperti generator kongruensial linier. Mereka adalah negara. Keadaan dalam berarti kurang entropi karena keadaan selanjutnya ditentukan oleh sebelumnya. Saya tidak akan mempelajari itu, mungkin jelas bagi Anda. Poin penting adalah bahwa algoritma deterministik sepenuhnya hanya bergantung pada keadaan sebelumnya, apa pun itu.

Sekarang lihat algoritma Anda. Berdasarkan apa? Berapa banyak status yang Anda miliki? Apakah itu deterministik?

  file.writeByte((byte) (System.nanoTime() & 0xff));

Mari kita abaikan file.writedan semua masalah penyiraman buffer, menunggu I / O (apakah Anda mencoba untuk menambah derau pada kabel harddisk sejenak? Tidak? Hei Anda bisa melakukannya. Hei, itu nondeterministic kalau begitu! :)), dan mari kita fokus pada sumbernya, itu lebih penting.

The Waktu adalah semacam negara. Ini bervariasi, tetapi sebagian besar sama. Itulah mengapa Anda mencoba mengelak dan mengambil & 0xFF untuk membatalkan sebagian besar keadaan. Tetapi Anda belum menjatuhkan semuanya, beberapa keadaan dari pembacaan sebelumnya mungkin bocor ke yang berikutnya, jadi tentu saja tidak sepenuhnya non-deterministik *)

Tapi kami tidak tertarik dengan itu. Untuk "membuktikan" bahwa kutipannya salah:

Siapa pun yang berusaha menghasilkan angka acak dengan cara deterministik, tentu saja, hidup dalam keadaan berdosa.

Anda perlu membuktikannya dengan cara deterministik.
Yang kami minati adalah: apakah algo Anda tentu sepenuhnya deterministik ?

..dan Sudah jelas tidak.

  System.nanoTime() & 0xff

Itu pengukuran waktu. Waktu dan pengukuran . Bagian pengukuran dapat membuatnya deterministik, jika nilainya di-cache. Saya berasumsi tidak, kalau tidak fungsi ini tidak masuk akal. Kemudian, jika dibaca dengan cepat dari sumber, kami memiliki nilai berdasarkan waktu. Karena ( saya berasumsi lagi ) Anda tidak menjalankannya pada perangkat keras khusus satu tugas, maka terkadang Anda mungkin harus berpindah konteks. Bahkan jika Anda memiliki perangkat keras khusus untuk satu tugas, pengukuran waktu mungkin masih tidak deterministik, karena suhu / kelembaban melayang di sumber waktu, waktu pencatatan jam bus, dll.

Saya sepenuhnya setuju saya senang di sini. Drift tidak akan sebesar itu untuk membuat banyak dampak (meskipun untuk nyata nanotimemereka bisa jadi). Lebih penting lagi, nanotimeini dimaksudkan untuk menjadi cepat. Itu tidak membaca dari sumber waktu nyata. Ini didasarkan pada instruksi / siklus hitungan dalam prosesor. Itu sebenarnya deterministik, jika Anda memastikan tidak ada konteks yang berubah.

Maksud saya adalah, mungkin sebenarnya sangat sulit untuk menjalankan algoritma deterministik yang benar-benar 100% jika Anda mendasarkannya tepat waktu, dan Anda tidak memiliki hak untuk membantah kutipan itu kecuali jika Anda memiliki cara deterministik sepenuhnya.

*) Menariknya, Anda mungkin dapat meningkatkan keacakan yang sebenarnya jika Anda menggunakan cara yang hardcore. Lakukan & 0x01, sedikit demi sedikit, dan utas - tunggu waktu yang nyata, sebelum membaca setiap bit. Menghasilkan data seperti itu akan sangat panjang, tetapi saya sebenarnya berpendapat bahwa itu bisa dianggap hampir benar-benar acak, IIF Anda berjalan pada non-RTOS dan juga IFF di setiap 'waktu yang terlihat' cukup tinggi untuk memastikan bahwa yang mendasarinya OS baik tidur, atau konteks-beralih ke tugas lain.

Saya pikir jawaban yang Anda butuhkan dimulai dengan komentar ini yang Anda buat sendiri dalam menjawab jawaban lain:

Polanya adalah hasil dari interaksi Java, JVM, OS, cache CPU +, hard disk, musik Trans saya streaming yang mengkonsumsi siklus CPU / RAM dan segala sesuatu di antaranya. Pola hanya muncul dari satu baris kode Java di dalam untuk / loop berikutnya. Bagian penting dari entropi berasal dari sirkuit perangkat keras yang mendasarinya.

Anda sudah menyadari ini, saya pikir: Anda tidak menggunakan cara deterministik untuk membuat pola.

Anda menggunakan komputer, bagian yang tidak dapat diabaikan yang bersifat deterministik, tetapi entropi berasal dari eksternal yang non-deterministik (atau setidaknya, non-deterministik untuk semua maksud dan tujuan praktis saat ini) sumber: Anda atau dunia eksternal yang berinteraksi dengan komputer (dan pada tingkat lebih rendah, segala ketidaksempurnaan fisik dalam perangkat keras komputer yang mungkin mempengaruhi pengaturan waktu hal-hal).

Omong-omong, ini adalah bagian besar dari bagaimana sistem operasi modern menyemai generator angka acak mereka yang tersedia untuk program: dengan memanfaatkan entropi dalam interaksi dengan perangkat kerasnya dan pengguna yang kami harap tidak dapat diprediksi oleh penyerang.

Ngomong-ngomong, entropi dunia-eksternal sebenarnya merupakan masalah yang harus diatasi hingga hari ini dalam kriptografi yang dikodekan dengan baik: komputer yang memiliki perilaku yang dapat diprediksipada saat boot dan selama runtime, seperti yang dengan penyimpanan read-only atau yang boot dari jaringan, dan yang memiliki lingkungan jaringan yang dapat diprediksi (baik tidak terpasang ke jaringan atau beban kerja pada jaringan cukup rendah sehingga semuanya dikirim dalam jumlah waktu yang dapat diandalkan), dan yang menjalankan perangkat lunak terbatas yang sama dengan perilaku yang hampir konsisten, mungkin terlalu tinggi memperkirakan entropi yang mereka peroleh dari komponen yang dianggap tidak dapat diprediksi ini, dan akhirnya menghasilkan angka yang jauh lebih dapat diprediksi. daripada yang Anda dapatkan di stasiun kerja biasa yang melakukan segala macam hal lain untuk Anda (streaming musik, sinkronisasi dengan dropbox, apa pun) di latar belakang.

Saya pikir sebagian besar jawaban semakin terfokus pada apakah memeriksa delapan bit terakhir pengukuran waktu dalam nanodetik yang diambil dalam satu lingkaran adalah cara yang baik untuk memanen entropi itu. Ini adalah sangat pertanyaan penting untuk menjawab dengan benar sebelum Anda menggunakan metode dalam contoh Anda sebagai skema generasi nomor acak dalam praktek , tapi itu pertanyaan terpisah dari apa yang saya pikir Anda bertanya tentang.

Untuk menambah jawaban sebelumnya, berikut adalah cara mudah untuk memikirkan pertanyaan ini.

Ini semua tentang perbedaan antara acak dan deterministik . Kami akan datang ke Von Neumann dan apa yang dia katakan, sesudahnya.

Angka acak

Generator angka acak yang benar tidak akan memiliki pola, bahkan tidak tersembunyi di latar belakang, yang dapat kita gunakan untuk memprediksi nomor berikutnya mengingat urutan sejauh ini. Di dunia yang ideal, Anda bisa mengetahui segala sesuatu yang perlu diketahui di alam semesta fisik, dan tentang sistem, nanosecond oleh nanosecond, dan masih akan sia-sia untuk mencoba dan memprediksi angka berikutnya yang diproduksi.

Itu adalah kasus yang ideal - dalam istilah praktis kita sampai di sana dengan menggabungkan banyak sumber yang "bukan perkiraan buruk" menjadi acak, atau benar-benar acak, atau yang secara matematis mencampuradukkan banyak hal sehingga Anda dapat secara matematis membuktikan bahwa mereka menjadi sangat dekat dengan yang tidak bisa dihilangkan dan tidak bias terhadap angka atau pola tertentu.

• Sumber "baik" adalah hal-hal yang mirip dengan menunggu proses peluruhan radioaktif, atau proses kuantum lain yang secara inheren tidak dapat diprediksi. Output dari semikonduktor sensitif panas. Kebisingan acak dalam dioda atau bahan listrik lainnya. Menghitung foton dari matahari.

• Digabungkan dengan ini, kami juga dapat menambahkan beberapa yang kami anggap "tidak buruk" yang membantu karena mereka tidak memiliki koneksi ke ini: Menunggu mouseclick atau paket jaringan berikutnya. Bit terakhir dari microtime pada file selanjutnya tulis. Output dari fungsi generator nomor pseudorandom "dikenal tetapi matematis acak". Entropi sebelumnya dari penggunaan angka acak sebelumnya.

Tujuannya di sini, adalah untuk mendapatkan angka yang masih tidak dapat diprediksi , apa pun di alam semesta yang Anda tahu , dan secara statistik kemungkinan akan seperti ini, tanpa pola yang dapat dideteksi secara matematis, bias atau prediktabilitas, dan tidak ada korelasi dengan peristiwa yang dapat dimonitor dan digunakan untuk prediksi. (Atau jika berkorelasi dengan suatu peristiwa, maka itu dilakukan dengan cara yang membuat koneksi menjadi sangat renggang, seperti "digit nanodetik hanya saat klik mouse terakhir")

Angka deterministik

Matematikawan dapat membuktikan hal-hal tentang rumus dan fungsi. Jadi mungkin untuk membuktikan bahwa suatu fungsi, ketika berulang kali dipanggil, tidak memberikan bias atau preferensi pada pola apa pun, selain pola sederhana "ini adalah output dari fungsi itu jika berulang kali disebut".

Jadi misalnya, jika Anda memilih angka yang mengatakan antara 1 dan 10 juta, tulislah dalam biner, dan "hash" berulang kali, Anda akan mendapatkan urutan angka yang terlihat acak. Hampir acak - tetapi sebenarnya tidak acak sama sekali. Anda dapat memprediksi dengan algoritma dan kondisi apa pun, berapa angka selanjutnya.

Kami menyebutnya "pseudorandom" karena terlihat dan tampaknya sebagian besar acak, bahkan jika tidak.

Ini contoh yang bagus. Pikirkan tentang urutan 3 digit "angka acak" ini: 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Katakan saja saya beri tahu Anda Saya dapat menghasilkan jutaan angka dengan cara yang sama. Anda dapat memberikan kepada ahli statistik yang akan mengkonfirmasi (mengatakan) bahwa mereka didistribusikan secara merata atau apa pun itu. Tidak ada pola yang bisa diprediksi jelasb. Mereka terlihat sangat acak, bukan? Tetapi sekarang saya memberi tahu Anda bahwa mereka sebenarnya

digit ke-500 Pi, dikelompokkan dalam 3s.

Tiba-tiba, bagaimanapun acak itu

digit Pi

mungkin, Anda dapat segera memprediksi bahwa 2 angka berikutnya adalah 986 dan 094.

Untuk lebih jelasnya, saya tidak tahu persis bagaimana acaknya

digit Pi

adalah. Itu akan dipelajari dan jawabannya sudah diketahui. Tetapi intinya adalah ini: Pada prinsipnya, kesimpulan yang sama berlaku untuk setiap sumber yang dihasilkan setelah proses deterministik .

Diantara

Di antara keduanya, ada berbagai macam "hal-hal yang terlihat acak dan seringkali acak hingga taraf tertentu". Semakin banyak keacakan dan hampir keacakan yang dapat digabungkan, semakin kecil kemungkinan keluarannya untuk dapat mendeteksi pola atau output apa pun yang diprediksi, secara matematis.

Kembali ke von Neumann dan pertanyaan Anda

Seperti yang Anda lihat, output deterministik mungkin terlihat acak, tetapi dan bahkan mungkin, secara statistik, didistribusikan secara acak. Mereka bahkan mungkin menggunakan "rahasia" atau data yang berubah cepat yang kita tidak memiliki harapan realistis untuk mengetahuinya. Tapi selama itu deterministik, angka-angka itu masih belum pernah benar-benar acak . Mereka hanya bisa "cukup dekat ke acak sehingga kami senang melupakan perbedaannya".

Itulah arti dari kutipan yang Anda berikan. Proses deterministik tidak bisa memberikan angka acak. Ini hanya dapat memberikan angka yang tampaknya, dan berperilaku cukup seperti, angka acak.

Kami sekarang dapat menguraikan kembali pertanyaan Anda seperti ini: "Output komputer saya (atau modern) dapat terlihat dan berperilaku secara acak, apakah itu berarti kutipan von Neumann sekarang ketinggalan jaman dan salah?"

Masalahnya masih seperti ini: Bahkan jika output komputer Anda mungkin terlihat dan berperilaku secara acak, masih mungkin tidak benar - benar acak . Jika itu hanya dihitung secara deterministik, itu berarti tidak ada yang tidak dapat dipulihkan sebab akibat tentang mendapatkan nomor berikutnya (itulah yang dimaksud "deterministik" dalam pengertian ini). Kami mulai dengan beberapa data yang ada (diketahui), kami menerapkan proses yang dikenal (kompleks atau berantakan atau apa pun), dan kami mendapatkan apa yang tampaknya "nomor acak" baru keluar. Tetapi ini tidak acak, karena prosesnya bersifat deterministik.

Jika Anda mengatakan bahwa metode Anda akan menyertakan generator acak perangkat keras yang sebenarnya, untuk memperbaikinya (seperti angka acak yang dihasilkan dari peluruhan radioaktif atau derau dalam semikonduktor), maka jawaban Anda sekarang bisa acak - tetapi metode Anda menurut definisi tidak lagi deterministik , tepatnya karena Anda tidak dapat memprediksi output (atau efek) yang diberikan input / data awal (penyebab) lagi .

Von Neumann memenangkan kedua cara, hampir secara definisi!