Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π”Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл

Π“Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ псСвдослучайных чисСл (Π“ΠŸΠ‘Π§, Π°Π½Π³Π». Pseudorandom number generator, PRNG ) β€” Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ чисСл, элСмСнты ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΠΎΡ‡Ρ‚ΠΈ нСзависимы Π΄Ρ€ΡƒΠ³ ΠΎΡ‚ Π΄Ρ€ΡƒΠ³Π° ΠΈ ΠΏΠΎΠ΄Ρ‡ΠΈΠ½ΡΡŽΡ‚ΡΡ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡƒ Ρ€Π°ΡΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΡŽ (ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎΠΌΡƒ).

БоврСмСнная ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ° ΡˆΠΈΡ€ΠΎΠΊΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ псСвдослучайныС числа Π² самых Ρ€Π°Π·Π½Ρ‹Ρ… прилоТСниях β€” ΠΎΡ‚ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° ΠœΠΎΠ½Ρ‚Π΅-ΠšΠ°Ρ€Π»ΠΎ ΠΈ ΠΈΠΌΠΈΡ‚Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠ³ΠΎ модСлирования Π΄ΠΎ ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ. ΠŸΡ€ΠΈ этом ΠΎΡ‚ качСства ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Ρ… Π“ΠŸΠ‘Π§ Π½Π°ΠΏΡ€ΡΠΌΡƒΡŽ зависит качСство ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌΡ‹Ρ… Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ². Π­Ρ‚ΠΎ ΠΎΠ±ΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ ΠΏΠΎΠ΄Ρ‡Ρ‘Ρ€ΠΊΠΈΠ²Π°Π΅Ρ‚ извСстный Π°Ρ„ΠΎΡ€ΠΈΠ·ΠΌ Π ΠΎΠ±Π΅Ρ€Ρ‚Π° Π . Кавью ΠΈΠ· ORNL (Π°Π½Π³Π».): «гСнСрация случайных чисСл слишком Π²Π°ΠΆΠ½Π°, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ Π΅Ρ‘ Π½Π° волю случая».

Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅

Π”Π΅Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ Π“ΠŸΠ‘Π§

Никакой Π΄Π΅Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ случайныС числа, ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π°ΠΏΠΏΡ€ΠΎΠΊΡΠΈΠΌΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ свойства случайных чисСл. Как сказал Π”ΠΆΠΎΠ½ Ρ„ΠΎΠ½ НСйман, «всякий, ΠΊΡ‚ΠΎ ΠΏΠΈΡ‚Π°Π΅Ρ‚ ΡΠ»Π°Π±ΠΎΡΡ‚ΡŒ ΠΊ арифмСтичСским ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌ получСния случайных чисСл, Π³Ρ€Π΅ΡˆΠ΅Π½ Π²Π½Π΅ всяких сомнСний».

Π‘ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ простых арифмСтичСских Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² хотя ΠΈ ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‚ большой ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒΡŽ, Π½ΠΎ ΡΡ‚Ρ€Π°Π΄Π°ΡŽΡ‚ ΠΎΡ‚ ΠΌΠ½ΠΎΠ³ΠΈΡ… ΡΠ΅Ρ€ΡŒΡ‘Π·Π½Ρ‹Ρ… нСдостатков:

Π“ΠŸΠ‘Π§ с источником энтропии ΠΈΠ»ΠΈ Π“Π‘Π§

НаравнС с ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΉ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒΡŽ Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π»Π΅Π³ΠΊΠΎ воспроизводимыС ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ случайных чисСл, Ρ‚Π°ΠΊΠΆΠ΅ сущСствуСт Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒ Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΡΠΎΠ²Π΅Ρ€ΡˆΠ΅Π½Π½ΠΎ нСпрСдсказуСмыС ΠΈΠ»ΠΈ попросту Π°Π±ΡΠΎΠ»ΡŽΡ‚Π½ΠΎ случайныС числа. Π’Π°ΠΊΠΈΠ΅ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ΡΡ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°ΠΌΠΈ случайных чисСл (Π“Π‘Π§ β€” Π°Π½Π³Π». random number generator, RNG ). Π’Π°ΠΊ ΠΊΠ°ΠΊ Ρ‚Π°ΠΊΠΈΠ΅ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Ρ‡Π°Ρ‰Π΅ всСго ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ для Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½Ρ‹Ρ… симмСтричных ΠΈ асиммСтричных ΠΊΠ»ΡŽΡ‡Π΅ΠΉ для ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, ΠΎΠ½ΠΈ Ρ‡Π°Ρ‰Π΅ всСго строятся ΠΈΠ· ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ криптостойкого Π“ΠŸΠ‘Π§ ΠΈ внСшнСго источника энтропии (ΠΈ ΠΈΠΌΠ΅Π½Π½ΠΎ Ρ‚Π°ΠΊΡƒΡŽ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΡŽ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΠΈ принято ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ‚ΡŒ ΠΏΠΎΠ΄ Π“Π‘Π§).

ΠŸΠΎΡ‡Ρ‚ΠΈ всС ΠΊΡ€ΡƒΠΏΠ½Ρ‹Π΅ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΠΈ ΠΌΠΈΠΊΡ€ΠΎΡ‡ΠΈΠΏΠΎΠ² ΠΏΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Π΅ Π“Π‘Π§ с Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌΠΈ источниками энтропии, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ для ΠΈΡ… очистки ΠΎΡ‚ Π½Π΅ΠΈΠ·Π±Π΅ΠΆΠ½ΠΎΠΉ прСдсказуСмости. Однако Π½Π° Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ сбора случайных чисСл всСми ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠΌΠΈ ΠΌΠΈΠΊΡ€ΠΎΡ‡ΠΈΠΏΠ°ΠΌΠΈ (нСсколько тысяч Π±ΠΈΡ‚ Π² сСкунду) Π½Π΅ соотвСтствуСт Π±Ρ‹ΡΡ‚Ρ€ΠΎΠ΄Π΅ΠΉΡΡ‚Π²ΠΈΡŽ соврСмСнных процСссоров.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€Ρ‹ Π“Π‘Π§ ΠΈ источников энтропии

НСсколько ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ² Π“Π‘Π§ с ΠΈΡ… источниками энтропии ΠΈ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°ΠΌΠΈ:

Π“ΠŸΠ‘Π§ Π² ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ

Π Π°Π·Π½ΠΎΠ²ΠΈΠ΄Π½ΠΎΡΡ‚ΡŒΡŽ Π“ΠŸΠ‘Π§ ΡΠ²Π»ΡΡŽΡ‚ΡΡ Π“ΠŸΠ‘Π‘ (PRBG) β€” Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ псСвдо-случайных Π±ΠΈΡ‚, Π° Ρ‚Π°ΠΊ ΠΆΠ΅ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… ΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Ρ… ΡˆΠΈΡ„Ρ€ΠΎΠ². Π“ΠŸΠ‘Π§, ΠΊΠ°ΠΊ ΠΈ ΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Π΅ ΡˆΠΈΡ„Ρ€Ρ‹, состоят ΠΈΠ· Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ состояния (ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Ρ€Π°Π·ΠΌΠ΅Ρ€ΠΎΠΌ ΠΎΡ‚ 16 Π±ΠΈΡ‚ Π΄ΠΎ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΌΠ΅Π³Π°Π±Π°ΠΉΡ‚), Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ состояния ΠΊΠ»ΡŽΡ‡ΠΎΠΌ ΠΈΠ»ΠΈ сСмСнСм (Π°Π½Π³Π». seed ), Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ обновлСния Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅Π³ΠΎ состояния ΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π²Ρ‹Π²ΠΎΠ΄Π°. Π“ΠŸΠ‘Π§ ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»ΡΡŽΡ‚ΡΡ Π½Π° простыС арифмСтичСскиС, сломанныС криптографичСскиС ΠΈ криптостойкиС. Π˜Ρ… ΠΎΠ±Ρ‰Π΅Π΅ ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ β€” гСнСрация ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ чисСл, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΡ‚ΡŒ ΠΎΡ‚ случайных Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌΠΈ.

Π₯отя ΠΌΠ½ΠΎΠ³ΠΈΠ΅ криптостойкиС Π“ΠŸΠ‘Π§ ΠΈΠ»ΠΈ ΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Π΅ ΡˆΠΈΡ„Ρ€Ρ‹ ΠΏΡ€Π΅Π΄Π»Π°Π³Π°ΡŽΡ‚ Π³ΠΎΡ€Π°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ «случайныС» числа, Ρ‚Π°ΠΊΠΈΠ΅ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ Π³ΠΎΡ€Π°Π·Π΄ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹Ρ… арифмСтичСских ΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Ρ‹ Π²ΠΎ всякого Ρ€ΠΎΠ΄Π° исслСдованиях, Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‰ΠΈΡ…, Ρ‡Ρ‚ΠΎΠ±Ρ‹ процСссор Π±Ρ‹Π» свободСн для Π±ΠΎΠ»Π΅Π΅ ΠΏΠΎΠ»Π΅Π·Π½Ρ‹Ρ… вычислСний.

Π’ Π²ΠΎΠ΅Π½Π½Ρ‹Ρ… цСлях ΠΈ Π² ΠΏΠΎΠ»Π΅Π²Ρ‹Ρ… условиях ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ засСкрСчСнныС синхронныС криптостойкиС Π“ΠŸΠ‘Π§ (ΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Π΅ ΡˆΠΈΡ„Ρ€Ρ‹), Π±Π»ΠΎΡ‡Π½Ρ‹Π΅ ΡˆΠΈΡ„Ρ€Ρ‹ Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ. ΠŸΡ€ΠΈΠΌΠ΅Ρ€Π°ΠΌΠΈ извСстных криптостойких Π“ΠŸΠ‘Π§ ΡΠ²Π»ΡΡŽΡ‚ΡΡ ISAAC, SEAL, Snow, совсСм ΠΌΠ΅Π΄Π»Π΅Π½Π½Ρ‹ΠΉ тСорСтичСский Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π‘Π»ΡŽΠΌΠ°, Π‘Π»ΡŽΠΌΠ° ΠΈ Π¨ΡƒΠ±Π°, Π° Ρ‚Π°ΠΊ ΠΆΠ΅ счётчики с криптографичСскими Ρ…Π΅Ρˆ-функциями ΠΈΠ»ΠΈ криптостойкими Π±Π»ΠΎΡ‡Π½Ρ‹ΠΌΠΈ ΡˆΠΈΡ„Ρ€Π°ΠΌΠΈ вмСсто Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π²Ρ‹Π²ΠΎΠ΄Π°.

