Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 95
The Top Ten Algorithms of the Century
5. the Fortran compiler, developed by a team lead by John Backus;
5. the Fortran compiler, developed by a team lead by John Backus;
Вот, да, кстати.
Буду признателен, если кто-нибудь расскажет, что в этом компиляторе такого особенного.
Буду признателен, если кто-нибудь расскажет, что в этом компиляторе такого особенного.
Может это потому, что это был первый компилятор, в котором использовался анализатор на основе BNF, насколько я понимаю?
Для своего времени компилятор был революционным. Как с точки зрения внутреннего устройства, так и с точки зрения пользователя. Насколько я помню, это был первый компилятор с «нормальными» сообщениям об ошибках в виде сообщения, а не номера, который нужно искать в мануале.
Это первый компилятор языка высокого уровня. До этого были только ассемблеры.
А этот алгоритм на другие иррациональные числа перекладывается?
Отличное практическое применение вышеупомянутого алгоритма: πfs! Давно перенес на нее всю свою коллекцию фильмов.
Чёрт, мы пару дней назад взялись за реализацию подобного.
А оказывается, всё уже придумали до нас!
Практического применения этому, конечно, никакого, но весело!
Если мы всё же доделаем свой вариант, имеет смысл статью об этом писать? Интересно будет? Или не очень?
А оказывается, всё уже придумали до нас!
Практического применения этому, конечно, никакого, но весело!
Если мы всё же доделаем свой вариант, имеет смысл статью об этом писать? Интересно будет? Или не очень?
Пишите, конечно. Интересно будет почитать.
В связи с ухудшающейся общемировой ситуацией, связанной с копирайтами и последствиями его нарушения, предлагаю simple yet brilliant идею — Offline Torrents Downloader!
Суть очень проста — для скачивания каждого блока достаточно просто найти последовательность в π с требуемым хэшем! Доступ к интернету? Зачем, ведь есть Offline Torrents Downloader — и пусть копираст докажет, что ты что-то откуда-то скачал!
Суть очень проста — для скачивания каждого блока достаточно просто найти последовательность в π с требуемым хэшем! Доступ к интернету? Зачем, ведь есть Offline Torrents Downloader — и пусть копираст докажет, что ты что-то откуда-то скачал!
Когда я последний раз изучал вопрос, скорость этой ФС еще не позволяла записывать туда фильмы. Это тонкий сарказм, или неожиданный прорыв в скорости поиска чанков?
Да сарказм, очевидно же. Туда мегабайт будет «писаться» не один час на Core i7.
Это почему же на порядки больше? В среднем, того же объёма. Иногда больше, иногда меньше.
Согласен с вами до фразы «Почему-то я уверен». Это заблуждение сродни тому, что вероятность выигрыша лотерейного билета номер 123456 ниже, чем 593742.
Для иллюстрации попробуйте поискать в числе Пи, например, ABC и 7F3. Да и любые данные, которые выглядят более-менее осмысленными и сравните со «случайными».
Для иллюстрации попробуйте поискать в числе Пи, например, ABC и 7F3. Да и любые данные, которые выглядят более-менее осмысленными и сравните со «случайными».
Обалдеть какая красивая формула
Красивая? Женись.
Действительно, редкой красоты формула. Вспомнилась, кстати сразу античная (!) 22/7
> Учитывая, что Пи — это иррациональное число, то есть, в его записи каждая следующая цифра непредсказуема,…
Довольно сомнительный вывод. Что вы понимаете под непредсказуемостью, и как это следует из иррациональности?
Довольно сомнительный вывод. Что вы понимаете под непредсказуемостью, и как это следует из иррациональности?
Наверное, неправильно сформулировал.
Я имею в виду то, что любой случайно взятый знак дробной части числа Пи может с равной вероятностью оказаться любой цифрой от 0 до 9 (или, в случае с HEX-ом, от 0 до F).
Я имею в виду то, что любой случайно взятый знак дробной части числа Пи может с равной вероятностью оказаться любой цифрой от 0 до 9 (или, в случае с HEX-ом, от 0 до F).
Да, неверно. Это — не непредсказуемость. И более того, совершенно не следует из иррациональности. Например, число 1.10100100010000100001 и т.д. иррациональное, хотя распределение цифр далеко от равномерного.
Спасибо, вы правы, отредактировал.
Если бы распределение в таких числах было хорошим, генераторы случайных чисел для криптографии были бы в разы проще.
Не факт. Допустим они абсолютно случайные.
Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.
Ну и как такую случайность использовать в генераторе случайных чисел в криптографии?
Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.
Ну и как такую случайность использовать в генераторе случайных чисел в криптографии?
Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например. Естественно, это очень упрощенный пример.
хм. верно.
С другой стороны такое может не подойти из-за вот этого требования
ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D1%81%D1%82%D0%BE%D0%B9%D0%BA%D0%B8%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
Т.е. если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа), то и вся последовательность становится известной.
Пусть генератор основывается на выводе бит какого-то представления числа Пи, начиная с какой то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью (это было бы гарантированно, если доказать что Пи является нормальным числом). Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.
ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D1%81%D1%82%D0%BE%D0%B9%D0%BA%D0%B8%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
Т.е. если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа), то и вся последовательность становится известной.
Если вы перехватили часть последовательности гаммы(потока бит числа Пи в данном случае), то это не дает вам возможность найти следующие биты. Данное условие направлено было исходя из того, что алгоритм генерации — конечный автомат и по N отсчетам (n1,n2...nN) можно найти текущее состояние генератора. В случае же числа Пи сколько угодно отсчетов можете взять и это не поможет: существует бесконечно много отсчетов вида (n1,n2...nN,l1,l2....lL), т.е. включающих в себя выбранный.
Другими словами скомпрометированный кусок может продолжаться бесконечным числом способов.
Другими словами скомпрометированный кусок может продолжаться бесконечным числом способов.
Здесь речь про другое:
если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.
если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа)
Я как раз и отмечаю, что второе утверждение неверно: часть полученной последовательности не дает знания порядкового номера.
Здесь нигде не идёт речь про узнавание порядкового номера, с помощью полученной последовательности.
Речь просто про узнавание порядкового номера. Не важно каким путём.
Речь просто про узнавание порядкового номера. Не важно каким путём.
next-bit тест будет тем не менее пройден.
pS. вот бы для всех шифров так анализ происходил: для начала найдем секретный ключ. не важно каким путем.
pS. вот бы для всех шифров так анализ происходил: для начала найдем секретный ключ. не важно каким путем.
Во первых это требование написано в википедии, не я его выдумал.
Ну вот в моём примере выше.
на что Milfgard отвечает
Итак, у нас есть последовательность в миллион «случайных» бит числа ПИ, полученная начиная с позиции 76352843
И вот — 76352843 можно просто угадать. Это легче чем угадать миллион случайных бит.
Ну вот в моём примере выше.
Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.
на что Milfgard отвечает
Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например.
Итак, у нас есть последовательность в миллион «случайных» бит числа ПИ, полученная начиная с позиции 76352843
И вот — 76352843 можно просто угадать. Это легче чем угадать миллион случайных бит.
Когда вы получили эту последовательность у вас нет гарантии, что данная последовательность не повторяется «чуть» раньше или «чуть» позже: до данной позиции у вас еще примерно столько же, сколько и порядковый номер, последовательностей длины миллион. Об этом я и говорю выше: вы не сможете просто так угадать этот номер, ведь данная последовательность будет встречаться бесконечное множество раз в Пи.
Возможно, я непонятно объясняю… =(
Возможно, я непонятно объясняю… =(
Я понимаю что она бесконечно много раз встречается.
Но это не влияет на то что 76352843 можно просто угадать, и легче чем угадать миллион случайных бит.
76352843 влезает в 56 бит. Если мы решили из 76352843 сделать миллион случайных бит, «сэкономив» генератор настоящих случайных чисел («медленных физический генератор»).
То, злоумышленник, зная этот алгоритм, не будет угадывать миллон бит, он знает что исходное число влезало в 56 бит, и ему нужно брутфорсить 56 бит, а не миллион.
Но это не влияет на то что 76352843 можно просто угадать, и легче чем угадать миллион случайных бит.
76352843 влезает в 56 бит. Если мы решили из 76352843 сделать миллион случайных бит, «сэкономив» генератор настоящих случайных чисел («медленных физический генератор»).
То, злоумышленник, зная этот алгоритм, не будет угадывать миллон бит, он знает что исходное число влезало в 56 бит, и ему нужно брутфорсить 56 бит, а не миллион.
У 76352843 уместится и в 32-битный int, что по сути ничего не меняет. Вы вслепую ссылаетесь на теорему Шеннона про идеальные шифры. Просто тогда и гамму надо как-то передавать по еще одному секретному каналу.
В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?
В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?
Да, пардон, не 56 бит, а 56/2=28 бит.
В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?
Как раз таки по этому стойкость там считается как 128 бит, а не миллион бит.
А если и этот начальный 128-битовый ключ генерировали бы из 28-битового индекса числа ПИ, то стойкость была бы 28 бит.
Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное. Так вот в случае Пи это число бесконечно битное, просто старшие разряды нули. Или числа после некоего предела в последовательности Пи отбрасываются?
Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное.
Я называю 76352843 28-ми битным, потому что по легенде мы получили его из медленного физического генератора настоящих случайных чисел, и этот факт известен злоумышленнику. Ясно что медленный генератор генерирует маленькие числа, и какая именно разрядность — известно злоумышленнику, т.к. алгоритм не является секретом.
В начальной фазе инициализации сколько захотите, столько и будет стойкость: никто не запрещает использовать AES и для ключей длины 32 биты. В этом случае нам уже не интересно есть ли дальше уязвимости. Интерес в том не вносит ли алгоритм генерации гаммы других уязвимостей, о чем собственно и говорит тест next-bit.
оно не иррациональное, оно трансцендентное
Трасцендентное — да, но почему же не иррациональное?
ну просто потому что это более строгое определение ))
Более строгое определение? Иррациональное число — это не определение числа, это его принадлежность множеству иррациональных чисел. Так, что пи — рациональное число, пи — действительное число, это верные утверждения. А то, что пи — не иррациональное число, т.е. не принадлежит множеству иррациональных чисел — утверждение неверное.
Хотели сказать, что трансцендентные числа — более узкое множество? Но, увы, число может быть:
1) Не иррациональное, не трансцендентное. Например, 1.
2) Иррациональное, не трансцендентное. Например, sqrt(2).
3) Не иррациональное, трансцендентное. Например, pi * i.
4) Иррациональное, трансцендентное, Например, pi.
Хотели сказать, что трансцендентные числа — более узкое множество? Но, увы, число может быть:
1) Не иррациональное, не трансцендентное. Например, 1.
2) Иррациональное, не трансцендентное. Например, sqrt(2).
3) Не иррациональное, трансцендентное. Например, pi * i.
4) Иррациональное, трансцендентное, Например, pi.
Да вы — просто кладезь интересных ссылок!
Между тем, я нашёл заметку Саймона Плаффа, где он рассказывает о том, как открыл эту формулу.
Интересна следующая цитата:
Интересна следующая цитата:
Величайшей ошибкой в моей жизни было то, что я позволил Боруэйну и Бэйли называться соавторами формулы, когда они не открыли ничего вообще.
(ориг. This is where I made the biggest mistake in my life: To accept the collaboration of Peter Borwein and David H. Bailey as co-founders of that algorithm and formula when they have found nothing at all)
Про точку Фейнмана не знал, очень интересно, спасибо.
Наверное, на днях займусь написанием статьи о формуле BBP для русской Википедии, учтя при этом замечания Хабра.
Наверное, на днях займусь написанием статьи о формуле BBP для русской Википедии, учтя при этом замечания Хабра.
Напрямую — честно говоря, не знаю подходящих формул, из которых можно было бы что-нибудь подобное вывести.
А с промежуточным этапом в виде шестнадцатеричных знаков — с этим отлично справляется С-шный код, приведённый в статье.
А, значит, полагаю, и из формулы Белларда можно вывести, с промежуточным этапом в виде двоичных чисел.
А с промежуточным этапом в виде шестнадцатеричных знаков — с этим отлично справляется С-шный код, приведённый в статье.
А, значит, полагаю, и из формулы Белларда можно вывести, с промежуточным этапом в виде двоичных чисел.
И, похоже, вы только что прочитали первую русскоязычную статью об этом алгоритме в рунете — других я найти не смог.
а вот cih.ru/a1/e79.html
Саймон Плафф, как выяснилось, готов с вами поспорить.
Цитирую первые строчки:
Цитирую первые строчки:
We outline a method for computing the n'th decimal (or any other base) digit of Pi in
C*n^3*log(n)^3 time and with very little memory.
А чему соответствует C?
Имеется в виду следующее:
«Существует такая константа C, для которой при любом сколь угодно большом N время выполнения алгоритма будет ниже, чем C*n^3*log(n)^3».
По-другому то же самое можно записать как T = О(n^3*log(n)^3)
«Существует такая константа C, для которой при любом сколь угодно большом N время выполнения алгоритма будет ниже, чем C*n^3*log(n)^3».
По-другому то же самое можно записать как T = О(n^3*log(n)^3)
Согласно эмпирическим данным, дробная часть числа Пи представляет собой нормальную числовую последовательность (хотя доказать это достоверно ещё не удалось), а значит, последовательности цифр из него можно использовать в генерации паролей и просто случайных чисел, или в криптографических алгоритмах (например, в хэшировании). Способов применения можно найти великое множество — надо только включить фантазию.
Для генерации паролей, случайных чисел и другого есть более оптимальные и менее ресурсозатратные методы.
Был проект распределенных вычислений пи до миллиардного знака, как раз эту формулу использовал. Там был клинт, нужно было его скачать, чтобы сервер выдал ему диапазон для вычисления
Сомневаюсь в ценности формулы для распределенных вычислений большого количества цифр. Время вычисления n-го знака O(n), то есть на вычисление n цифр потратим O(n^2) времени, думаю есть более эффективные методы. Или нет?
Для вычисления всех цифр до n есть алгоритм со сложностью O(M(n)*log(n)), где M(n) — сложность перемножения двух чисел длиной n бит.
А каков геометрический смысл этой формулы? Встречались статьи на русском? Что она говорит про суть числа пи и прочих, считаемых подобными формулами? Как доказано, что ими вычисляется именно пи, а не лабуда какая-нибудь?
Что то не пойму и как из этого получить 10-ичную цифру, кто то может объяснить?
position = 6
fraction = 0.533289136557027
hex digits = 8885A308D3
position = 6
fraction = 0.533289136557027
hex digits = 8885A308D3
Меня одного смущает вот этот цикл в коде: for (k = 0; k < id; k++)?
Получается, чтобы вычислить цифру числа PI начиная с позиции id, нам придется выполнить id итераций этого цикла. Получается, алгоритм имеет сложность O(n) для вычисления n-й цифры числа.
Честно говоря, по заголовку подумал, что, найдена формула, которая имеет сложность O(1) для конкретной цифры числа. Формула, безусловно, красивая. Но думаю, что генератор случайных чисел создать на её базе, увы, не получится: накладно.
Получается, чтобы вычислить цифру числа PI начиная с позиции id, нам придется выполнить id итераций этого цикла. Получается, алгоритм имеет сложность O(n) для вычисления n-й цифры числа.
Честно говоря, по заголовку подумал, что, найдена формула, которая имеет сложность O(1) для конкретной цифры числа. Формула, безусловно, красивая. Но думаю, что генератор случайных чисел создать на её базе, увы, не получится: накладно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисление N-го знака числа Пи без вычисления предыдущих