Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 28
К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа.
А как же субэкспоненциальные алгоритмы факторизации? Да и о «классической архитектуре» следуем упомянуть
На мой взгляд, субэкспоненциальные — это экспоненциальные с оптимизацией. То есть, экспонента от длины числа в знаках в субэкспоненциальных никуда не исчезает.
А что касается классической архитектуры, то статья, это просто способ проиллюстрировать наглядно введение в некоторые классические идеи. Я сам разбираюсь с теорией чисел и проникаю в некоторые затейливые компактные формулы, разворачивая их для себя наглядно.
В статье нет особенной новизны, кроме, разве что, введения произведения последовательности простых чисел как самоподобной базы и намеков на возможное аналитическое изучение самоподобных областей симметрии в регулярности множества составных чисел (дополнительного к множеству простых)
А что касается классической архитектуры, то статья, это просто способ проиллюстрировать наглядно введение в некоторые классические идеи. Я сам разбираюсь с теорией чисел и проникаю в некоторые затейливые компактные формулы, разворачивая их для себя наглядно.
В статье нет особенной новизны, кроме, разве что, введения произведения последовательности простых чисел как самоподобной базы и намеков на возможное аналитическое изучение самоподобных областей симметрии в регулярности множества составных чисел (дополнительного к множеству простых)
Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 раз. Это и значит, что сложность алгоритма является экспоненциальный...
Это ложное утверждение: если умножить число на 100, то поиск замедлится не более, чем в 100 раз. У вас неверные представления об экспоненциальный сложности: она экспоненциальная относительно битовой длины числа, а не относительно самого числа.
К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, можно, заодно, решить математическую проблему, известную как гипотеза Римана.
Можно ссылку на то, что гипотеза Римана следует из указанного вами утверждения?
Спасибо, про увеличение сложности — исправил.
Про связь гипотезы Римана и экспоненциальности возможных алгоритмов факторизации — предположение неточное и вопрос спорный. Если говорить о практике, то я не встречал предложенных алгоритмов факторизации полиномиальной сложности, отсутствие ошибки в которых бы доказывалось справедливостью Гипотезы Римана.
Про связь гипотезы Римана и экспоненциальности возможных алгоритмов факторизации — предположение неточное и вопрос спорный. Если говорить о практике, то я не встречал предложенных алгоритмов факторизации полиномиальной сложности, отсутствие ошибки в которых бы доказывалось справедливостью Гипотезы Римана.
Построение вашего последнего предложения завело меня в тупик.
На уровне идей: справедливость гипотезы Римана означает, что простые числа распределены в некотором смысле наиболее регулярным способом, т. е. в асимптотическом законе простых чисел остаточный член мажорируется корневой оценкой. Это может повлиять на оценки сложности алгоритмов проверки на простоту (и влияет), но у нас они и так полиномиальны. Связь же гипотезы Римана именно с алгоритмами факторизации идейно ничем не обусловлена.
На уровне идей: справедливость гипотезы Римана означает, что простые числа распределены в некотором смысле наиболее регулярным способом, т. е. в асимптотическом законе простых чисел остаточный член мажорируется корневой оценкой. Это может повлиять на оценки сложности алгоритмов проверки на простоту (и влияет), но у нас они и так полиномиальны. Связь же гипотезы Римана именно с алгоритмами факторизации идейно ничем не обусловлена.
Но, пожалуй, наибольший интерес вызывает возможность уточнения оценки вероятности нахождения простых чисел все дальше и дальше. Если рассматривать матрицы, то мы видим, как вероятность падает, начиная с 4/6, далее до 7/24 (или усредненно 11/30), потом 36/180 (или 47/210), и т.д.
Не понял, о какой вероятности идет речь. Насколько я понял, выше в таком же смысле упоминалась вероятности 2/6 и 8/30.
Вероятность того, что число не делится на последовательные простые p1, ..., pn, есть (1-1/p1)...(1-1/pn), что по теореме Мертенса равно e-γ / ln pn, где γ — константа Эйлера-Маскерони.
Если брать разные интервалы, то и вероятность в них — разная. Если мы берем интервал от 1 до 30, то вероятность 11/30. Если же мы исключаем первую группу из 6 чисел, то получаем отрезок 1..6 (где вероятность 4/6) и 7..30 (где вероятность 8/24)
Есть много формул оценки вероятности, но их появление нужно разобрать. В данной же статье — лишь иллюстрация подхода, идея о том, какова структура, как устроены составные числа, как можно показать в этой структуре симметрию и уровни самоподобия.
Есть много формул оценки вероятности, но их появление нужно разобрать. В данной же статье — лишь иллюстрация подхода, идея о том, какова структура, как устроены составные числа, как можно показать в этой структуре симметрию и уровни самоподобия.
Позволите говорить прямо?
Факт «отбрасывание теней» (он же метод решета) в различных ипостасях является очень популярным в любительских исследованиях по теории чисел. Я регулярно встречаю эссе, претендующие на открытие нового алгоритма факторизации, основанные на его применении. Вашу статью от них выгодно отличает неплохой стиль и отсутствие завышенного ЧСВ. Однако фактический уровень математического содержания — такой же.
Читайте книжки по теории чисел и развивайтесь. Когда одолеете стандартный учебник для первого курса (лучше забугорный Hardy & Wright), можете переходить к литературе по методу решета, раз уж оно вам интересно. Например, «Распределение простых чисел» Прахара будет неплохим стартом.
Факт «отбрасывание теней» (он же метод решета) в различных ипостасях является очень популярным в любительских исследованиях по теории чисел. Я регулярно встречаю эссе, претендующие на открытие нового алгоритма факторизации, основанные на его применении. Вашу статью от них выгодно отличает неплохой стиль и отсутствие завышенного ЧСВ. Однако фактический уровень математического содержания — такой же.
Читайте книжки по теории чисел и развивайтесь. Когда одолеете стандартный учебник для первого курса (лучше забугорный Hardy & Wright), можете переходить к литературе по методу решета, раз уж оно вам интересно. Например, «Распределение простых чисел» Прахара будет неплохим стартом.
Автор, вы сперва заявляете «в статье не будет сложной математики, и мы не будем забираться глубоко в ее дебри», а потом начинаете сыпать терминами, вроде «Многомерные матрицы и гиперреалистичные фракталы», причем я не уверен, что вы сами поняли что сказали. И так далее в том же духе. Короче, пока мне кажется, что статья — фричество и ересь.
Статья совершенно любительская, Вы совершенно правы (я, правда, не очень склонен начальный уровень сложности введения в проблему дискредетировать словами фричество и ересь). Математика — не догматическая наука, а точная. Поэтому слово «ересь» в математике — ересь.
Слово «ересь», в данном случае, означает, что автор не следует соглашениям, выработанным для облегчения понимания подобных статей, изобретает собственные термины вместо использования общепринятых, не работает с источникам по данной теме. Как следствие этого — статья малополезна, и автору лучше бы научиться писать не-ересь.
Окей, с такой формулировкой согласен. Но всегда есть вопрос баланса — изобретать велосипеды (так же, как это делали многие «отцы-основатели», придумывая свою нотацию, свои методы), или изучать существующие. Когда существующие не решают поставленные задачи, можно и «пофричить» в пределах разумного. Хотя, немало примеров, когда простые числа или деление на ноль сводят с ума и съедают все время у «подсевших» на довольно тривиальные расчеты.
Меня изобретение велосипедов не пугает. Но, в одном Вы правы — публиковать изобретение велосипедов затея спорная. На будущее остерегусь спешить.
Может и эту убрать в черновики? Из 20 тысяч прочитавших не так много проголосовали «за». И много против…
Но, если честно, мне помогла критика. Когда я играл с числами — у меня было большое вдохновение, чувство чего-то значительного. Сейчас я понимаю, что это не дает новизны (но надеюсь, что может немного вдохновить таких же нубов, как и я)
Меня изобретение велосипедов не пугает. Но, в одном Вы правы — публиковать изобретение велосипедов затея спорная. На будущее остерегусь спешить.
Может и эту убрать в черновики? Из 20 тысяч прочитавших не так много проголосовали «за». И много против…
Но, если честно, мне помогла критика. Когда я играл с числами — у меня было большое вдохновение, чувство чего-то значительного. Сейчас я понимаю, что это не дает новизны (но надеюсь, что может немного вдохновить таких же нубов, как и я)
мне понравилась идея многомерного представления простых чисел, о которой узнал из вашей статьи
Попробуйте переработать статью. Почитайте источники (для начала — хотя бы английскую википедию, там есть ссылки на серьезные статьи), переформулируйте в общепринятых терминах, проставьте ссылки. Может чего и найдете интересного. Вы извините, что я вас так резко раскритиковал, но, к сожалению, такие малопонятные и малополезные стати пишут все чаще, а исправляться их авторы не желают. Рад знать, что вы — приятное исключение.
Вот вам антипримеры «как не надо писать». Почитайте и ужаснитесь:
habrahabr.ru/post/225175 — по вашей теме, между прочим. Идеи похожи на ваши, насколько я смог понять — а понять тяжело. Если бы автор этой стати писал понятнее, а вы поискали бы что по этой теме уже написано хотя бы на ГТ, возможно почерпнули бы у него какие-то идеи. Но поскольку его статья написана и оформлена безграмотно, никому, кроме автора, вообще не понятно о чем идет речь.
sohabr.net/gt/post/242548, geektimes.ru/post/242214 — это, конечно, экстремальный пример, но публикация сырых идей без проработки источников может закончится и так.
habrahabr.ru/post/205900 — там все кончилось натуральным мошенничеством. Я вас не в коем случае приравниваю к мошенникам, да и в математике запутаться куда легче, чем в физике, но правила исследований для того и придумывали, чтобы фильтровать подобных граждан.
В общем: вы хотите исправиться — уже хорошо. Еще раз говорю, почитайте серьезную литературу по теме, возможно найдете что-то полезное и сможете оформить ваши идеи в теорию. А скорее всего — окажется, что ваши идеи никакой новизны не содержат, но это — не страшно, придумаете что-нибудь новое. И опубликуете уже без отсебятской терминологии и каши.
Вот вам антипримеры «как не надо писать». Почитайте и ужаснитесь:
habrahabr.ru/post/225175 — по вашей теме, между прочим. Идеи похожи на ваши, насколько я смог понять — а понять тяжело. Если бы автор этой стати писал понятнее, а вы поискали бы что по этой теме уже написано хотя бы на ГТ, возможно почерпнули бы у него какие-то идеи. Но поскольку его статья написана и оформлена безграмотно, никому, кроме автора, вообще не понятно о чем идет речь.
sohabr.net/gt/post/242548, geektimes.ru/post/242214 — это, конечно, экстремальный пример, но публикация сырых идей без проработки источников может закончится и так.
habrahabr.ru/post/205900 — там все кончилось натуральным мошенничеством. Я вас не в коем случае приравниваю к мошенникам, да и в математике запутаться куда легче, чем в физике, но правила исследований для того и придумывали, чтобы фильтровать подобных граждан.
В общем: вы хотите исправиться — уже хорошо. Еще раз говорю, почитайте серьезную литературу по теме, возможно найдете что-то полезное и сможете оформить ваши идеи в теорию. А скорее всего — окажется, что ваши идеи никакой новизны не содержат, но это — не страшно, придумаете что-нибудь новое. И опубликуете уже без отсебятской терминологии и каши.
достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 разтак в сто раз или на 2-3 знака?
растет по очень простому законукакому?
Простому закону, но невыразимому аналитически. Легко эту закономерность заметить, но чтобы написать формулу, снова старая проблема — неопределенность метрики в множестве простых чисел.
База развертки матрицы увеличивается каждый раз на уже известное небольшое простое последовательное число, размер матрицы быстро растет, в начале и конце матрицы образуются растующие медленно, но устойчиво симметричные зоны составных чисел.
Вообще мне очень интересны осевые симметрии во вложенных диапазонах, например, если база 30030, то внутри имеем 13 симметричных областей по 2310 строк, в каждой из которых 11 симметричных областей по 210 строк, в каждой из которых 7 симметричных областей по 30 строк, в каждой из которых 5 симметричных областей по 6 строк.
Как бы мы ни увеличивали базу, умножая ее на последовательные уже известные простые числа, все области симметрии сохраняются, добавляются при этом новые.
Такая закономерность очевидна. И то, что широкая зона строк с составными числами в начале и конце каждой базы растет, определяя регулярную структуру максимального расстояния между двумя простыми числами — можно заметить, аналитически же надо записать формулу вроде
...13 х (11 x (7 x (5 x (6n | {p mod 6}) | {q mod 30}) | {r mod 210}) | {s mod 2310}) | {t mod 30030} ...,
где сокращение вида "| {p mod 6}" значит исключение строк в данной области симметрии, по соответствующему модулю, например {p mod 6} это {0, 2, 3, 4}.
База развертки матрицы увеличивается каждый раз на уже известное небольшое простое последовательное число, размер матрицы быстро растет, в начале и конце матрицы образуются растующие медленно, но устойчиво симметричные зоны составных чисел.
Вообще мне очень интересны осевые симметрии во вложенных диапазонах, например, если база 30030, то внутри имеем 13 симметричных областей по 2310 строк, в каждой из которых 11 симметричных областей по 210 строк, в каждой из которых 7 симметричных областей по 30 строк, в каждой из которых 5 симметричных областей по 6 строк.
Как бы мы ни увеличивали базу, умножая ее на последовательные уже известные простые числа, все области симметрии сохраняются, добавляются при этом новые.
Такая закономерность очевидна. И то, что широкая зона строк с составными числами в начале и конце каждой базы растет, определяя регулярную структуру максимального расстояния между двумя простыми числами — можно заметить, аналитически же надо записать формулу вроде
...13 х (11 x (7 x (5 x (6n | {p mod 6}) | {q mod 30}) | {r mod 210}) | {s mod 2310}) | {t mod 30030} ...,
где сокращение вида "| {p mod 6}" значит исключение строк в данной области симметрии, по соответствующему модулю, например {p mod 6} это {0, 2, 3, 4}.
Помню в детстве/юности неплохо увлекался математикой, получал дипломы на разных олимпиадах, и действительно думал что когда-нибудь позже докажу что-нибудь подобное. Сейчас сижу и понимаю как далек от этого я стал спустя 5-7 лет…
Да, согласен. Теория чисел мое небольшое большое увлечение, которое откладывалось много-много лет. Понадобилось разобраться с факторизацией чисел, полез в учебники и статьи и обнаружил, что требуется множество времени, чтобы понять, что значат те или другие формулы. Попробовал это нарисовать сам себе наглядно (что-то на листочке, что-то в экселе) и обнаружил, что наглядность помогает. Поработав со структурами наглядно стал хорошо понимать суть многих статей, стало легче разбираться. Правда, не ко всему еще смог подступиться
1+29=7+23=11+19=13+7.
Вероятно, вы имели в виду 13+17?
Статья интересная, спасибо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Непростые простые числа: секреты тайного общества ткачей