Вы написали дилетантский текст про то, что уже многократно написано и опубликовано, включая и научно-популярные изложения. Кроме этого, Вы ограничились только так называемым «энтропийным кодированием» или «кодированием для источника», хотя существует «помехоустойчивое кодирование» — направление, не менее важное как в теоретическом, так и практическом плане. Например, в каждом смартфоне стоит микросхема, которая отвечает как за кодирование информации, которая предназначена для передачи по каналу с шумом, так и за декодирование принятой информации с исправлением ошибок/стираний. Уверяю вас — это большая и весьма изощрённая теория, в которой работают выдающиеся люди. И вообще основные положения теории информации, откуда всё это «кодирование» и пошло, собственно, были сформулированы в фундаментальной работе Клода Шеннона, про которого Вы даже не упомянули. Кроме этого, «кодированием» иногда называют криптографическое преобразование, что по-сути неверно и следует расценивать, как терминологический нонсенс. В общем, когда затеваешь написание статьи с последующей её публикацией, надо отдавать себе отчёт в том, зачем ты это делаешь, какие цели преследуешь, и на кого рассчитана эта публикация. Иначе может быть стыдно за результат.
1) Когда я написал O(2n) я имел в виду два умножить на n, без квадратов. Связано это с тем что пузырёк с оптимизациями завершает работу если нет перестановок, поэтому если в огромном массиве из нулей поместить одну единицу, то цикл сортировки пройдёт два раза по n - первый раз угнав единицу в конец массива, а второй раз - убедиться, что перестановок нет. Если же массив уже отсортирован, то это будет O(n). Поэтому сложность пузырька варьируется от O(n) до O(n^2).
К вопросу об ограничениях и частных случаях. А если предположить, что только на одной позиции (неизвестной заранее) имеется отличное от нуля значения, а во всех остальных позициях расположены нули и это установленный факт? Тогда потребуется n-j сравнений и перестановок, где j — позиция, на которой находится это самое ненулевое значение. Иными словами, n-1 таких операций в худшем случае. А если заранее известно, на какой позиции находится это ненулевое значение, то сортировка вообще не нужна? Вы хотя бы интуитивно понимаете, что это вот всё вообще ни о чём?
Уважаемый автор! Продолжаете упорствовать и пришло время вас немного пожурить. Вы не понимаете смысла асимптотической оценки сложности «O-большое» или «символа Бахмана», как эту оценку ещё называют по имени математика, который её ввёл. А ведь про это должен знать каждый, кто прослушал и усвоил университетский курс computer science. Здесь уже несколько комментаторов отметили сей печальный факт. Вместо того, чтобы обратиться к учебнику и всё тщательно обдумать, Вы продолжаете твердить своё. При этом Вы не понимаете, что вычислительную трудоёмкость — этот термин принят в русскоязычной литературе вместо «сложность» (прямой перевод англоязычного термина «complexity») — оценивают в «худшем» случае, редко «в среднем» (для этого нужны веские причины), но уж точно не подбирают параметры так, чтобы обосновать преимущество алгоритма. Что касается каких-то весьма частных случаев, то они малоинтересны. И на это вам тоже указывали. Кто из нас не предлагал эффективного решения отдельных задач с сильными ограничениями? Интересны универсальные методы с гарантированной асимптотической оценкой. В общем писать программы — это хорошо, конечно, но как завещал Дональд, отец наш Кнут, надо к ещё и к источнику знаний припадать время от времени, а лучше всего математику учить. Тогда и вопросов лишних не будет, а у некоторых мировоззрение даже выправляется.
Ваш алгоритм сортировки, как я его понимаю, поправьте если что не так, устроен следующим образом. Пусть имеется объектов, которые необходимо отсортировать в порядке неубывания. Например, это могут быть записи в базе данных. Сортировка осуществляется по ключу, а именно по содержимому некоторого позиционно фиксированного поля в пределах каждой записи и это поле всегда существует. Пусть ключ — это натуральное число. Отмечу, что алгоритм обобщается на целые числа. Ключ принимает значение из диапазона . Заранее величины ключа не известны и можно исходить только из минимально и максимального значений указанного диапазона. Это означает, что необходимо зарезервировать бит памяти. Назовём ячейкой отдельную порцию бит. Тогда для сортировки нам понадобится ячеек памяти с прямым доступом и значение ключа — это относительный адрес некоторой ячейки. Для начала мы выполняем подготовительную операцию обнуления — заносим в каждую ячейку значение 0. Затем приступаем непосредственно к сортировке: 1) считываем значение ключа из записи; 2) используем это значение для перехода к нужной ячейке (смещением относительно базового адреса) и увеличиваем её значение на 1 (это счётчик вхождений). Когда все ключи обработаны, нам надо получить результат сортировки. Для этого мы проверяем значение каждой ячейки и формируем отдельный список, в котором напротив значения ключа располагается значение счётчика. Дело сделано. Понятно, что асимптотическая сложность такой сортировки не , а . При этом, очевидно, что в худшем случаеЕсли — это некоторая экспонента, то асимптотическая сложность такого алгоритма сортировки перестаёт быть полиномиальной.
пузырьковому как минимум потребуется O(2n) даже всего на одной единице среди миллиарда
Асимптотическая сложность сортировки методом «пузырька» — O(N^2). На всякий случай ещё и напишу: N в квадрате, где N — мощность сортируемого массива данных (количество объектов в нём). Кстати, оценка O(2N) смысла не имеет. Поскольку символ Бахмана так устроен, что учитывает мульпликативные константы, которые могут отличаться для различных реализаций алгоритма, зависеть, например, от платформы и пр.
Пузырьковая сортировка имеет асимптотическую оценку сложности O(N^2). Самые быстрые алгоритмы сортировки, HeapSort например (сортировка на бинарных деревьях), имеют асимптотическую сложность O(NlogN). Это означает, что все они полиномиальны по сложности. Есть алгоритмы, которые предполагают сортировку отдельных массивов данных с их последующим слиянием. Алгоритм, который Вы рассматриваете, при небольшом массиве сортируемых данных может потребовать очень большой памяти. Если на примере чисел, то всё зависит от того, из какого диапазоне выбираются эти числа.
Если сводимость доказана, то задача относится к NP-полным. Для задачи факторизации и дискретного логарифма это не доказано. Возможно по этой причине для этих задач известны решения с полиномиальной сложностью на квантовом компьютере. Вообще эта публикация настолько поверхностна, что её нельзя использовать в дидактичеких целях. Я уже написал, что те, кто не разбираются в вопросе, скорее больше запутаются, чем что-то для себя выяснят.
А имеет ли смысл публиковать перевод статьи неспециалиста? Ведь Erica Klarreich не является специалистом в этой области. Те, кто не разбираются могут вообще не понять, понять неправильно или не до конца. Специалисты же читают совсем другие тексты. Тогда возникает вопрос: А на кого рассчитана эта публикация? Тем более, что текст не рецензировался, как я понимаю.
Хотите подешевле? Так правильно и дешево не всегда получается сделать. Хотя на примере аппаратных кошельков, так называемых холодных (KeepKey, Trezor, и пр.), мы видим, что сделать можно и более того, можно их продавать на массовом рынке за вполне умеренные деньги и без всяких экспортных ограничений. Кстати, в KeepKey стоит специальная микросхема, которая отвечает за формирование случайных бит. Про это прямо в документации написано. Да и с габаритами вроде всё нормально. Ещё и код открытый. Так может в вашем случае дело в чём-то другом?
А про энтропию планеты — это круто, конечно. Но звучит как бред. Надеюсь, Вы понимаете, что энтропия считается по формуле Шеннона. А этот сумма произведений вероятностей на логарифм по основанию два тех же вероятностей (со знаком минус для нормировки, так как логарифм по основанию два величины меньшей единицы всегда отрицательное число). Это значит, что нужно определиться с пространством событий, задать случайную переменную и взять откуда-то эти самые вероятности, например вероятности исходов некоторых событий.
Я понимаю, что большинству всё равно, но если приводите уравнение, то делайте это правильно. Тогда в общем виде будет гдепринадлежат и – простое. В частном случае Тем более, что на Хабр можно вводить формулы в нотации LaTeX.
И вообще вы привели график уравнения в поле вещественных чисел. Тогда как эллиптическая криптография использует подгруппу простого порядка группы точек эллиптической кривой над полем Можно привести график и такой кривой, но только это будет некоторый набор точек наподобие решётки.
Это ведь самое узкое место. Вы ведь специалист по аппаратной части. Так возьмите соответствующую микросхему и генерируйте энтропийные биты. Есть такие. Например, на основе измерений теплового шума и другие. Самое логичное решение в вашем случае. И это будет настоящая случайность, а не какой-нибудь ГПСЧ. Полагаю, что Вы про такие аппаратные решения должны понимать лучше других. Вот что хотелось от вас услышать, а не самоустранение от ответа на конкретный вопрос. Но, увы.
…+ берутся некоторые случайные метеоданные из интернета…
Вот уж странно. А это зачем? Энтропия возрастёт? Вообще-то надо понимать, что любая такая странность трактуется не в пользу разработки, а вызывает подозрения. Особенно, когда речь идёт о генерации секретных ключей, задействованных в криптографических преобразованиях.
Надо всем помнить, что в холодной войне против нас со всех сторон ведутся агрессивные действия, в том числе против развития прорывных научных исследований в России.
Нда… всё бы ничего, но вот этот вот пассаж говорит о многом.
Контракт либо проведет сделку с выполнением всех условий, либо не проведет и здесь неважно принадлежит ли адрес тому, кто заявляет об этом.
Важно. Ведь ЭЦП транзакции проверяется всегда. Если ЭЦП не валидна, то транзакция будет отвергнута и никогда не попадёт в блок. За это, помимо прочего, отвечает смарт-контракт или скрипт в случае Bitcoin.
Смарт-контракт вторичен, так как инициируется владельцем актива. Владелец представлен адресом (кошельком). Блокчейн сам по себе тоже к этому не имеет отношения. В некоторых приложениях можно применять и сертификаты и блокчейн. Это не запрещено. Зависит от задачи. Так что основная цель, которая достигается путём исключения сертификатов общедоступных ключей – это анонимность.
Вы написали дилетантский текст про то, что уже многократно написано и опубликовано, включая и научно-популярные изложения. Кроме этого, Вы ограничились только так называемым «энтропийным кодированием» или «кодированием для источника», хотя существует «помехоустойчивое кодирование» — направление, не менее важное как в теоретическом, так и практическом плане. Например, в каждом смартфоне стоит микросхема, которая отвечает как за кодирование информации, которая предназначена для передачи по каналу с шумом, так и за декодирование принятой информации с исправлением ошибок/стираний. Уверяю вас — это большая и весьма изощрённая теория, в которой работают выдающиеся люди. И вообще основные положения теории информации, откуда всё это «кодирование» и пошло, собственно, были сформулированы в фундаментальной работе Клода Шеннона, про которого Вы даже не упомянули. Кроме этого, «кодированием» иногда называют криптографическое преобразование, что по-сути неверно и следует расценивать, как терминологический нонсенс. В общем, когда затеваешь написание статьи с последующей её публикацией, надо отдавать себе отчёт в том, зачем ты это делаешь, какие цели преследуешь, и на кого рассчитана эта публикация. Иначе может быть стыдно за результат.
К вопросу об ограничениях и частных случаях. А если предположить, что только на одной позиции (неизвестной заранее) имеется отличное от нуля значения, а во всех остальных позициях расположены нули и это установленный факт? Тогда потребуется n-j сравнений и перестановок, где j — позиция, на которой находится это самое ненулевое значение. Иными словами, n-1 таких операций в худшем случае. А если заранее известно, на какой позиции находится это ненулевое значение, то сортировка вообще не нужна? Вы хотя бы интуитивно понимаете, что это вот всё вообще ни о чём?
Уважаемый автор! Продолжаете упорствовать и пришло время вас немного пожурить. Вы не понимаете смысла асимптотической оценки сложности «O-большое» или «символа Бахмана», как эту оценку ещё называют по имени математика, который её ввёл. А ведь про это должен знать каждый, кто прослушал и усвоил университетский курс computer science. Здесь уже несколько комментаторов отметили сей печальный факт. Вместо того, чтобы обратиться к учебнику и всё тщательно обдумать, Вы продолжаете твердить своё. При этом Вы не понимаете, что вычислительную трудоёмкость — этот термин принят в русскоязычной литературе вместо «сложность» (прямой перевод англоязычного термина «complexity») — оценивают в «худшем» случае, редко «в среднем» (для этого нужны веские причины), но уж точно не подбирают параметры так, чтобы обосновать преимущество алгоритма. Что касается каких-то весьма частных случаев, то они малоинтересны. И на это вам тоже указывали. Кто из нас не предлагал эффективного решения отдельных задач с сильными ограничениями? Интересны универсальные методы с гарантированной асимптотической оценкой. В общем писать программы — это хорошо, конечно, но как завещал Дональд, отец наш Кнут, надо к ещё и к источнику знаний припадать время от времени, а лучше всего математику учить. Тогда и вопросов лишних не будет, а у некоторых мировоззрение даже выправляется.
Ваш алгоритм сортировки, как я его понимаю, поправьте если что не так, устроен следующим образом. Пусть имеется
объектов, которые необходимо отсортировать в порядке неубывания. Например, это могут быть записи в базе данных. Сортировка осуществляется по ключу, а именно по содержимому некоторого позиционно фиксированного поля в пределах каждой записи и это поле всегда существует. Пусть ключ — это натуральное число. Отмечу, что алгоритм обобщается на целые числа. Ключ принимает значение из диапазона 
. Заранее величины ключа не известны и можно исходить только из минимально и максимального значений указанного диапазона. Это означает, что необходимо зарезервировать 
бит памяти. Назовём ячейкой отдельную порцию 
бит. Тогда для сортировки нам понадобится 
ячеек памяти с прямым доступом и значение ключа — это относительный адрес некоторой ячейки. Для начала мы выполняем подготовительную операцию обнуления — заносим в каждую ячейку значение 0. Затем приступаем непосредственно к сортировке: 1) считываем значение ключа из записи; 2) используем это значение для перехода к нужной ячейке (смещением относительно базового адреса) и увеличиваем её значение на 1 (это счётчик вхождений). Когда все ключи обработаны, нам надо получить результат сортировки. Для этого мы проверяем значение каждой ячейки и формируем отдельный список, в котором напротив значения ключа располагается значение счётчика. Дело сделано. Понятно, что асимптотическая сложность такой сортировки не 
, а 
. При этом, очевидно, что в худшем случае
Если 
— это некоторая экспонента, то асимптотическая сложность такого алгоритма сортировки перестаёт быть полиномиальной.
Асимптотическая сложность сортировки методом «пузырька» — O(N^2). На всякий случай ещё и напишу: N в квадрате, где N — мощность сортируемого массива данных (количество объектов в нём). Кстати, оценка O(2N) смысла не имеет. Поскольку символ Бахмана так устроен, что учитывает мульпликативные константы, которые могут отличаться для различных реализаций алгоритма, зависеть, например, от платформы и пр.
Очень правильное замечание. Совершенно согласен.
Пузырьковая сортировка имеет асимптотическую оценку сложности O(N^2). Самые быстрые алгоритмы сортировки, HeapSort например (сортировка на бинарных деревьях), имеют асимптотическую сложность O(NlogN). Это означает, что все они полиномиальны по сложности. Есть алгоритмы, которые предполагают сортировку отдельных массивов данных с их последующим слиянием. Алгоритм, который Вы рассматриваете, при небольшом массиве сортируемых данных может потребовать очень большой памяти. Если на примере чисел, то всё зависит от того, из какого диапазоне выбираются эти числа.
Если сводимость доказана, то задача относится к NP-полным. Для задачи факторизации и дискретного логарифма это не доказано. Возможно по этой причине для этих задач известны решения с полиномиальной сложностью на квантовом компьютере. Вообще эта публикация настолько поверхностна, что её нельзя использовать в дидактичеких целях. Я уже написал, что те, кто не разбираются в вопросе, скорее больше запутаются, чем что-то для себя выяснят.
А имеет ли смысл публиковать перевод статьи неспециалиста? Ведь Erica Klarreich не является специалистом в этой области. Те, кто не разбираются могут вообще не понять, понять неправильно или не до конца. Специалисты же читают совсем другие тексты. Тогда возникает вопрос: А на кого рассчитана эта публикация? Тем более, что текст не рецензировался, как я понимаю.
May be so, but the article is not about that.
А с какого перепугу я должен для вас что-то рассчитывать? Это же работа, а я вас даже не знаю. Так что как-нибудь сами, сами…
Думаю, что следует закончить. Всяческих вам успехов! Путь будет тернист!
Хотите подешевле? Так правильно и дешево не всегда получается сделать. Хотя на примере аппаратных кошельков, так называемых холодных (KeepKey, Trezor, и пр.), мы видим, что сделать можно и более того, можно их продавать на массовом рынке за вполне умеренные деньги и без всяких экспортных ограничений. Кстати, в KeepKey стоит специальная микросхема, которая отвечает за формирование случайных бит. Про это прямо в документации написано. Да и с габаритами вроде всё нормально. Ещё и код открытый. Так может в вашем случае дело в чём-то другом?
А про энтропию планеты — это круто, конечно. Но звучит как бред. Надеюсь, Вы понимаете, что энтропия считается по формуле Шеннона. А этот сумма произведений вероятностей на логарифм по основанию два тех же вероятностей (со знаком минус для нормировки, так как логарифм по основанию два величины меньшей единицы всегда отрицательное число). Это значит, что нужно определиться с пространством событий, задать случайную переменную и взять откуда-то эти самые вероятности, например вероятности исходов некоторых событий.
Я понимаю, что большинству всё равно, но если приводите уравнение, то делайте это правильно. Тогда в общем виде будет
где
принадлежат 
и 
– простое. В частном случае 
Тем более, что на Хабр можно вводить формулы в нотации LaTeX.
И вообще вы привели график уравнения в поле вещественных чисел. Тогда как эллиптическая криптография использует подгруппу простого порядка группы точек эллиптической кривой над полем
Можно привести график и такой кривой, но только это будет некоторый набор точек наподобие решётки.
Кое-что и на Хабр про это есть https://habr.com/ru/amp/post/128666/
Название статьи: «Как работает новый генератор случайных чисел Intel».
С тех пор многое могло измениться в лучшую сторону.
Это ведь самое узкое место. Вы ведь специалист по аппаратной части. Так возьмите соответствующую микросхему и генерируйте энтропийные биты. Есть такие. Например, на основе измерений теплового шума и другие. Самое логичное решение в вашем случае. И это будет настоящая случайность, а не какой-нибудь ГПСЧ. Полагаю, что Вы про такие аппаратные решения должны понимать лучше других. Вот что хотелось от вас услышать, а не самоустранение от ответа на конкретный вопрос. Но, увы.
Так замечательные рассуждения. Душеспасительные. Но тут наука нужна. Колличество энтропийных бит можете оценить при таком способе генерации?
Вот уж странно. А это зачем? Энтропия возрастёт? Вообще-то надо понимать, что любая такая странность трактуется не в пользу разработки, а вызывает подозрения. Особенно, когда речь идёт о генерации секретных ключей, задействованных в криптографических преобразованиях.
Нда… всё бы ничего, но вот этот вот пассаж говорит о многом.
Важно. Ведь ЭЦП транзакции проверяется всегда. Если ЭЦП не валидна, то транзакция будет отвергнута и никогда не попадёт в блок. За это, помимо прочего, отвечает смарт-контракт или скрипт в случае Bitcoin.
Смарт-контракт вторичен, так как инициируется владельцем актива. Владелец представлен адресом (кошельком). Блокчейн сам по себе тоже к этому не имеет отношения. В некоторых приложениях можно применять и сертификаты и блокчейн. Это не запрещено. Зависит от задачи. Так что основная цель, которая достигается путём исключения сертификатов общедоступных ключей – это анонимность.