АппаратныС Π“ΠŸΠ‘Π§

ΠšΡ€ΠΎΠΌΠ΅ ΡƒΡΡ‚Π°Ρ€Π΅Π²ΡˆΠΈΡ…, Ρ…ΠΎΡ€ΠΎΡˆΠΎ извСстных LFSR-Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ², ΡˆΠΈΡ€ΠΎΠΊΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΠ²ΡˆΠΈΡ…ΡΡ Π² качСствС Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Ρ… Π“ΠŸΠ‘Π§ Π² XX Π²Π΅ΠΊΠ΅, ΠΊ соТалСнию, ΠΎΡ‡Π΅Π½ΡŒ ΠΌΠ°Π»ΠΎ извСстно ΠΎ соврСмСнных Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Ρ… Π“ΠŸΠ‘Π§ (ΠΏΠΎΡ‚ΠΎΡ‡Π½Ρ‹Ρ… ΡˆΠΈΡ„Ρ€Π°Ρ…), Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ ΠΈΠ· Π½ΠΈΡ… Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Π°Π½ΠΎ для Π²ΠΎΠ΅Π½Π½Ρ‹Ρ… Ρ†Π΅Π»Π΅ΠΉ ΠΈ дСрТатся Π² сСкрСтС. ΠŸΠΎΡ‡Ρ‚ΠΈ всС ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ коммСрчСскиС Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Π΅ Π“ΠŸΠ‘Π§ Π·Π°ΠΏΠ°Ρ‚Π΅Π½Ρ‚ΠΎΠ²Π°Π½Ρ‹ ΠΈ Ρ‚Π°ΠΊΠΆΠ΅ дСрТатся Π² сСкрСтС. АппаратныС Π“ΠŸΠ‘Π§ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½Ρ‹ строгими трСбованиями ΠΊ расходуСмой памяти (Ρ‡Π°Ρ‰Π΅ всСго использованиС памяти Π·Π°ΠΏΡ€Π΅Ρ‰Π΅Π½ΠΎ), Π±Ρ‹ΡΡ‚Ρ€ΠΎΠ΄Π΅ΠΉΡΡ‚Π²ΠΈΡŽ (1-2 Ρ‚Π°ΠΊΡ‚Π°) ΠΈ ΠΏΠ»ΠΎΡ‰Π°Π΄ΠΈ (нСсколько сотСн FPGA- ΠΈΠ»ΠΈ

Из-Π·Π° нСдостатка Ρ…ΠΎΡ€ΠΎΡˆΠΈΡ… Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Ρ… Π“ΠŸΠ‘Π§ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΠΈ Π²Ρ‹Π½ΡƒΠΆΠ΄Π΅Π½Ρ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠ΅ΡΡ ΠΏΠΎΠ΄ Ρ€ΡƒΠΊΠΎΠΉ Π³ΠΎΡ€Π°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ ΠΌΠ΅Π΄Π»Π΅Π½Π½Ρ‹Π΅, Π½ΠΎ ΡˆΠΈΡ€ΠΎΠΊΠΎ извСстныС Π±Π»ΠΎΡ‡Π½Ρ‹Π΅ ΡˆΠΈΡ„Ρ€Ρ‹ (

ΠŸΡ€ΠΈΠΌΠ΅Ρ‡Π°Π½ΠΈΡ

Π‘ΠΌ. Ρ‚Π°ΠΊΠΆΠ΅

Бсылки

Π›ΠΈΡ‚Π΅Ρ€Π°Ρ‚ΡƒΡ€Π°

ПолСзноС

Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ‡Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ «Π”Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл» Π² Π΄Ρ€ΡƒΠ³ΠΈΡ… словарях:

Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл β€” Аппаратно Ρ€Π΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π½ΠΎΠ΅ устройство (элСмСнт, Π±Π»ΠΎΠΊ), ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½Π½ΠΎΠ΅ для Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ случайных Π±ΠΈΡ‚ΠΎΠ²Ρ‹Ρ… ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ, ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‰ΠΈΡ… Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹ΠΌΠΈ свойствами равновСроятности ΠΏΠΎΡ€ΠΎΠΆΠ΄Π°Π΅ΠΌΠΎΠΉ ΠΊΠ»ΡŽΡ‡Π΅Π²ΠΎΠΉ Π³Π°ΠΌΠΌΡ‹. [Π”ΠΎΠΌΠ°Ρ€Π΅Π² Π’.Π’. Π‘Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΡΡ‚ΡŒ информационных… … Π‘ΠΏΡ€Π°Π²ΠΎΡ‡Π½ΠΈΠΊ тСхничСского ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Ρ‡ΠΈΠΊΠ°

Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл β€” Π£Π·Π΅Π» Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ слуТит для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ случайных чисСл … ΠŸΠΎΠ»ΠΈΡ‚Π΅Ρ…Π½ΠΈΡ‡Π΅ΡΠΊΠΈΠΉ тСрминологичСский Ρ‚ΠΎΠ»ΠΊΠΎΠ²Ρ‹ΠΉ ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ

Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных Π²Π΅Π»ΠΈΡ‡ΠΈΠ½ β€” Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ случайных чисСл Устройство ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°, ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½Π½Ρ‹Π΅ для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ случайных чисСл ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡƒ Π·Π°ΠΊΠΎΠ½Ρƒ распрСдСлСния вСроятностСй ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. [http://slovar lopatnikov.ru/] ВСматики… … Π‘ΠΏΡ€Π°Π²ΠΎΡ‡Π½ΠΈΠΊ тСхничСского ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Ρ‡ΠΈΠΊΠ°

Π”Π°Ρ‚Ρ‡ΠΈΠΊ случайных Π²Π΅Π»ΠΈΡ‡ΠΈΠ½ β€” [random number generator] Ρ‚ΠΎ ΠΆΠ΅: Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл, Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ случайных чисСл устройство ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°, ΠΏΡ€Π΅Π΄Π½Π°Π·Π½Π°Ρ‡Π΅Π½Π½Ρ‹Π΅ для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ случайных чисСл ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡƒ Π·Π°ΠΊΠΎΠ½Ρƒ распрСдСлСния вСроятностСй ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ … Π­ΠΊΠΎΠ½ΠΎΠΌΠΈΠΊΠΎ-матСматичСский ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ

Π‘Π»ΡƒΡ‡Π°ΠΉΠ½Ρ‹Ρ… чисСл Π΄Π°Ρ‚Ρ‡ΠΈΠΊ β€” устройство для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ случайных чисСл, Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎ распрСдСлённых Π² Π·Π°Π΄Π°Π½Π½ΠΎΠΌ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ чисСл. ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΠ΅Ρ‚ΡΡ для ΠΈΠΌΠΈΡ‚Π°Ρ†ΠΈΠΈ Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… условий функционирования систСм автоматичСского управлСния, для Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ статистичСских… … Π‘ΠΎΠ»ΡŒΡˆΠ°Ρ совСтская энциклопСдия

БЛУЧАЙНЫΠ₯ Π§Π˜Π‘Π•Π› Π”ΠΠ’Π§Π˜Πš β€” устройство для Π²Ρ‹Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ случайных чисСл, Ρ€Π°Π²Π½ΠΎΠΌΠ΅Ρ€Π½ΠΎ распрСдСлённых Π² Π·Π°Π΄Π°Π½Π½ΠΎΠΌ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅. ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΠ΅Ρ‚ΡΡ для ΠΈΠΌΠΈΡ‚Π°Ρ†ΠΈΠΈ Ρ€Π΅Π°Π»ΡŒΠ½Ρ‹Ρ… условий функционирования систСм Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚ΠΈΡ‡. управлСния, ΠΏΡ€ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠΈ Π½Π° Π­Π’Πœ Π·Π°Π΄Π°Ρ‡ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ статистич. испытаний (Ρ‚. Π½.… … Π‘ΠΎΠ»ΡŒΡˆΠΎΠΉ энциклопСдичСский политСхничСский ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ

Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ случайных чисСл β€” Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл β€” [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Π’Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠΈ Π·Π°Ρ‰ΠΈΡ‚Π° ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ Π‘ΠΈΠ½ΠΎΠ½ΠΈΠΌΡ‹ Π΄Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл EN random number generatorrandom number generator … Π‘ΠΏΡ€Π°Π²ΠΎΡ‡Π½ΠΈΠΊ тСхничСского ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄Ρ‡ΠΈΠΊΠ°

Π”Π°Ρ‚Ρ‡ΠΈΠΊ β€” ΠΏΠ΅Ρ€Π²ΠΈΡ‡Π½Ρ‹ΠΉ ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒ, элСмСнт ΠΈΠ·ΠΌΠ΅Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ, сигнального, Ρ€Π΅Π³ΡƒΠ»ΠΈΡ€ΡƒΡŽΡ‰Π΅Π³ΠΎ ΠΈΠ»ΠΈ ΡƒΠΏΡ€Π°Π²Π»ΡΡŽΡ‰Π΅Π³ΠΎ устройства систСмы, ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΡƒΡŽΡ‰ΠΈΠΉ ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΠΈΡ€ΡƒΠ΅ΠΌΡƒΡŽ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρƒ (Π΄Π°Π²Π»Π΅Π½ΠΈΠ΅, Ρ‚Π΅ΠΌΠΏΠ΅Ρ€Π°Ρ‚ΡƒΡ€Ρƒ, частоту, ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ, ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Ρ‰Π΅Π½ΠΈΠ΅, напряТСниС, элСктричСский Ρ‚ΠΎΠΊ … Π‘ΠΎΠ»ΡŒΡˆΠ°Ρ совСтская энциклопСдия

АппаратноС ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ β€” АппаратноС ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ процСсс ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΠΌΡ‹ΠΉ ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ спСциализированных Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… устройств. Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅ 1 Π’Π²Π΅Π΄Π΅Π½ΠΈΠ΅ 2 Достоинства ΠΈ нСдостатки Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½ΠΎΠ³ΠΎ ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ … ВикипСдия

ΠœΠ΅Ρ‚ΠΎΠ΄ Π€ΠΈΠ±ΠΎΠ½Π°Ρ‡Ρ‡ΠΈ с запаздываниями β€” (Lagged Fibonacci generator) ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ псСвдослучайных чисСл. ΠžΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΠΈ распрСдСлСния случайных чисСл, Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΠ΅ΠΌΡ‹Ρ… Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌ конгруэнтным Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ, Π΄Π΅Π»Π°ΡŽΡ‚ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹ΠΌ ΠΈΡ… использованиС Π² статистичСских Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ…, Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‰ΠΈΡ…β€¦ … ВикипСдия

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π“Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ случайных чисСл Π² Ρ€Π°Π·Π½Ρ‹Ρ… ОБ

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Как-Ρ‚ΠΎ ΠΏΠΎΠ·Π΄Π½ΠΈΠΌ Π»Π΅Ρ‚Π½ΠΈΠΌ Π²Π΅Ρ‡Π΅Ρ€ΠΎΠΌ ΠΌΠ½Π΅ ΠΏΡ€ΠΈΡˆΠ»ΠΎΡΡŒ Ρ€Π°Π·ΠΎΠ±Ρ€Π°Ρ‚ΡŒΡΡ, ΠΊΠ°ΠΊ устроСны Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ случайных чисСл Π² Windows ΠΈ Linux. БобствСнно, Π² этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ я ΠΏΠΎΠΏΡ€ΠΎΠ±ΡƒΡŽ привСсти ΡΠ°ΠΊΠΊΡƒΠΌΡƒΠ»ΠΈΡ€ΠΎΠ²Π°Π½Π½ΡƒΡŽ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ, ΠΈ прСподнСсти Π΅Π΅ максимально простыми словами, Π±Π΅Π· нСобходимости Π»Π΅Π·Ρ‚ΡŒ Π² исходники, Ρ‚ΡƒΡ‚ΠΎΡ€ΠΈΠ°Π»Ρ‹ ΠΈ ΡΡ‚Π°Ρ‚ΡŒΠΈ.

Π“Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ псСвдослучайных чисСл

Π‘ Ρ€Π°Π·Π²ΠΈΡ‚ΠΈΠ΅ΠΌ Ρ‚Π΅Ρ…Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ ΠΈ бСзопасности ΠΌΡ‹ всС большС ΠΈ большС нуТдаСмся Π² Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ случайных числах, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ нСльзя Π±Ρ‹Π»ΠΎ Π±Ρ‹ ΠΏΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Ρ‚ΡŒ ΠΈΠ·Π²Π½Π΅. ΠŸΠΎΡ‡Π΅ΠΌΡƒ? Π’ ΠΏΠ΅Ρ€Π²ΡƒΡŽ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΡŒ ΠΈΠ·-Π·Π° ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΡ, вСдь с ΠΊΠ°ΠΆΠ΄Ρ‹ΠΌ Π³ΠΎΠ΄ΠΎΠΌ растСт количСство пСрСсылаСмого Ρ‚Ρ€Π°Ρ„ΠΈΠΊΠ°, ΠΈ ΠΏΡ€ΠΈ этом хочСтся ΠΈΠΌΠ΅Ρ‚ΡŒ Π΄ΠΎΡΡ‚Π°Ρ‚ΠΎΡ‡Π½ΡƒΡŽ ΡΡ‚Π΅ΠΏΠ΅Π½ΡŒ бСзопасности Π½Π°ΡˆΠΈΡ… Π΄Π°Π½Π½Ρ‹Ρ…. И Π²ΠΎΡ‚ Π² Ρ‚ΠΎΡ‚ ΠΌΠΎΠΌΠ΅Π½Ρ‚, ΠΊΠΎΠ³Π΄Π° Π½ΡƒΠΆΠ½ΠΎ ΡΠ³Π΅Π½Π΅Ρ€ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ случайноС число, Ρƒ Π½Π°ΡˆΠΈΡ… ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ΠΎΠ² Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ½ΠΈ созданы Π±Ρ‹Ρ‚ΡŒ максимально ΠΏΠΎΡΠ»ΡƒΡˆΠ½Ρ‹ΠΌΠΈ, прСдсказуСмыми ΠΈ Π΄Π΅Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹ΠΌΠΈ для Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ всС Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ ΠΏΡ€ΠΈ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Ρ… Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… Π²ΠΎΡΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΠ»ΠΈΡΡŒ, ΠΈΠ½Π°Ρ‡Π΅ Π±Ρ‹ вСсь ΠΌΠΈΡ€ развалился.

НСмного ΠΏΡ€ΠΎ ΡΠ½Ρ‚Ρ€ΠΎΠΏΠΈΡŽ

Код ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠΈΠ²Π°Π½ΠΈΡ Π² ChaCha

Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ ΠΊΠ»ΡŽΡ‡Π° K ΠΈ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ Π²Π΅ΠΊΡ‚ΠΎΡ€Π° V ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° обновлСния ΠΈ Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…;

Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΡ‹Ρ… псСвдослучайных чисСл, происходит ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ счСтчика, ΠΏΡ€ΠΈ этом счСтчик инкрСмСнтируСтся послС ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ шага. Π‘Π°ΠΌΠΎ ΡˆΠΈΡ„Ρ€ΠΎΠ²Π°Π½ΠΈΠ΅ происходит ΠΏΡ€ΠΈ ΠΏΠΎΠΌΠΎΡ‰ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° AES с сгСнСрированным ΠΊΠ»ΡŽΡ‡ΠΎΠΌ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ этот Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ лишСн нСобходимости Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠΈΠ²Π°Π½ΠΈΡ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния послС ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ обращСния, ΠΊΠ°ΠΊ это Π±Ρ‹Π»ΠΎ Π² ChaCha.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² информатикСАлгоритм обновлСния Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ Π²Ρ‹Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…

Π‘Π»ΡƒΡ‡Π°ΠΉΠ½Ρ‹Π΅ события

Linux

ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ ΠΏΡ€Π°Π²ΠΈΠ»Π° Π²Ρ‹Π±ΠΎΡ€Π° событий, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Ρ€Π°ΡΡ†Π΅Π½ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΊΠ°ΠΊ случайныС. Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, эти события Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ Π½Π΅Π΄Π΅Ρ‚Π΅Ρ€ΠΌΠΈΠ½ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅. Π’ΠΎ-Π²Ρ‚ΠΎΡ€Ρ‹Ρ…, ΠΈΡ… Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±Ρ‹Ρ‚ΡŒ тяТСло ΠΏΡ€ΠΎΠ½Π°Π±Π»ΡŽΠ΄Π°Ρ‚ΡŒ ΠΈΠ·Π²Π½Π΅. Π­Ρ‚ΠΈ случайныС события Π΄ΠΎΠ±Π°Π²Π»ΡΡŽΡ‚ΡΡ Π² ΠΏΡƒΠ» энтропии (просто массив чисСл), ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠΈΠ²Π°ΡΡΡŒ с Π΅Π³ΠΎ содСрТимым с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠΉ CRC-ΠΏΠΎΠ΄ΠΎΠ±Π½ΠΎΠΉ Ρ…ΡΡˆ-Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ. Она выполняСтся быстро, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π΅Π΅ ΠΌΠΎΠΆΠ½ΠΎ Π±Ρ‹Π»ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ послС ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΡƒΡŽΡ‰Π΅Π³ΠΎ события Π² систСмС, ΠΈ достаточно Ρ…ΠΎΡ€ΠΎΡˆΠ°, Ссли ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ случайныС события Π·Π°ΠΏΠΎΠ»Π½ΡΡŽΡ‚ ΠΏΡƒΠ» Π½Π΅ врСдоносным ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ. ΠŸΡ€ΠΈ этом ΠΏΡ€ΠΈ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ события Π² ΠΏΡƒΠ», происходит ΡƒΡ‡Π΅Ρ‚ ΠΏΡ€ΠΈΠ±Ρ‹Π²ΡˆΠ΅Π³ΠΎ количСства энтропии.

Π’ Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ 4 Ρ‚ΠΈΠΏΠ° источников случайных событий:

Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡ ΠΎΡ‚ устройств, которая Π΄ΠΎΠ»ΠΆΠ½Π° Π±Ρ‹Ρ‚ΡŒ Ρ€Π°Π·Π½ΠΎΠΉ Π½Π° физичСски Ρ€Π°Π·Π½Ρ‹Ρ… ΠΌΠ°ΡˆΠΈΠ½Π°Ρ…, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€ MAC адрСс сСтСвой ΠΊΠ°Ρ€Ρ‚Ρ‹. ЀактичСски, это Π½Π΅ добавляСт энтропии систСмС, Π½ΠΎ позволяСт Π² ΠΎΡ‡Π΅Π½ΡŒ ΠΏΠ»ΠΎΡ…ΠΈΡ… случаях (запуск с ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΎΠ±Ρ€Π°Π·Π°) Π½Π° Ρ€Π°Π·Π½Ρ‹Ρ… устройствах ΠΏΠΎΠ»ΡƒΡ‡Π°Ρ‚ΡŒ Ρ€Π°Π·Π½Ρ‹Π΅ состояния;

Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡ ΠΎΡ‚ Ρ‚Π°ΠΉΠΌΠ΅Ρ€Π°, прСрывания, Ρ‚ΠΈΠΏΠ° прСрывания, значСния;

Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡ ΠΎ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ поиска Π±Π»ΠΎΠΊΠ° Π½Π° дискС. Однако Π½Π° соврСмСнных SSD это достаточно ΠΏΠ»ΠΎΡ…ΠΎΠΉ источник случайности, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Ρƒ Π½ΠΈΡ… врСмя поиска ΡΡ€Π°Π²Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ малСнькоС ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠ΅ всСгда.

Π§Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΠ»ΠΈ ΠΏΠ΅Ρ€Π΅ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π“ΠŸΠ‘Π§, Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΠ· ΠΏΡƒΠ»Π° энтропии Π΄ΠΎΡΡ‚Π°Ρ‚ΡŒ нСсколько случайных Π±Π°ΠΉΡ‚. Для этого, вСсь ΠΏΡƒΠ» Ρ…ΡΡˆΠΈΡ€ΡƒΠ΅Ρ‚ΡΡ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ SHA-1, Π° Ρ…ΡΡˆ-сумма выдаСтся ΠΊΠ°ΠΊ случайный Π½Π°Π±ΠΎΡ€ Π±ΠΈΡ‚. ΠŸΡ€ΠΈ этом ΠΏΡ€Π΅Π΄ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°ΡŽΡ‚ΡΡ ΠΌΠ΅Ρ€Ρ‹ для обСспСчСния бСзопасности Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° Π² Π±ΡƒΠ΄ΡƒΡ‰Π΅ΠΌ. Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Ρ…ΡΡˆΠΈΡ€ΠΎΠ²Π°Π½ΠΈΡ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠΈΠ²Π°Π΅Ρ‚ΡΡ с ΠΏΡƒΠ»ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΠΎ Π²Ρ‹Ρ…ΠΎΠ΄Π½ΠΎΠΌΡƒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ нСльзя Π±Ρ‹Π»ΠΎ Π²ΠΎΡΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π΅ состояниС. Π’ΠΎ-Π²Ρ‚ΠΎΡ€Ρ‹Ρ…, происходит постоянная ΠΎΡ†Π΅Π½ΠΊΠ° ΠΎΡΡ‚Π°Π²ΡˆΠ΅Π³ΠΎΡΡ количСства энтропии Π² ΠΏΡƒΠ»Π΅.

Windows

Π’ качСствС источников энтропии Π² Windows ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ:

Как ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Hyper-V ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с Windows прСдоставляСт Ρ‚Π°ΠΊΠΈΠ΅ ΡƒΠ»ΡƒΡ‡ΡˆΠ΅Π½ΠΈΡ. МногиС Π³ΠΈΠΏΠ΅Ρ€Π²ΠΈΠ·ΠΎΡ€Ρ‹ «ΠΏΡ€ΠΈΠΊΠΈΠ΄Ρ‹Π²Π°ΡŽΡ‚ся» Hyper-V, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΠ²Π°Ρ‚ΡŒ Ρ‚Π°ΠΊΠΎΠΉ ΠΆΠ΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π» ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ встроСнныС возмоТности ΠΏΠΎ ΠΏΠΎΠ²Ρ‹ΡˆΠ΅Π½ΠΈΡŽ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с Windows.

Π’ΠΎ врСмя старта систСмы Π΄Π°Π½Π½Ρ‹Π΅ с 7 источников (Seed Ρ„Π°ΠΉΠ», внСшняя энтропия, TPM, RDRAND, ACPI-OEM0, UEFI ΠΈ врСмя старта) Ρ…ΡΡˆΠΈΡ€ΡƒΡŽΡ‚ΡΡ SHA-512 ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ для ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ SP800-90 AES-CTR-DRBG. Π£ΠΆΠ΅ Π²ΠΎ врСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ систСмы, Π΄Π°Π½Π½Ρ‹Π΅ прСдоставлСнныС источником, ΠΏΠΎΠΌΠ΅Ρ‰Π°ΡŽΡ‚ΡΡ Π² ΠΏΡƒΠ» (Π·Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ Ρ€Π°Π·Π°, ΠΊΠΎΠ³Π΄Π° ΠΎΠ½ΠΈ ΠΈΠ΄ΡƒΡ‚ сразу Π½Π° ΠΏΠ΅Ρ€Π΅ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ ΠΊΠΎΡ€Π½Π΅Π²ΠΎΠ³ΠΎ Π“ΠŸΠ‘Π§).

Π—Π°ΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅

Как ΠΌΠΎΠΆΠ½ΠΎ Π±Ρ‹Π»ΠΎ Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, ΠΌΠ½ΠΎΠ³ΠΈΠ΅ источники случайных событий связаны с Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΌ состояниСм ΠΌΠ°ΡˆΠΈΠ½Ρ‹, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΈ Π²ΠΈΡ€Ρ‚ΡƒΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΌΠΎΠ³ΡƒΡ‚ Π½Π°Ρ‡Π°Ρ‚ΡŒΡΡ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹. Π’ Linux Π² коммСнтариях ΠΊ ΠΊΠΎΠ΄Ρƒ ΠΈΠ½ΠΎΠ³Π΄Π° ΠΎΡ‚ΠΊΡ€Ρ‹Ρ‚ΠΎ признаСтся эта ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ°. Π’ Windows с Hyper-V (ΠΈΠ»ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌ Π³ΠΈΠΏΠ΅Ρ€Π²ΠΈΠ·ΠΎΡ€ΠΎΠΌ, «ΠΏΡ€ΠΈΠΊΠΈΠ΄Ρ‹Π²Π°ΡŽΡ‰ΠΈΠΌΡΡ» ΠΈΠΌ) ΠΏΡ‹Ρ‚Π°ΡŽΡ‚ΡΡ с этим Π±ΠΎΡ€ΠΎΡ‚ΡŒΡΡ, Π½ΠΎ сама ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° всС ΠΆΠ΅ ΠΈΠ½ΠΎΠ³Π΄Π° проявляСтся. Битуация нСсколько облСгчаСтся, Ρ‚Π΅ΠΌ Ρ„Π°ΠΊΡ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ Π² соврСмСнных процСссорах Π΅ΡΡ‚ΡŒ «ΠΆΠ΅Π»Π΅Π·Π½Ρ‹Π΅» Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ случайных чисСл, Π° Ρ‚Π°ΠΊ ΠΆΠ΅ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ Π²ΠΈΡ€Ρ‚ΡƒΠ°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΠ΄ΡΠΎΠ²Ρ‹Π²Π°ΡŽΡ‚ случайныС числа хостовой ОБ гостСвой. Π’Π΅Π΄ΡŒ нСльзя ΠΎΡΡ‚Π°Π²Π»ΡΡ‚ΡŒ это Π½Π° волю случая.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

ΠŸΠΎΠ΄Ρ€ΠΎΠ±Π½ΠΎ ΠΎ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°Ρ… случайных ΠΈ псСвдослучайных чисСл

Π’Π²Π΅Π΄Π΅Π½ΠΈΠ΅

Как ΠΎΡ‚Π»ΠΈΡ‡ΠΈΡ‚ΡŒ ΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΡƒΡŽ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ чисСл ΠΎΡ‚ нСслучайной?

Π§ΡƒΡ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ слоТный ΠΏΡ€ΠΈΠΌΠ΅Ρ€ ΠΈΠ»ΠΈ число Пи

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅
ΠŸΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Ρ†ΠΈΡ„Ρ€Ρ‹ Π² числС Пи считаСтся случайной. ΠŸΡƒΡΡ‚ΡŒ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ основываСтся Π½Π° Π²Ρ‹Π²ΠΎΠ΄Π΅ Π±ΠΈΡ‚ прСдставлСния числа Пи, начиная с ΠΊΠ°ΠΊΠΎΠΉ-Ρ‚ΠΎ нСизвСстной Ρ‚ΠΎΡ‡ΠΊΠΈ. Π’Π°ΠΊΠΎΠΉ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ ΠΈ ΠΏΡ€ΠΎΠΉΠ΄Π΅Ρ‚ «тСст Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π±ΠΈΡ‚Β», Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ПИ, Π²ΠΈΠ΄ΠΈΠΌΠΎ, являСтся случайной ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ. Однако этот ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ Π½Π΅ являСтся критографичСски Π½Π°Π΄Π΅ΠΆΠ½Ρ‹ΠΌ β€” Ссли ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ°Π½Π°Π»ΠΈΡ‚ΠΈΠΊ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚, ΠΊΠ°ΠΊΠΎΠΉ Π±ΠΈΡ‚ числа Пи ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Π² Π΄Π°Π½Π½Ρ‹ΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚, ΠΎΠ½ смоТСт Π²Ρ‹Ρ‡ΠΈΡΠ»ΠΈΡ‚ΡŒ ΠΈ всС ΠΏΡ€Π΅Π΄ΡˆΠ΅ΡΡ‚Π²ΡƒΡŽΡ‰ΠΈΠ΅ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ Π±ΠΈΡ‚Ρ‹.
Π”Π°Π½Π½Ρ‹ΠΉ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Π½Π°ΠΊΠ»Π°Π΄Ρ‹Π²Π°Π΅Ρ‚ Π΅Ρ‰Ρ‘ ΠΎΠ΄Π½ΠΎ ΠΎΠ³Ρ€Π°Π½ΠΈΡ‡Π΅Π½ΠΈΠ΅ Π½Π° Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ случайных чисСл. ΠšΡ€ΠΈΠΏΡ‚ΠΎΠ°Π½Π°Π»ΠΈΡ‚ΠΈΠΊ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠΌΠ΅Ρ‚ΡŒ возмоТности ΠΏΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Ρ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° случайных чисСл.

ΠžΡ‚Π»ΠΈΡ‡ΠΈΠ΅ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° псСвдослучайных чисСл (Π“ΠŸΠ‘Π§) ΠΎΡ‚ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° случайных чисСл (Π“Π‘Π§)

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊΠΈ энтропии ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ для накоплСния энтропии с ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΏΠΎΠ»ΡƒΡ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΈΠ· Π½Π΅Ρ‘ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ значСния (initial value, seed), Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΠ³ΠΎ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π°ΠΌ случайных чисСл (Π“Π‘Π§) для формирования случайных чисСл. Π“ΠŸΠ‘Π§ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ СдинствСнноС Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, ΠΎΡ‚ΠΊΡƒΠ΄Π° ΠΈ слСдуСт Π΅Π³ΠΎ ΠΏΡΠ΅Π²Π΄ΠΎΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΠΎΡΡ‚ΡŒ, Π° Π“Π‘Π§ всСгда Ρ„ΠΎΡ€ΠΌΠΈΡ€ΡƒΠ΅Ρ‚ случайноС число, имСя Π² Π½Π°Ρ‡Π°Π»Π΅ Π²Ρ‹ΡΠΎΠΊΠΎΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ ΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΡƒΡŽ Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρƒ, ΠΏΡ€Π΅Π΄ΠΎΡΡ‚Π°Π²Π»Π΅Π½Π½ΡƒΡŽ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹ΠΌΠΈ источниками энтропии.
Энтропия – это ΠΌΠ΅Ρ€Π° бСспорядка. Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½Π°Ρ энтропия β€” ΠΌΠ΅Ρ€Π° нСопрСдСлённости ΠΈΠ»ΠΈ нСпрСдсказуСмости ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ.
МоТно ΡΠΊΠ°Π·Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π“Π‘Π§ = Π“ΠŸΠ‘Π§ + источник энтропии.

Уязвимости Π“ΠŸΠ‘Π§

Π›ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ конгруэнтный Π“ΠŸΠ‘Π§ (LCPRNG)

Распространённый ΠΌΠ΅Ρ‚ΠΎΠ΄ для Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ псСвдослучайных чисСл, Π½Π΅ ΠΎΠ±Π»Π°Π΄Π°ΡŽΡ‰ΠΈΠΉ криптографичСской ΡΡ‚ΠΎΠΉΠΊΠΎΡΡ‚ΡŒΡŽ. Π›ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ конгруэнтный ΠΌΠ΅Ρ‚ΠΎΠ΄ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² вычислСнии Ρ‡Π»Π΅Π½ΠΎΠ² Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠΉ Ρ€Π΅ΠΊΡƒΡ€Ρ€Π΅Π½Ρ‚Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΏΠΎ ΠΌΠΎΠ΄ΡƒΠ»ΡŽ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ числа m, Π·Π°Π΄Π°Π²Π°Π΅ΠΌΠΎΠΉ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»ΠΎΠΉ:

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π³Π΄Π΅ a (multiplier), c (addend), m (mask) β€” Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ цСлочислСнныС коэффициСнты. ΠŸΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌΠ°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ зависит ΠΎΡ‚ Π²Ρ‹Π±ΠΎΡ€Π° стартового числа (seed) X0 ΠΈ ΠΏΡ€ΠΈ Ρ€Π°Π·Π½Ρ‹Ρ… Π΅Π³ΠΎ значСниях ΠΏΠΎΠ»ΡƒΡ‡Π°ΡŽΡ‚ΡΡ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ случайных чисСл.

Для Π²Ρ‹Π±ΠΎΡ€Π° коэффициСнтов ΠΈΠΌΠ΅ΡŽΡ‚ΡΡ свойства ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‰ΠΈΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π΄Π»ΠΈΠ½Ρƒ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄Π°(максимальная Π΄Π»ΠΈΠ½Π° Ρ€Π°Π²Π½Π° m), Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΌΠΎΠΌΠ΅Π½Ρ‚, с ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ зациклится [1].

ΠŸΡƒΡΡ‚ΡŒ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ Π²Ρ‹Π΄Π°Π» нСсколько случайных чисСл X0, X1, X2, X3. ΠŸΠΎΠ»ΡƒΡ‡Π°Π΅Ρ‚ΡΡ систСма ΡƒΡ€Π°Π²Π½Π΅Π½ΠΈΠΉ

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

РСшив эту систСму, ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ коэффициСнты a, c, m. Как ΡƒΡ‚Π²Π΅Ρ€ΠΆΠ΄Π°Π΅Ρ‚ википСдия [8], эта систСма ΠΈΠΌΠ΅Π΅Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅, Π½ΠΎ Ρ€Π΅ΡˆΠΈΡ‚ΡŒ ΡΠ°ΠΌΠΎΡΡ‚ΠΎΡΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΈΠ»ΠΈ Π½Π°ΠΉΡ‚ΠΈ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ Π½Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΎΡΡŒ. Π‘ΡƒΠ΄Ρƒ ΠΎΡ‡Π΅Π½ΡŒ ΠΏΡ€ΠΈΠ·Π½Π°Ρ‚Π΅Π»Π΅Π½ Π·Π° Π»ΡŽΠ±ΡƒΡŽ ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² этом Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠΈ.

ΠŸΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Π½ΠΈΠ΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-конгруэнтного ΠΌΠ΅Ρ‚ΠΎΠ΄Π°

ΠžΡΠ½ΠΎΠ²Π½Ρ‹ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ прСдсказания чисСл для Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-конгруэнтного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° являСтся Plumstead’s β€” Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ здСсь [4](Π΅ΡΡ‚ΡŒ ΠΎΠ½Π»Π°ΠΉΠ½ запуск) ΠΈ здСсь [5]. ОписаниС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π² [9].
ΠŸΡ€ΠΎΡΡ‚Π°Ρ рСализация конгруэнтного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Π½Π° Java.

ΠžΡ‚ΠΏΡ€Π°Π²ΠΈΠ² 20 чисСл Π½Π° сайт [4], ΠΌΠΎΠΆΠ½ΠΎ с большой Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅. Π§Π΅ΠΌ большС чисСл, Ρ‚Π΅ΠΌ большС Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒ.

Π’Π·Π»ΠΎΠΌ встроСнного Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° случайных чисСл Π² Java

МногиС языки программирования, Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€ C(rand), C++(rand) ΠΈ Java ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ LΠ‘PRNG. Рассмотрим, ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ провСсти Π²Π·Π»ΠΎΠΌ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π΅ java.utils.Random. Зайдя Π² исходный ΠΊΠΎΠ΄ (jdk1.7) Π΄Π°Π½Π½ΠΎΠ³ΠΎ класса ΠΌΠΎΠΆΠ½ΠΎ ΡƒΠ²ΠΈΠ΄Π΅Ρ‚ΡŒ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ константы

ΠœΠ΅Ρ‚ΠΎΠ΄ java.utils.Randon.nextInt() выглядит ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ (здСсь bits == 32)

Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ являСтся nextseed сдвинутый Π²ΠΏΡ€Π°Π²ΠΎ Π½Π° 48-32=16 Π±ΠΈΡ‚. Π”Π°Π½Π½Ρ‹ΠΉ ΠΌΠ΅Ρ‚ΠΎΠ΄ называСтся truncated-bits, особСнно нСприятСн ΠΏΡ€ΠΈ black-box, приходится Π΄ΠΎΠ±Π°Π²Π»ΡΡ‚ΡŒ Π΅Ρ‰Ρ‘ ΠΎΠ΄ΠΈΠ½ Ρ†ΠΈΠΊΠ» Π² brute-force. Π’Π·Π»ΠΎΠΌ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΡΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π³Ρ€ΡƒΠ±ΠΎΠΉ силы(brute-force).

ΠŸΡƒΡΡ‚ΡŒ ΠΌΡ‹ Π·Π½Π°Π΅ΠΌ Π΄Π²Π° подряд сгСнСрированных числа x1 ΠΈ x2. Π’ΠΎΠ³Π΄Π° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠ΅Ρ€Π΅Π±Ρ€Π°Ρ‚ΡŒ 2^16 = 65536 Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² oldseed ΠΈ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡ‚ΡŒ ΠΊ x1 Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ:

Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° ΠΎΠ½Π° Π½Π΅ станСт Ρ€Π°Π²Π½ΠΎΠΉ x2. Код для brute-force ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Ρ‚Π°ΠΊ

Π’Ρ‹Π²ΠΎΠ΄ Π΄Π°Π½Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΈΠΌΠ΅Ρ€Π½ΠΎ Ρ‚Π°ΠΊΠΈΠΌ:

НСслоТно ΠΏΠΎΠ½ΡΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ нашли Π½Π΅ самый ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ seed, Π° seed, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹ΠΉ ΠΏΡ€ΠΈ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ числа. Для нахоТдСния ΠΏΠ΅Ρ€Π²ΠΎΠ½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ seed Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ провСсти нСсколько ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Java использовала для прСобразования seed, Π² ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠΌ порядкС.

И Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Π² исходном ΠΊΠΎΠ΄Π΅ Π·Π°ΠΌΠ΅Π½ΠΈΠΌ
crackingSeed.set(seed);
Π½Π°
crackingSeed.set(getPreviousSeed(seed));

И всё, ΠΌΡ‹ ΡƒΡΠΏΠ΅ΡˆΠ½ΠΎ Π²Π·Π»ΠΎΠΌΠ°Π»ΠΈ Π“ΠŸΠ‘Π§ Π² Java.

Π’Π·Π»ΠΎΠΌ Π“ΠŸΠ‘Π§ Mersenne twister Π² PHP

Рассмотрим Π΅Ρ‰Ρ‘ ΠΎΠ΄ΠΈΠ½ Π½Π΅ криптостойкий Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ псСвдослучайных чисСл Mersenne Twister. ΠžΡΠ½ΠΎΠ²Π½Ρ‹Π΅ прСимущСства Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° β€” это ΡΠΊΠΎΡ€ΠΎΡΡ‚ΡŒ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΈ ΠΎΠ³Ρ€ΠΎΠΌΠ½Ρ‹ΠΉ ΠΏΠ΅Ρ€ΠΈΠΎΠ΄ 2^19937 βˆ’ 1, На этот Ρ€Π°Π· Π±ΡƒΠ΄Π΅ΠΌ Π°Π½Π°Π»ΠΈΠ·ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° mt_srand() ΠΈ mt_rand() Π² исходном ΠΊΠΎΠ΄Π΅ php вСрсии 5.4.6.

МоТно Π·Π°ΠΌΠ΅Ρ‚ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ php_mt_reload вызываСтся ΠΏΡ€ΠΈ ΠΈΠ½ΠΈΡ†ΠΈΠ°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈ послС Π²Ρ‹Π·ΠΎΠ²Π° php_mt_rand 624 Ρ€Π°Π·Π°. НачнСм Π²Π·Π»ΠΎΠΌ с ΠΊΠΎΠ½Ρ†Π°, ΠΎΠ±Ρ€Π°Ρ‚ΠΈΠΌ трансформации Π² ΠΊΠΎΠ½Ρ†Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). Π’ Π±ΠΈΠ½Π°Ρ€Π½ΠΎΠΌ прСдставлСниС опСрация выглядит Ρ‚Π°ΠΊ:

10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Π’ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ ΠΏΠ΅Ρ€Π²Ρ‹Π΅ 18 Π±ΠΈΡ‚ (Π²Ρ‹Π΄Π΅Π»Π΅Π½Ρ‹ ΠΆΠΈΡ€Π½Ρ‹ΠΌ) ΠΎΡΡ‚Π°Π»ΠΈΡΡŒ Π±Π΅Π· ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΉ.
НапишСм Π΄Π²Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ для инвСртирования Π±ΠΈΡ‚ΠΎΠ²ΠΎΠ³ΠΎ сдвига ΠΈ xor

Π’ΠΎΠ³Π΄Π° ΠΊΠΎΠ΄ для инвСртирования послСдних строк Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ php_mt_rand() Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ Ρ‚Π°ΠΊ

Если Ρƒ нас Π΅ΡΡ‚ΡŒ 624 ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… числа сгСнСрированных Mersenne Twister, Ρ‚ΠΎ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠ² этот Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для этих ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Ρ… чисСл, ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠΌ ΠΏΠΎΠ»Π½ΠΎΠ΅ состояниС Mersenne Twister, ΠΈ смоТСм Π»Π΅Π³ΠΊΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅Π΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, запустив php_mt_reload для извСстного Π½Π°Π±ΠΎΡ€Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ.

ΠžΠ±Π»Π°ΡΡ‚ΡŒ для Π²Π·Π»ΠΎΠΌΠ°

Если Π²Ρ‹ Π΄ΡƒΠΌΠ°Π΅Ρ‚Π΅, Ρ‡Ρ‚ΠΎ ΡƒΠΆΠ΅ Π½Π΅Ρ‡Π΅Π³ΠΎ Π»ΠΎΠΌΠ°Ρ‚ΡŒ, Ρ‚ΠΎ Π’Ρ‹ Π³Π»ΡƒΠ±ΠΎΠΊΠΎ Π·Π°Π±Π»ΡƒΠΆΠ΄Π°Π΅Ρ‚Π΅ΡΡŒ. Одним ΠΈΠ· интСрСсных Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π½ΠΈΠΉ являСтся Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ случайных чисСл Adobe Flash(Action Script 3.0). Π•Π³ΠΎ ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎΡΡ‚ΡŒΡŽ являСтся Π·Π°ΠΊΡ€Ρ‹Ρ‚ΠΎΡΡ‚ΡŒ исходного ΠΊΠΎΠ΄Π° ΠΈ отсутствиС задания seed’Π°. Основной интСрСс ΠΊ Π½Π΅ΠΌΡƒ, это использованиС Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΈΡ… ΠΎΠ½Π»Π°ΠΉΠ½-ΠΊΠ°Π·ΠΈΠ½ΠΎ ΠΈ ΠΎΠ½Π»Π°ΠΉΠ½-ΠΏΠΎΠΊΠ΅Ρ€Π΅.
Π•ΡΡ‚ΡŒ ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚Π΅ΠΉ чисСл, начиная ΠΎΡ‚ курса Π΄ΠΎΠ»Π»Π°Ρ€Π° ΠΈ заканчивая количСством Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ ΠΏΡ€ΠΎΠ²Π΅Π΄Π΅Π½Π½Ρ‹ΠΌ Π² ΠΏΡ€ΠΎΠ±ΠΊΠ΅ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ дСнь. И Π½Π°ΠΉΡ‚ΠΈ Π·Π°ΠΊΠΎΠ½ΠΎΠΌΠ΅Ρ€Π½ΠΎΡΡ‚ΡŒ Π² Ρ‚Π°ΠΊΠΈΡ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΡ‡Π΅Π½ΡŒ Π½Π΅ простая Π·Π°Π΄Π°Ρ‡Π°.

Π—Π°Π΄Π°Π½ΠΈΠ΅ распрСдСлСния для Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€Π° псСвдослучайных чисСл

Для любой случайной Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρ‹ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°Π΄Π°Ρ‚ΡŒ распрСдСлСниС. ΠŸΠ΅Ρ€Π΅Π½ΠΎΡΡ Π½Π° ΠΏΡ€ΠΈΠΌΠ΅Ρ€ с ΠΊΠ°Ρ€Ρ‚Π°ΠΌΠΈ, ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ‚ΡƒΠ·Ρ‹ Π²Ρ‹ΠΏΠ°Π΄Π°Π»ΠΈ Ρ‡Π°Ρ‰Π΅, Ρ‡Π΅ΠΌ дСвятки. Π”Π°Π»Π΅Π΅ прСдставлСны нСсколько ΠΏΡ€ΠΈΠΌΠ΅Ρ€ΠΎΠ² для Ρ‚Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΎΠ³ΠΎ распрСдСлСния ΠΈ ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ распрСдСлСния.

Π’Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΎΠ΅ распрСдСлСниС

ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅ΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ случайной Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρ‹ с Ρ‚Ρ€Π΅ΡƒΠ³ΠΎΠ»ΡŒΠ½Ρ‹ΠΌ распрСдСлСниСм [7] Π½Π° языкС C99.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π­ΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ распрСдСлСниС

ВСсты Π“ΠŸΠ‘Π§

НСкоторыС Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ ΡΡ‡ΠΈΡ‚Π°ΡŽΡ‚, Ρ‡Ρ‚ΠΎ Ссли ΠΎΠ½ΠΈ ΡΠΊΡ€ΠΎΡŽΡ‚ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹ΠΉ ΠΈΠΌΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ ΠΈΠ»ΠΈ ΠΏΡ€ΠΈΠ΄ΡƒΠΌΠ°ΡŽΡ‚ свой, Ρ‚ΠΎ этого достаточно для Π·Π°Ρ‰ΠΈΡ‚Ρ‹. Π­Ρ‚ΠΎ ΠΎΡ‡Π΅Π½ΡŒ распространённоС Π·Π°Π±Π»ΡƒΠΆΠ΄Π΅Π½ΠΈΠ΅. Π‘Π»Π΅Π΄ΡƒΠ΅Ρ‚ ΠΏΠΎΠΌΠ½ΠΈΡ‚ΡŒ, Ρ‡Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΠΈ ΠΏΡ€ΠΈΠ΅ΠΌΡ‹ для поиска зависимостСй Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ чисСл.

Одним ΠΈΠ· извСстных тСстов являСтся тСст Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π±ΠΈΡ‚ β€” тСст, слуТащий для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² псСвдослучайных чисСл Π½Π° ΠΊΡ€ΠΈΠΏΡ‚ΠΎΡΡ‚ΠΎΠΉΠΊΠΎΡΡ‚ΡŒ. ВСст гласит, Ρ‡Ρ‚ΠΎ Π½Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ полиномиального Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ, зная ΠΏΠ΅Ρ€Π²Ρ‹Π΅ k Π±ΠΈΡ‚ΠΎΠ² случайной ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ, смоТСт ΠΏΡ€Π΅Π΄ΡΠΊΠ°Π·Π°Ρ‚ΡŒ k+1 Π±ΠΈΡ‚ с Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ большСй Β½.

Π’ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎΠΉ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠΎΠΉ являСтся ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΠ³ΠΎ, насколько ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ чисСл ΠΈΠ»ΠΈ Π±ΠΈΡ‚, сгСнСрированных Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠΌ, являСтся случайной. Как ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ, для этой Ρ†Π΅Π»ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ статистичСскиС тСсты, Ρ‚Π°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ DIEHARD ΠΈΠ»ΠΈ NIST. Π­Π½Π΄Ρ€ΡŽ Π―ΠΎ Π² 1982 Π³ΠΎΠ΄Ρƒ Π΄ΠΎΠΊΠ°Π·Π°Π», Ρ‡Ρ‚ΠΎ Π³Π΅Π½Π΅Ρ€Π°Ρ‚ΠΎΡ€, ΠΏΡ€ΠΎΡˆΠ΅Π΄ΡˆΠΈΠΉ «тСст Π½Π° ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΉ Π±ΠΈΡ‚Β», ΠΏΡ€ΠΎΠΉΠ΄Π΅Ρ‚ ΠΈ Π»ΡŽΠ±Ρ‹Π΅ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ статистичСскиС тСсты Π½Π° ΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΠΎΡΡ‚ΡŒ, Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΠΌΡ‹Π΅ Π·Π° полиномиальноС врСмя.
Π’ ΠΈΠ½Ρ‚Π΅Ρ€Π½Π΅Ρ‚Π΅ [10] ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡ€ΠΎΠΉΡ‚ΠΈ тСсты DIEHARD ΠΈ мноТСство Π΄Ρ€ΡƒΠ³ΠΈΡ…, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΊΡ€ΠΈΡ‚ΠΎΡΡ‚ΠΎΠΉΠΊΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π‘ΠΎΠ΄Π΅Ρ€ΠΆΠ°Π½ΠΈΠ΅ ΡƒΡ€ΠΎΠΊΠ°

ΠŸΠΎΠ½ΡΡ‚ΠΈΠ΅ случайного числа

Β§ 19. Одна Π·Π°Π΄Π°Ρ‡Π° ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ массива
ΠŸΠΎΠ½ΡΡ‚ΠΈΠ΅ случайного числа

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

РСшим ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ. Массив заполняСтся случайным Π½Π°Π±ΠΎΡ€ΠΎΠΌ Ρ†Π΅Π»Ρ‹Ρ… чисСл. НуТно ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, сколько Ρ€Π°Π· Π΄Π°Π½Π½ΠΎΠ΅ Ρ†Π΅Π»ΠΎΠ΅ число Π²Ρ…ΠΎΠ΄ΠΈΡ‚ Π² этот массив.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа

Π‘Π½Π°Ρ‡Π°Π»Π° нСсколько слов ΠΎ случайных числах. ВсС сСбС ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²Π»ΡΡŽΡ‚ ΠΈΠ³Ρ€Π°Π»ΡŒΠ½Ρ‹ΠΉ ΠΊΡƒΠ±ΠΈΠΊ, ΠΈΠΌΠ΅ΡŽΡ‰ΠΈΠΉ ΡˆΠ΅ΡΡ‚ΡŒ Π³Ρ€Π°Π½Π΅ΠΉ. ΠŸΡ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ бросании ΠΊΡƒΠ±ΠΈΠΊΠ° Π²Ρ‹ΠΏΠ°Π΄Π΅Π½ΠΈΠ΅ ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Ρ‚ΠΎ числа Π΅ΡΡ‚ΡŒ случайноС событиС. Π‘ Ρ€Π°Π²Π½ΠΎΠΉ Π²Π΅Ρ€ΠΎΡΡ‚Π½ΠΎΡΡ‚ΡŒΡŽ ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠ°ΡΡ‚ΡŒ любоС число ΠΎΡ‚ 1 Π΄ΠΎ 6. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ бросания ΠΊΡƒΠ±ΠΈΠΊΠ° β€” это случайноС число. А Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΠΏΡ€Π΅Π΄ΡΡ‚Π°Π²ΡŒΡ‚Π΅ сСбС ΠΊΡƒΠ±ΠΈΠΊ с 10 гранями. ΠŸΡ€Π°Π²Π΄Π°, ΠΊΡƒΠ±ΠΈΠΊΠΎΠΌ Π΅Π³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π½Π°Π·Π²Π°Ρ‚ΡŒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ условно. Π­Ρ‚ΠΎ дСсятигранник, Π½Π° гранях ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ нанСсСны числа ΠΎΡ‚ 1 Π΄ΠΎ 10. Π Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ бросания Ρ‚Π°ΠΊΠΎΠ³ΠΎ Β«ΠΊΡƒΠ±ΠΈΠΊΠ°Β» β€” случайноС число Π² Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π΅ ΠΎΡ‚ 1 Π΄ΠΎ 10. Π•Ρ‰Π΅ ΠΎΠ΄ΠΈΠ½ ΠΏΡ€ΠΈΠΌΠ΅Ρ€. ΠŸΡ€ΠΈ Ρ€ΠΎΠ·Ρ‹Π³Ρ€Ρ‹ΡˆΠ΅ Π»ΠΎΡ‚Π΅Ρ€Π΅ΠΈ ΠΈΠ· Π²Ρ€Π°Ρ‰Π°ΡŽΡ‰Π΅Π³ΠΎΡΡ Π±Π°Ρ€Π°Π±Π°Π½Π° Π΄ΠΎΡΡ‚Π°ΡŽΡ‚ ΠΏΡ€ΠΎΠ½ΡƒΠΌΠ΅Ρ€ΠΎΠ²Π°Π½Π½Ρ‹Π΅ ΡˆΠ°Ρ€Ρ‹. Π’Ρ‹ΠΏΠ°Π²ΡˆΠΈΠΉ Π½ΠΎΠΌΠ΅Ρ€ ΡˆΠ°Ρ€Π° β€” случайноС число.

Π”Π°Ρ‚Ρ‡ΠΈΠΊ случайных чисСл Π½Π° ПаскалС

ΠŸΡ€ΠΈΠ²Π΅Π΄Π΅ΠΌ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ, которая дСмонстрируСт Ρ€Π°Π±ΠΎΡ‚Ρƒ Π΄Π°Ρ‚Ρ‡ΠΈΠΊΠ° случайных чисСл Π½Π° ПаскалС:

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

По этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ Π½Π° экран выводится Π΄Π΅ΡΡΡ‚ΡŒ случайных чисСл ΠΈΠ· Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½Π° ΠΎΡ‚ 0 Π΄ΠΎ 50. Π’ΠΎΡ‚ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ тСстового выполнСния этой ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹:

0 3 17 20 27 7 31 16 37 42

А Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ вСрнСмся ΠΊ ΡƒΡΠ»ΠΎΠ²ΠΈΡŽ Π·Π°Π΄Π°Ρ‡ΠΈ. ΠŸΠΎΠ»ΡƒΡ‡Π°ΡŽΡ‰ΠΈΠ΅ΡΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ Π΄Π°Ρ‚Ρ‡ΠΈΠΊΠ° случайныС числа Β«Ρ€Π°ΡΠΊΠ»Π°Π΄Ρ‹Π²Π°ΡŽΡ‚ΡΡΒ» ΠΏΠΎ элСмСнтам массива. НазовСм массив Rand, Π° число элСмСнтов Π² Π½Π΅ΠΌ ΠΏΡƒΡΡ‚ΡŒ Π±ΡƒΠ΄Π΅Ρ‚ Ρ€Π°Π²Π½ΠΎ 20. Число, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π½ΡƒΠΆΠ½ΠΎ ΠΈΡΠΊΠ°Ρ‚ΡŒ Π² массивС, Π±ΡƒΠ΄Π΅Ρ‚ Π²Π²ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π² ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ X.

Алгоритм поиска числа Π² массивС

На рисункС 2.11 ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Π° Π±Π»ΠΎΠΊ-схСма Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° поиска Π² массивС Rand Π²Π΅Π»ΠΈΡ‡ΠΈΠ½Ρ‹ X с подсчСтом числа Π΅Π΅ Π²Ρ…ΠΎΠΆΠ΄Π΅Π½ΠΈΠΉ Π² массив Π² ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎΠΉ NumberX.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

ΠžΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° Π±Π»ΠΎΠΊ, ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ°ΡŽΡ‰ΠΈΠΉ Ρ†ΠΈΠΊΠ» с ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠΌ. Он ΠΈΠΌΠ΅Π΅Ρ‚ Ρ„ΠΎΡ€ΠΌΡƒ вытянутого ΡˆΠ΅ΡΡ‚ΠΈΡƒΠ³ΠΎΠ»ΡŒΠ½ΠΈΠΊΠ°. Π’ Π±Π»ΠΎΠΊΠ΅ записываСтся ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ Ρ†ΠΈΠΊΠ»Π° (пСрСмСнная I), Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ ΠΈ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ значСния ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π° Ρ‡Π΅Ρ€Π΅Π· Π·Π°ΠΏΡΡ‚ΡƒΡŽ (:=1, 20).

ΠŸΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Π°Ρ NumberX ΠΈΠ³Ρ€Π°Π΅Ρ‚ Ρ€ΠΎΠ»ΡŒ счСтчика. Π’Π½Π°Ρ‡Π°Π»Π΅ Π΅ΠΉ присваиваСтся ноль. Π—Π°Ρ‚Π΅ΠΌ Π² Ρ†ΠΈΠΊΠ»Π΅ происходит ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ всСх элСмСнтов массива, ΠΈ ΠΏΡ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ условия равСнства ΠΊ счСтчику добавляСтся Π΅Π΄ΠΈΠ½ΠΈΡ†Π°. Π’Π°ΠΊ всСгда ΠΎΡ€Π³Π°Π½ΠΈΠ·ΡƒΡŽΡ‚ΡΡ счСтчики Π² ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°Ρ…! Π’ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ выполнСния ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π° экран Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π²Π΅Π΄Π΅Π½ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π΄Π²ΡƒΡ… Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ΠΎΠ² ΠΎΡ‚Π²Π΅Ρ‚Π°: Π»ΠΈΠ±ΠΎ сообщСниС, Ρ‡Ρ‚ΠΎ Π² массивС Π½Π΅Ρ‚ Π΄Π°Π½Π½ΠΎΠ³ΠΎ числа, Π»ΠΈΠ±ΠΎ сообщСниС ΠΎ Ρ‚ΠΎΠΌ, сколько Ρ€Π°Π· это число присутствуСт Π² массивС, Ссли ΠΎΠ½ΠΎ Ρ‚Π°ΠΌ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΎ.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π‘Π»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ страница Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅Β§ 19. Одна Π·Π°Π΄Π°Ρ‡Π° ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ массива. ΠŸΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° поиска числа Π² массивС

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Как ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΠ΅Ρ‚ случайныС числа

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ ΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΠΎΡΡ‚ΡŒ Π² ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€Π΅? Как происходит гСнСрация случайных чисСл? Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ ΠΏΠΎΡΡ‚Π°Ρ€Π°Π»ΠΈΡΡŒ Π΄Π°Ρ‚ΡŒ простыС ΠΎΡ‚Π²Π΅Ρ‚Ρ‹ Π½Π° эти вопросы.

Π’ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ½ΠΎΠΌ обСспСчСнии, Π΄Π° ΠΈ Π² Ρ‚Π΅Ρ…Π½ΠΈΠΊΠ΅ Π² Ρ†Π΅Π»ΠΎΠΌ сущСствуСт Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒ Π² воспроизводимой случайности: числа ΠΈ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠΈ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ каТутся случайными, Π½Π° самом Π΄Π΅Π»Π΅ сгСнСрированы ΠΎΠΏΡ€Π΅Π΄Π΅Π»Ρ‘Π½Π½Ρ‹ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ. Π­Ρ‚ΠΎ называСтся ΠΏΡΠ΅Π²Π΄ΠΎΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΠΎΡΡ‚ΡŒΡŽ, ΠΈ ΠΌΡ‹ рассмотрим простыС способы создания псСвдослучайных чисСл. Π’ ΠΊΠΎΠ½Ρ†Π΅ ΡΡ‚Π°Ρ‚ΡŒΠΈ ΠΌΡ‹ сформулируСм ΠΏΡ€ΠΎΡΡ‚ΡƒΡŽ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡƒ для создания этих, казалось Π±Ρ‹, случайных чисСл.

ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ ΠΈΠΌΠ΅Π½Π½ΠΎ являСтся ΡΠ»ΡƒΡ‡Π°ΠΉΠ½ΠΎΡΡ‚ΡŒΡŽ, ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ довольно слоТной Π·Π°Π΄Π°Ρ‡Π΅ΠΉ. Π‘ΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ тСсты (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, колмогоровская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ), ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠ³ΡƒΡ‚ Π΄Π°Ρ‚ΡŒ Π²Π°ΠΌ Ρ‚ΠΎΡ‡Π½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Ρ‚ΠΎΠ³ΠΎ, насколько случайна Ρ‚Π° ΠΈΠ»ΠΈ иная ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ. Но ΠΌΡ‹ Π½Π΅ Π±ΡƒΠ΄Π΅ΠΌ Π·Π°ΠΌΠΎΡ€Π°Ρ‡ΠΈΠ²Π°Ρ‚ΡŒΡΡ, Π° просто ΠΏΠΎΠΏΡ€ΠΎΠ±ΡƒΠ΅ΠΌ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ чисСл, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ ΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ нСсвязанными ΠΌΠ΅ΠΆΠ΄Ρƒ собой.

Часто трСбуСтся Π½Π΅ просто ΠΎΠ΄Π½ΠΎ число, Π° нСсколько случайных чисСл, Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΡŽΠ΅ΠΌΡ‹Ρ… Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΠΎ. Π‘Π»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, учитывая Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Π½Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ случайныС числа. Π­Ρ‚ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ называСтся сСмСнСм, ΠΈ ΠΏΠΎΠ·ΠΆΠ΅ ΠΌΡ‹ ΡƒΠ²ΠΈΠ΄ΠΈΠΌ, ΠΊΠ°ΠΊ Π΅Π³ΠΎ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ. А ΠΏΠΎΠΊΠ° Π΄Π°Π²Π°ΠΉΡ‚Π΅ сконцСнтрируСмся Π½Π° создании Π΄Ρ€ΡƒΠ³ΠΈΡ… случайных Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ.

Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ случайных чисСл ΠΈΠ· сСмСни

Один ΠΈΠ· ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² ΠΌΠΎΠΆΠ΅Ρ‚ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Ρ‚ΡŒΡΡ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΡ‚ΡŒ ΠΊΠ°ΠΊΡƒΡŽ-Ρ‚ΠΎ Π±Π΅Π·ΡƒΠΌΠ½ΡƒΡŽ ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΡ‡Π΅ΡΠΊΡƒΡŽ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ ΠΊ сСмСни, Π° Π·Π°Ρ‚Π΅ΠΌ ΠΈΡΠΊΠ°Π·ΠΈΡ‚ΡŒ Π΅Ρ‘ Π½Π°ΡΡ‚ΠΎΠ»ΡŒΠΊΠΎ, Ρ‡Ρ‚ΠΎ число Π½Π° Π²Ρ‹Ρ…ΠΎΠ΄Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ нСпрСдсказуСмым, Π° послС Π²Π·ΡΡ‚ΡŒ Π΅Π³ΠΎ ΠΊΠ°ΠΊ сСмя для ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ. Вопрос Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² Ρ‚ΠΎΠΌ, ΠΊΠ°ΠΊ Π΄ΠΎΠ»ΠΆΠ½Π° Π²Ρ‹Π³Π»ΡΠ΄Π΅Ρ‚ΡŒ эта функция искаТСния.

Π”Π°Π²Π°ΠΉΡ‚Π΅ поэкспСримСнтируСм с этой ΠΈΠ΄Π΅Π΅ΠΉ ΠΈ посмотрим, ΠΊΡƒΠ΄Π° ΠΎΠ½Π° нас ΠΏΡ€ΠΈΠ²Π΅Π΄Ρ‘Ρ‚.

Ѐункция искаТСния Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΈΠ½ΠΈΠΌΠ°Ρ‚ΡŒ ΠΎΠ΄Π½ΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Π° Π²ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ΠΎΠ΅. Назовём Π΅Ρ‘ R.

Числовой ΠΊΡ€ΡƒΠ³

ΠŸΠΎΡΠΌΠΎΡ‚Ρ€ΠΈΠΌ Π½Π° Ρ†ΠΈΡ„Π΅Ρ€Π±Π»Π°Ρ‚ часов: наш ряд начинаСтся с 1 ΠΈ ΠΈΠ΄Ρ‘Ρ‚ ΠΏΠΎ ΠΊΡ€ΡƒΠ³Ρƒ Π΄ΠΎ 12. Но ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΌΡ‹ Ρ€Π°Π±ΠΎΡ‚Π°Π΅ΠΌ с ΠΊΠΎΠΌΠΏΡŒΡŽΡ‚Π΅Ρ€ΠΎΠΌ, ΠΏΡƒΡΡ‚ΡŒ вмСсто 12 Π±ΡƒΠ΄Π΅Ρ‚ 0.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Ρ„ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π‘ΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ ΠΊΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΡƒ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. ΠšΠ°Ρ€Ρ‚ΠΈΠ½ΠΊΠ° ΠΏΡ€ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅. Π€ΠΎΡ‚ΠΎ Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ случайныС числа Π² ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠ΅

Π’Π΅ΠΏΠ΅Ρ€ΡŒ начиная с 1 снова Π±ΡƒΠ΄Π΅ΠΌ ΠΏΡ€ΠΈΠ±Π°Π²Π»ΡΡ‚ΡŒ 7. ΠŸΡ€ΠΎΠ³Ρ€Π΅ΡΡ! ΠœΡ‹ Π²ΠΈΠ΄ΠΈΠΌ, Ρ‡Ρ‚ΠΎ послС 12 наш ряд Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚ ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡ‚ΡŒΡΡ, нСзависимо ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, с ΠΊΠ°ΠΊΠΎΠ³ΠΎ числа Π½Π°Ρ‡Π°Ρ‚ΡŒ.

Π—Π΄Π΅ΡΡŒ ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΎΡ‡Π΅Π½ΡŒ Π²Π°ΠΆΠ½ΠΎ свойство: Ссли наш Ρ†ΠΈΠΊΠ» состоит ΠΈΠ· n элСмСнтов, Ρ‚ΠΎ максимальноС число элСмСнтов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΡ‹ ΠΌΠΎΠΆΠ΅ΠΌ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ ΠΏΠ΅Ρ€Π΅Π΄ Ρ‚Π΅ΠΌ, ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ Π½Π°Ρ‡Π½ΡƒΡ‚ ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡ‚ΡŒΡΡ это n.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ Π΄Π°Π²Π°ΠΉΡ‚Π΅ ΠΏΠ΅Ρ€Π΅Π΄Π΅Π»Π°Π΅ΠΌ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ R Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ½Π° соотвСтствовала нашСй Π»ΠΎΠ³ΠΈΠΊΠ΅. ΠžΠ³Ρ€Π°Π½ΠΈΡ‡ΠΈΡ‚ΡŒ Π΄Π»ΠΈΠ½Ρƒ Ρ†ΠΈΠΊΠ»Π° ΠΌΠΎΠΆΠ½ΠΎ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° модуля ΠΈΠ»ΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° остатка ΠΎΡ‚ дСлСния.

Если Π²Ρ‹ ΠΏΠΎΠΏΡ€ΠΎΠ±ΡƒΠ΅Ρ‚Π΅ нСсколько Ρ€Π°Π·Π½Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Ρ‚ΠΎ смоТСтС ΡƒΠ²ΠΈΠ΄Π΅Ρ‚ΡŒ ΠΎΠ΄Π½ΠΎ свойство: m ΠΈ с Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ Π²Π·Π°ΠΈΠΌΠ½ΠΎ простыми.

Π”ΠΎ сих ΠΏΠΎΡ€ ΠΌΡ‹ Π΄Π΅Π»Π°Π»ΠΈ «ΠΏΡ€Ρ‹ΠΆΠΊΠΈ» Π·Π° счёт добавлСния, Π½ΠΎ Ρ‡Ρ‚ΠΎ Ссли ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΡƒΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅? Π£ΠΌΠ½ΠΎΠΆΠΈΠΌ Ρ… Π½Π° константу a.

Бвойства, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΏΠΎΠ΄Ρ‡ΠΈΠ½ΡΡ‚ΡŒΡΡ Π°, Ρ‡Ρ‚ΠΎΠ±Ρ‹ образовался ΠΏΠΎΠ»Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ», Π½Π΅ΠΌΠ½ΠΎΠ³ΠΎ Π±ΠΎΠ»Π΅Π΅ спСцифичны. Π§Ρ‚ΠΎΠ±Ρ‹ ΡΠΎΠ·Π΄Π°Ρ‚ΡŒ Π²Π΅Ρ€Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ»:

Π­Ρ‚ΠΈ свойства вмСстС с ΠΏΡ€Π°Π²ΠΈΠ»ΠΎΠΌ, Ρ‡Ρ‚ΠΎ m ΠΈ с Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π±Ρ‹Ρ‚ΡŒ Π²Π·Π°ΠΈΠΌΠ½ΠΎ простыми ΡΠΎΡΡ‚Π°Π²Π»ΡΡŽΡ‚ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡƒ Π₯Π°Π»Π»Π°-Π”ΠΎΠ±Π΅Π»Π»Π°. ΠœΡ‹ Π½Π΅ Π±ΡƒΠ΄Π΅ΠΌ Ρ€Π°ΡΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ Π΅Ρ‘ Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ, Π½ΠΎ Ссли Π±Ρ‹ Π²Ρ‹ взяли ΠΊΡƒΡ‡Ρƒ Ρ€Π°Π·Π½Ρ‹Ρ… Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ для Ρ€Π°Π·Π½Ρ‹Ρ… констант, Ρ‚ΠΎ ΠΌΠΎΠ³Π»ΠΈ Π±Ρ‹ ΠΏΡ€ΠΈΠΉΡ‚ΠΈ ΠΊ Ρ‚ΠΎΠΌΡƒ ΠΆΠ΅ Π²Ρ‹Π²ΠΎΠ΄Ρƒ.

Π’Ρ‹Π±ΠΎΡ€ сСмСни

Настало врСмя ΠΏΠΎΠ³ΠΎΠ²ΠΎΡ€ΠΈΡ‚ΡŒ ΠΎ самом интСрСсном: Π²Ρ‹Π±ΠΎΡ€Π΅ ΠΏΠ΅Ρ€Π²ΠΎΠ½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ сСмСни. ΠœΡ‹ ΠΌΠΎΠ³Π»ΠΈ Π±Ρ‹ ΡΠ΄Π΅Π»Π°Ρ‚ΡŒ Π΅Π³ΠΎ константой. Π­Ρ‚ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΡ€ΠΈΠ³ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π² Ρ‚Π΅Ρ… случаях, ΠΊΠΎΠ³Π΄Π° Π²Π°ΠΌ Π½ΡƒΠΆΠ½Ρ‹ случайныС числа, Π½ΠΎ ΠΏΡ€ΠΈ этом Π½ΡƒΠΆΠ½ΠΎ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€ΠΈ ΠΊΠ°ΠΆΠ΄ΠΎΠΌ запускС ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΎΠ½ΠΈ Π±Ρ‹Π»ΠΈ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹Π΅. НапримСр, созданиС ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΉ ΠΊΠ°Ρ€Ρ‚Ρ‹ для ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ³Ρ€Ρ‹.

ΠšΠΎΠ½Π΅Ρ‡Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚

Когда ΠΌΡ‹ примСняСм Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ ΠΊ Π΅Ρ‘ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρƒ нСсколько Ρ€Π°Π·, ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ Ρ€Π΅ΠΊΡƒΡ€Ρ€Π΅Π½Ρ‚Π½ΠΎΠ΅ ΡΠΎΠΎΡ‚Π½ΠΎΡˆΠ΅Π½ΠΈΠ΅. Π”Π°Π²Π°ΠΉΡ‚Π΅ запишСм Π½Π°ΡˆΡƒ Ρ„ΠΎΡ€ΠΌΡƒΠ»Ρƒ с использованиСм рСкурсии:

Π’ΠΎ, Ρ‡Ρ‚ΠΎ ΠΌΡ‹ сдСлали, называСтся Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΌ конгруэнтным ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ. Он ΠΎΡ‡Π΅Π½ΡŒ часто ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ ΠΎΠ½ прост Π² Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ ΠΈ вычислСния Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ быстро.

Π’ Ρ€Π°Π·Π½Ρ‹Ρ… языках программирования рСализация Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ конгруэнтного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° отличаСтся, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ значСния констант. НапримСр, функция случайных чисСл Π² libc (стандартная Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° Π‘ для Linux) ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ m = 2 ^ 32, a = 1664525 ΠΈ c = 1013904223. Π’Π°ΠΊΠΈΠ΅ компиляторы, ΠΊΠ°ΠΊ gcc, ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ эти значСния.

Π—Π°ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ замСчания

Π‘ΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ Π³Π΅Π½Π΅Ρ€Π°Ρ†ΠΈΠΈ случайных чисСл, Π½ΠΎ Π»ΠΈΠ½Π΅ΠΉΠ½Ρ‹ΠΉ конгруэнтный ΠΌΠ΅Ρ‚ΠΎΠ΄ считаСтся классичСским ΠΈ Π»Ρ‘Π³ΠΊΠΈΠΌ для понимания. Если Π²Ρ‹ Ρ…ΠΎΡ‚ΠΈΡ‚Π΅ Π³Π»ΡƒΠ±ΠΆΠ΅ ΠΈΠ·ΡƒΡ‡ΠΈΡ‚ΡŒ Π΄Π°Π½Π½ΡƒΡŽ Ρ‚Π΅ΠΌΡƒ, Ρ‚ΠΎ ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚Π΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° ΠΊΠ½ΠΈΠ³Ρƒ Random Numbers Generators, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½Ρ‹ элСгантныС Π΄ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²Π° Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎΠ³ΠΎ конгруэнтного ΠΌΠ΅Ρ‚ΠΎΠ΄Π°.

ГСнСрация случайных чисСл ΠΈΠΌΠ΅Π΅Ρ‚ мноТСство ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΉ Π² области ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ‚ΠΈΠΊΠΈ ΠΈ особСнно Π²Π°ΠΆΠ½Π° для ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ³Ρ€Π°Ρ„ΠΈΠΈ.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ

Π’Π°Ρˆ адрСс email Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½. ΠžΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ поля ΠΏΠΎΠΌΠ΅Ρ‡Π΅Π½Ρ‹ *