Формула для вычисления систем счисления, образующих связи с оригинальной системой счисления для заданного простого числа
Связи систем счисления очень простые. Систем счисления больших, чем число N просто не нужно привлекать. Всё, что больше N вычисляется на основе систем счисления до N.
В вашем примере для 7-ки полезных систем счисления 5: 2,3,4,5,6. Из них 3 и 5 с полным периодом (равным N-1). Соответственно, системы счисления с максимальной длинной циклических чисел будут такие: k*N+3 и k*N+5, где k — целое положительное число.
Конкрентно для системы счисления 10 любые варианты циклических чисел легко вычисляются при наличии разложения числа N-1 на множители. Это же аналогично и для любой другой системы счисления, разумеется, но люди привыкли к десятичной, поэтому и вы тоже выбрали её.
Ваше направление исследует последствия деления на N для числа, которое является результатом операции деления. Это одно из направлений, в котром следует развивать наше понимание делимости. Но общее направление, включающее и ваше, включает дополнительно исследование остатков, получающихся при делении. Вариации на тему остатков могут быть довольно разнообразынми. Вариации на вашу тему, как мы видим, так же приводят к целому ряду направлений, и скорее всего, приведут к ещё большему количеству после более глубокого изучения, включая изучение уже существующих работ других авторов.
С точки зрения теории чисел остатки — это конечные поля и все их свойства. Эти свойства и дают мне основание утверждать всё то, что написано выше. Ваше направление движется случайным образом, поэтому в нём присутствуют и поля и ряды и что-то ещё. Для более качественного понимания темы вам нужно глубже понять ряды остатков (поля в терминах теории чисел). А в направлении чисел-результатов деления я и сам не знаю, что вам нужно понять, поскольку не занимался этим направлением. Но знаю одно — все показанные направления суть одно и то же, но с разных сторон. Поэтому сторону с остатками понимать нужно.
Подобные занятия увлекают, поэтому думаю, что вам будет интересно копать глубже. Результат копания может быть весьма и весьма фундаментально ценным. Хотя гарантий никто не даёт, потому что свойства числел могут довольно долго издеваться над исследователем, который выбрал не то направление исследования. А какое из них «то» никто не знает.
Кто-то реально участвует. Или вы хотите, что бы они участвовали именно в ваших исследованиях? Но тогда их нужно как-то убедить, а вы этого не сделали.
Вы не назвали ни одной конструктивной модели числа
На данном сайте можно ткнуть на псевдоним автора и перейти к списку его публикаций. Там есть такая модель. Она объясняет смысл и инволюций и идемпотентов и вашего предложения искать квадраты по модулю исследуемого числа.
Правда это всё следствия представленной модели, собственно алгоритма получения перечисленного в статье нет.
Хотя я повторю свои же слова — объектов, на которые можно «наматывать» числовой ряд, бесконечно много. Мой вариант исследует экспоненты, но есть, разумеется, и другие функции. Экспоненты проще для понимания, поскольку работа с ними сводится к привычной со школы работой с делением единицы на число, плюс набор законов там очень просто запоминается и эти законы повторяются для каждого показателя степени, а потому там всё единообразно, не нужно никаких специальных знаний из курса теории чисел. Но это для понимания. А для исследования, разумеется, нужны дополнительные знания из других областей математики.
Для примера скажу, что инволюции и идемпотенты есть лишь частный случай всё того же «наматывания» числа (отметок на нитке) на степенные функции. Помимо них есть и другие интересные варианты, которые точно так же помогают находить делители числа. Но это всё пока не помогает облегчать нахождение делителей, поскольку всё упирается в неясность способа такого поиска, более эффективного, нежели перебор делителей.
А вот известные в теории чисел закономерности при помощи предложенного объясняются (на мой взгляд) гораздо проще. Но это не то достижение, которое можно считать качественным шагом в сторону понимания сути числового ряда. Есть ряд других полезных моментов, но и они не решают имеющиеся важные проблемы. Поэтому я и не продолжаю размещать здесь статьи на эту тему.
Должен здесь не согласиться. Моя нитка контуров и полуконтуров на границах имеет всегда квадраты, а что у Вас?
А у меня просто отвлечённый пример, показывающий ваш подход по аналогии. Возьмите вместо линейки треугольник, квадрат или вообще что-то трёхмерное с нетривиальной схемой намотки — опять получите аналог вашего подхода. Здесь две составляющие — числовой ряд и наматывание. Форма предмета определяет закономерности намотки, а закономерности числового ряда накладываются на закономерности намотки, как отметки 70 и 100 см на нитке. Если не отделять закономерности намотки от закономерностей числового ряда — получится ерунда.
Роль квадратов в НРЧ еще не дооценивается до сих пор.
Хорошо, хорошо, только вы сложность алгоритма всё же посчитайте. И она будет пропорциональна корню из исследуемого числа.
Мне думается, что я не должен ожидать от читателя глубокого понимания моих работ
Читателю интересны приложения. Если приложений нет, то как заинтересовать читателя?
Приложение в виде сокращения количества операций, требуемых для факторизации, было бы интересным. Но к чему можно приложить алгоритм, который не сокращает количество требуемых операций, но требует от читателя внимательного изучения? Ведь он является более сложно устроенным, нежели простейший перебор делителей.
Люди ждут от науки повышения эффективности. Популярные статьи должны именно таким образом указывать на пользу от науки. Если повышения эффективности нет — это не популярная статья, это статья для тех, кто заинтересован в исследовании данной конкретной области. И разумеется, здесь таких очень мало. Но даже для них необходимость вникать в описание алгоритма, да ещё и самостоятельно догадываться о промежуточных шагах (или даже самостоятельно доказывать), не имея надежды на серьёзное ускорение той же факторизации (то есть не видя ощутимых улучшений по сравнению с ранее известным), не создаёт необходимой мотивации для подробного изучения ваших трудов.
В кольце вычетов по составному модулю надо научиться вычислять нетривиальные инволюции или идемпотенты. После этого вопрос будет закрыт так как я его разумею.
Ну да, только если сказать по другому, получится — нужно лишь научиться разлагать число на множители. После этого вопрос будет закрыт так как я его разумею.
меня удивляет ситуация запущенности и заброшенности проблем при наличии академических институтов и всяких математических центров.
В нашем мире давно пора привыкнуть к самым разным видам неэффективности. Вот вы, например, не предлагаете эффективное решение проблемы, а лишь указываете на различные подходы, которые менее эффективны нежели существующие методы факторизации. Точно так же и другие занимаются чем-то своим, возможно совершенно неэффективно занимаются, но их это устраивает, а чужие советы их не интересуют. Вы ведь тоже не готовы следовать советам о повышении эффективности? Вот так вот все вместе и пилим не там и не то.
Сложность поиска делителей перебором пропорциональна корню из исследуемого числа. В ваших алгоритмах сложность аналогична. Из этого следует бесполезность таких алгоритмов для задачи факторизации, ведь простой перебор делителей ничуть не хуже.
Но ваши поиски не совсем бесполезны. Хотя результаты вы выдаёте по мере нахождения и без оценки их значимости. Это снижает ценность найденного.
Вы видите ряд закономерностей при расположении чисел тем или иным образом, а потом делаете вывод о замечательных свойствах числового ряда, которые проявляются удивительным образом в ваших изысканиях. Но вот здесь стоит остановиться. И подумать.
Вы увлеклись тем или иным представлением числа и находите в нём какие-то закономерности, а потом без особых раздумий выкладываете информацию о находке. Но если серьёзно подумать, то получается очень простая штука — числовой ряд сам по себе имеет закономерности, а проекция ряда на разнообразные «интересные» структуры (вроде предлагаемых вами таблиц) всего лишь располагает закономерности числового ряда в соответствии со структурой выбранных таблиц.
Упрощённо — если наматывать нитку на метровую линейку, то мы получим строгую закономерность в виде интервалов по одному метру вдоль всей намотанной нитки. Теперь добавим на нитку отметку через каждые 70 сантиметров. После намотки получим сдвиг отметок на нитке относительно отметок от линейки на 30, 60, 10, 80 и т.д. сантиметров. Ваш подход анализирует конкретные цифры 30, 60, 10, 80 и т.д., но на самом деле закономерность очень простая: d=k1*n-k2*m, где k1,k2 — произвольные коэффициенты, n — интервал первой отметки, m — интервал второй отметки.
Имея общую формулу, мы сразу понимаем, что, например, наличие нуля (кратность десяти) в каждом сдвиге отметок не является «интересной» закономерностью, а просто вытекает из кратности самих отметок десяти. И точно так же можно сказать о многих других свойствах, которые вы выявляете — они просто выражение более общего закона. Но этот самый общий закон пока скрыт. И скрыт он, весьма вероятно, потому что вы увлекаетесь частностями, вроде той же кратности десяти всех интервалов между отметками на нитке.
С другой стороны, когда не знаешь истину, может подойти любой метод, а вдруг именно он откроет нам нужную закономерность? Пока не узнаешь — не поймёшь. Но всё же внимание к частностям, а за одно и отсутствие оценки своих достижений (самостоятельной и самокритичной оценки) легко уводит в сторону долгих, но малопродуктивных упражнений.
Поэтому повторюсь — оцените (самокритично) сложность получаемых алгоритмов. Ну и попробуйте всё же искать более общую закономерность.
Нет, следующий printf в том же самом цикле, что и первый.
Я воспользовался вашей аналогией и перенёс вами предложенную скобку на то место, куда предлагал это сделать в статье. При этом тело блока осталось прежним. И визуально блок остался бы тем же самым, если бы произошла замена скобок на верхнее и нижнее подчёркивание.
Должно быть вот так:
for ( int i = 0; i < 10; ++i)
¯ printf( "hello world" );
_ printf( "hello world again" );
Здесь расцветка и длина верхнего символа изменены стилями страницы, но суть именно такая. Нижняя и верхняя черта визуально ограничивают всё тот же двухстрочный блок.
Вы вместо упомянтых двух стилей предложили делать так:
Нет, не так. А вот так:
for ( int i = 0; i < 10; ++i)
{ printf( "hello world" );
} printf( "hello world again" );
То есть нижняя скобка сдвигается на строчку вверх. Иначе она так и будет занимать пустую строку. Но поскольку вместо скобки используется подчёркивание, всё выглядит как будто новые «скобки» выше и ниже блока кода.
Стандарт стоит поменять для того, что бы в нём было упоминание об альтернативном отображении текста. Не обязательно текст в таком виде сохранять, ведь IDE снова всё исправит при следующей загрузке. Но вот показать в стандарте удобный вариант отображения — это важно. Без стандартизации будет ситуация «кто в лес, кто по дрова».
Стилей по прежнему два, ведь не предлагается обязательно сохранять текст именно в таком виде. А если никто кроме конкретного разработчика не видит альтернативный стиль, значит для других его нет. Логично?
Смысл в удовлетворении разных желаний. Кто не хочет, тот не будет включать плагин, а кто хочет — сможет экономить много строк и не отказаться от привычного стиля в текстах, которые сохраняются на диск. Прозрачно, бесшовно, легко и непринуждённо. Как-то так.
Снова повторюсь — предлагаемые алгоритмы эквивалентны простому перебору делителей, а потому мало полезны на практике.
Но сама структура интересна. Поэтому её стоит изучать, только вот доносить результаты изучения не стоит с упором на алгоритмы, которые не дают практической пользы. Здесь аудитория условно «развлекательная», хотя и с техническим уклоном, поэтому некие закономерности без практической пользы здесь почти никому не нужны. И тем более, если практическая польза всё же предлагается (в виде алгоритмов), а на самом деле она ничтожна, то это ещё сильнее убивает восприятие найденного.
Закономерности натурального числового ряда интересны лишь тем, кто понимает, что даже без практической пользы сейчас они могут помочь при решении практических вопросов в будущем, путём упрощения достижения новых результатов с опорой на ранее достигнутое, хоть и не давшее никакой практической пользы. Я для себя вынес кое-что полезное из вашего подхода, но практическая польза для меня, опять же, лишь в выделении закономерностей, которые, как мне кажется, можно было бы использовать при изучении других направлений теории чисел.
С другой стороны понятно, что хочется заинтересовать читателей упоминанием про факторизацию чисел криптографического порядка, но если такая факторизация, как и прежде, остаётся несбыточной мечтой, то зачем раздражать людей? Неявно вы обманываете их ожидания. Видимо не со зла, но результат именно такой.
Я, не имея каких-то практических результатов или же не умея увлекательно рассказать о неких закономерностях, предпочитаю просто молчать. Зафиксировать результат исследования можно на сайтах вроде arxiv.org, там много подобных работ, а раздражения они не вызывают, поскольку очень мало кто их читает, но вам-то хочется застолбить приоритет? Для этого arxiv вполне подходит. Если же хочется поделится и услышать комментарии, то вы видите результат — без практической пользы и без увлекательной искры вы вряд ли здесь найдёте положительный отклик. Ну а с точки зрения именно математических достижений, подозреваю, что многие вами упоминаемые закономерности уже давно открыты, но так и лежат в каких-то научных статьях, недоступные для массового читателя, а потому с точки зрения математиков ваши выводы неинтересны (ведь давно известны, хотя и в узких кругах).
Ещё вариант — можно просто показать саму структуру и лёгкость обнаружения закономерностей с её помощью, но опять же, без ссылок на существующие работы по математике всё будет выглядеть как некая алхимия, когда рассуждают о математике, а результаты непонятно как классифицировать — то ли это не стоящее затрат времени сочинение очередного изобретателя, то ли это давно известные факты, то ли ещё что. Третий вариант (ещё что, включая открытия) крайне редок, надеюсь вы это понимаете, а потому и реакция ожидаемая — воспринимают как то ли глупость, то ли банальность.
Может быть стоит подойти примерно так — в математике известно, что… и далее сообщить некие закономерности, доказанные неким непонятным для большинства путём (в терминах колец, групп и т.д.), а потом предложить взглянуть на результаты с другой точки зрения и показать, например, ваши таблицы, объяснив, что с их помощью можно получить все перечисленные математические законы по сути на пальцах, без привлечения колец, полей и прочих методов теории чисел, которые не учат в средней школе. Но увлекательно подать такой материал непросто.
Обратной операцией к «прямой» считается такая, которая позволяет восстановить исходные данные перед выполнением прямой, располагая лишь ее результатом.
Я лишь повторюсь — разговор про определения.
По сути же — вы считаете, что всё нужно получать из результата, но у функций бывают множественные аргументы, от которых вы вот так легко отказываетесь. Отказавшись от аргументов, часть из которых могут быть известными, вы отказываетесь от лёгких способов решения задач, то есть предлагаете найти иголку в многомерном стоге сена вместо, например, простого бинарного поиска. Это неэффективно, а потому традиция здесь очень даже уместна.
И про сложение — если подходить к обратным операциям по вашему, то оно полностью аналогично умножению. Конечный результат разложения на множители предполагает нахождение всех множителей. Конечный результат разложения суммы на слагаемые так же предполагает её разложение на минимальные элементы — единицы. Для умножения действует основная теорема арифметики о единственности полного разложения, для сложения действует самоочевидная теорема о единственности способа разложения суммы на неделимые элементы — единицы.
Обратная операция для умножения — деление. Если вы хотите как-то по другому определить обратную операцию, то вам нужно быть готовым к противостоянию с традицией, что (уверяю вас) очень даже нелегко.
Разложение на множители, скорее, ближе к разложению в ряд. Хотя это всё вкусовщина о названиях.
Здесь целью является изучение предмета — натурального ряда чисел
Цель и метод её достижения могут очень сильно отличаться внешне. Вы нашли метод в виде изучения структуры сумм и разностей квадратов, при этом сам ряд натуральных чисел предполагает бесконечное количество методов изучения, хотя все они в итоге сведутся к чему-то единому. Но сил одного человека в принципе недостаточно для охвата некоего спектра методов, а потому вы точно не охватите задачу изучения числового ряда. А вот задача изучения структуры таблицы сумм и разностей квадратов вполне может быть решена одним человеком. Поэтому не разбрасывайтесь и дайте себе строгий отчёт в том, что вы изучаете конкретную структуру. Иначе море возможностей разбросает ваши слабые силы по удалённым островкам и результат будет околонулевым.
Большинство задач элементарной теории чисел относительно составного числа N могут быть решены только при наличии его мультипликативного разложения.
Да. Но цель факторизации сильно отличается от цели исследования структуры предложенной таблицы. Поэтому нужно выбрать что-то одно. Таблица позволяет охватить её одному человеку, а методы факторизации можно сочинять множеством способов, что означает отказ от концентрации на чём-то одном. Тут как в охоте на сотню зайцев.
Если цель — факторизация, то нужно сконцентрироваться на ней. Если цель — показ структуры, обнаруженной при исследовании сумм и разностей квадратов — нужно забыть о факторизации и подробно (с доказательствами) исследовать структуру, а потом выложить наиболее интересное, дающее возможность, например, выполнить факторизацию. Переход к факторизации должен быть выделен, описание факторизации на основе ранее показанной структуры должно быть кратким, в виде формул.
Длинное описание, смешивающее всё и сразу, плюс ещё числовые примеры, да ещё и не структурированное как следует, заставляет долго вдумываться, а большинство к такому занятию категорически не готово.
Но тем не менее, сама структура интересная. Я в ней увидел, например, доказательство того факта, что любое нечётное число можно представить в виде разности квадратов. А вот, например, доказательства утверждения (№3) про простоту числа, следующую из отсутствия одинаковых чисел в смежных столбцах — не увидел. Ещё увидел два утверждения №4. А в целом, повторюсь, плохо структурированный текст.
Наличие пары одинаковых чисел в смежных столбцах действительно интересно, но природа явления не раскрыта. То есть алгебраическое выражение, соответствующее ситуации с наличием такой пары, не является объяснением природы данной структуры. Непонятно, как появляются такие пары, почему они появляются для одних чисел и почему не появляются для других. Хотя, возможно, на это есть какие-то намёки в объяснениях про «лестницы», но весь текст до «лестниц» настраивает на несколько скептический взгляд, а потому внимательно прочитать далее не хватает мотивации.
По краткому изложению алгоритма в конце статьи видно, что для больших чисел он непригоден. В алгоритме предлагается построить два ряда сумм квадратов и далее искать в них одинаковые значения, но никак не упоминается тот факт, что даже если мы работаем с корнями из исследуемого числа, то при порядках чисел, используемых в криптографии, значения корней становятся столь большими, что никакой последовательный перебор значений в принципе не представляется возможным при сегодняшнем уровне вычислительной техники. Поэтому алгоритм неприменим для факторизации больших чисел (криптографических порядков). Хотя и с точки зрения доказанности данный алгоритм не выглядит впечатляюще.
Скорее всего доказательства (либо опровержение) утверждений из статьи выглядят довольно просто, в рамках алгебры из средней школы, поэтому такие вещи стоит привести. Можно убрать всё лишнее, не касающееся факторизации, но добавить доказательства каждого шага приведённого алгоритма. Правда, даже будучи доказанным, алгоритм так и останется нереализуемым для действительно больших чисел.
Ну и стоит напомнить, что факторизация некоторых очень больших чисел выполняется очень легко просто из-за того, что эти числа удачно попадают в ту нишу, в которой алгоритм факторизации работает превосходно. Но стоит взять другое число — и вся радость тут же куда-то исчезает. Чисто для примера, число Мерсенна 2^100-1 факторизуется чуть ли не на пальцах (сразу видно, что оно делится на 3, 5, 11, 31 и т.д.), а вот следующее (2^101-1) — уже без мощного компьютера не обойдётся.
Посмотрел код Java-библиотеки. Там стоит ряд ограничений, в зависимости от размера проверяемого числа. Для размера 1024 и более стоит насильственное урезание количества повторов до 2. То есть либо 1 проверка, либо две.
Почему это сделано? Очевидно, что ради скорости. При этом, если вспомним, что вероятность выбрать систему счисления, ложно свидетельствующую о простоте числа, составляет 1/4. Если принимаем повторные попытки за независимые испытания, то в серии из 2-х испытаний получаем вероятность ложного ответа, равную 1/16. И это против гарантированного результата, хоть и достигаемого за несколько большее время (видимо от 4-5 раз больше). На мой взгляд выбор в данной ситуации абсолютно очевиден и однозначен. Ну а установка такого явного ограничения на количество повторов внутри библиотеки, да ещё и без указания на это в документации, это просто кричащее предупреждение — срочно меняйте подход при генерации простых для криптографии!
Пугать я вас, разумеется, не собирался (хотя услышать более обоснованное мнение хотел, признаюсь, ведь многие склонны бросить слово и потом «замять»).
Но мне казалось, что раз мы совершаем повторное испытание при условии, что предыдущее дало один конкретный вариант из двух, то и подходить к оценке вероятности повторения ранее случившегося события (на том же испытуемом объекте) нужно с позиций условной вероятности.
Рад, что вы подробно описали свой ход мыслей. Кроме того, почитал ещё раз википедию, там тоже поддерживают ваш подход. Ну и признаюсь — вероятности изучал давно, а потому не уверен и в своей правоте.
Но тем не менее, если всё же говорить о времени выполнения теста, то очевидно, что предлагаемые вами 500 возведений в степень по модулю представляют из себя существенно большую нагрузку на процессор, нежели одно возведение в степень по модулю (для больших чисел) в случае предложенного выше алгоритма. А потому предложенный алгоритм имеет очевидное преимущество перед альтернативой в виде 500 (да пусть даже 10) возведений в степень по модулю.
Вообще, вместе с Java идут и исходники, надо подробнее будет посмотреть, как они реализовали этот тест. Раньше мельком заглядывал и видел какие-то ограничения по количеству возведений в степень.
Вероятность ошибки оценивается по единичному испытанию, а далее — по формулам теории вероятностей. Об этом в википедии написано достаточно подробно. Вы же приняли прямо пропорциональную зависимость, то есть игнорировали формулы из теории вероятностей. Попробуйте всё же выполнить расчёт правильно.
Это ещё быстро. Возможно, стоит повысить коэффициент на входе метода проверки, потому что от него зависит количество прогонов, ну а от количества — время.
Связи систем счисления очень простые. Систем счисления больших, чем число N просто не нужно привлекать. Всё, что больше N вычисляется на основе систем счисления до N.
В вашем примере для 7-ки полезных систем счисления 5: 2,3,4,5,6. Из них 3 и 5 с полным периодом (равным N-1). Соответственно, системы счисления с максимальной длинной циклических чисел будут такие: k*N+3 и k*N+5, где k — целое положительное число.
Конкрентно для системы счисления 10 любые варианты циклических чисел легко вычисляются при наличии разложения числа N-1 на множители. Это же аналогично и для любой другой системы счисления, разумеется, но люди привыкли к десятичной, поэтому и вы тоже выбрали её.
Ваше направление исследует последствия деления на N для числа, которое является результатом операции деления. Это одно из направлений, в котром следует развивать наше понимание делимости. Но общее направление, включающее и ваше, включает дополнительно исследование остатков, получающихся при делении. Вариации на тему остатков могут быть довольно разнообразынми. Вариации на вашу тему, как мы видим, так же приводят к целому ряду направлений, и скорее всего, приведут к ещё большему количеству после более глубокого изучения, включая изучение уже существующих работ других авторов.
Вариант с остатками поверхностно описан здесь.
С точки зрения теории чисел остатки — это конечные поля и все их свойства. Эти свойства и дают мне основание утверждать всё то, что написано выше. Ваше направление движется случайным образом, поэтому в нём присутствуют и поля и ряды и что-то ещё. Для более качественного понимания темы вам нужно глубже понять ряды остатков (поля в терминах теории чисел). А в направлении чисел-результатов деления я и сам не знаю, что вам нужно понять, поскольку не занимался этим направлением. Но знаю одно — все показанные направления суть одно и то же, но с разных сторон. Поэтому сторону с остатками понимать нужно.
Подобные занятия увлекают, поэтому думаю, что вам будет интересно копать глубже. Результат копания может быть весьма и весьма фундаментально ценным. Хотя гарантий никто не даёт, потому что свойства числел могут довольно долго издеваться над исследователем, который выбрал не то направление исследования. А какое из них «то» никто не знает.
Кто-то реально участвует. Или вы хотите, что бы они участвовали именно в ваших исследованиях? Но тогда их нужно как-то убедить, а вы этого не сделали.
На данном сайте можно ткнуть на псевдоним автора и перейти к списку его публикаций. Там есть такая модель. Она объясняет смысл и инволюций и идемпотентов и вашего предложения искать квадраты по модулю исследуемого числа.
Правда это всё следствия представленной модели, собственно алгоритма получения перечисленного в статье нет.
Хотя я повторю свои же слова — объектов, на которые можно «наматывать» числовой ряд, бесконечно много. Мой вариант исследует экспоненты, но есть, разумеется, и другие функции. Экспоненты проще для понимания, поскольку работа с ними сводится к привычной со школы работой с делением единицы на число, плюс набор законов там очень просто запоминается и эти законы повторяются для каждого показателя степени, а потому там всё единообразно, не нужно никаких специальных знаний из курса теории чисел. Но это для понимания. А для исследования, разумеется, нужны дополнительные знания из других областей математики.
Для примера скажу, что инволюции и идемпотенты есть лишь частный случай всё того же «наматывания» числа (отметок на нитке) на степенные функции. Помимо них есть и другие интересные варианты, которые точно так же помогают находить делители числа. Но это всё пока не помогает облегчать нахождение делителей, поскольку всё упирается в неясность способа такого поиска, более эффективного, нежели перебор делителей.
А вот известные в теории чисел закономерности при помощи предложенного объясняются (на мой взгляд) гораздо проще. Но это не то достижение, которое можно считать качественным шагом в сторону понимания сути числового ряда. Есть ряд других полезных моментов, но и они не решают имеющиеся важные проблемы. Поэтому я и не продолжаю размещать здесь статьи на эту тему.
А у меня просто отвлечённый пример, показывающий ваш подход по аналогии. Возьмите вместо линейки треугольник, квадрат или вообще что-то трёхмерное с нетривиальной схемой намотки — опять получите аналог вашего подхода. Здесь две составляющие — числовой ряд и наматывание. Форма предмета определяет закономерности намотки, а закономерности числового ряда накладываются на закономерности намотки, как отметки 70 и 100 см на нитке. Если не отделять закономерности намотки от закономерностей числового ряда — получится ерунда.
Хорошо, хорошо, только вы сложность алгоритма всё же посчитайте. И она будет пропорциональна корню из исследуемого числа.
Читателю интересны приложения. Если приложений нет, то как заинтересовать читателя?
Приложение в виде сокращения количества операций, требуемых для факторизации, было бы интересным. Но к чему можно приложить алгоритм, который не сокращает количество требуемых операций, но требует от читателя внимательного изучения? Ведь он является более сложно устроенным, нежели простейший перебор делителей.
Люди ждут от науки повышения эффективности. Популярные статьи должны именно таким образом указывать на пользу от науки. Если повышения эффективности нет — это не популярная статья, это статья для тех, кто заинтересован в исследовании данной конкретной области. И разумеется, здесь таких очень мало. Но даже для них необходимость вникать в описание алгоритма, да ещё и самостоятельно догадываться о промежуточных шагах (или даже самостоятельно доказывать), не имея надежды на серьёзное ускорение той же факторизации (то есть не видя ощутимых улучшений по сравнению с ранее известным), не создаёт необходимой мотивации для подробного изучения ваших трудов.
Ну да, только если сказать по другому, получится — нужно лишь научиться разлагать число на множители. После этого вопрос будет закрыт так как я его разумею.
В нашем мире давно пора привыкнуть к самым разным видам неэффективности. Вот вы, например, не предлагаете эффективное решение проблемы, а лишь указываете на различные подходы, которые менее эффективны нежели существующие методы факторизации. Точно так же и другие занимаются чем-то своим, возможно совершенно неэффективно занимаются, но их это устраивает, а чужие советы их не интересуют. Вы ведь тоже не готовы следовать советам о повышении эффективности? Вот так вот все вместе и пилим не там и не то.
Сложность поиска делителей перебором пропорциональна корню из исследуемого числа. В ваших алгоритмах сложность аналогична. Из этого следует бесполезность таких алгоритмов для задачи факторизации, ведь простой перебор делителей ничуть не хуже.
Но ваши поиски не совсем бесполезны. Хотя результаты вы выдаёте по мере нахождения и без оценки их значимости. Это снижает ценность найденного.
Вы видите ряд закономерностей при расположении чисел тем или иным образом, а потом делаете вывод о замечательных свойствах числового ряда, которые проявляются удивительным образом в ваших изысканиях. Но вот здесь стоит остановиться. И подумать.
Вы увлеклись тем или иным представлением числа и находите в нём какие-то закономерности, а потом без особых раздумий выкладываете информацию о находке. Но если серьёзно подумать, то получается очень простая штука — числовой ряд сам по себе имеет закономерности, а проекция ряда на разнообразные «интересные» структуры (вроде предлагаемых вами таблиц) всего лишь располагает закономерности числового ряда в соответствии со структурой выбранных таблиц.
Упрощённо — если наматывать нитку на метровую линейку, то мы получим строгую закономерность в виде интервалов по одному метру вдоль всей намотанной нитки. Теперь добавим на нитку отметку через каждые 70 сантиметров. После намотки получим сдвиг отметок на нитке относительно отметок от линейки на 30, 60, 10, 80 и т.д. сантиметров. Ваш подход анализирует конкретные цифры 30, 60, 10, 80 и т.д., но на самом деле закономерность очень простая: d=k1*n-k2*m, где k1,k2 — произвольные коэффициенты, n — интервал первой отметки, m — интервал второй отметки.
Имея общую формулу, мы сразу понимаем, что, например, наличие нуля (кратность десяти) в каждом сдвиге отметок не является «интересной» закономерностью, а просто вытекает из кратности самих отметок десяти. И точно так же можно сказать о многих других свойствах, которые вы выявляете — они просто выражение более общего закона. Но этот самый общий закон пока скрыт. И скрыт он, весьма вероятно, потому что вы увлекаетесь частностями, вроде той же кратности десяти всех интервалов между отметками на нитке.
С другой стороны, когда не знаешь истину, может подойти любой метод, а вдруг именно он откроет нам нужную закономерность? Пока не узнаешь — не поймёшь. Но всё же внимание к частностям, а за одно и отсутствие оценки своих достижений (самостоятельной и самокритичной оценки) легко уводит в сторону долгих, но малопродуктивных упражнений.
Поэтому повторюсь — оцените (самокритично) сложность получаемых алгоритмов. Ну и попробуйте всё же искать более общую закономерность.
Я воспользовался вашей аналогией и перенёс вами предложенную скобку на то место, куда предлагал это сделать в статье. При этом тело блока осталось прежним. И визуально блок остался бы тем же самым, если бы произошла замена скобок на верхнее и нижнее подчёркивание.
Должно быть вот так:
Здесь расцветка и длина верхнего символа изменены стилями страницы, но суть именно такая. Нижняя и верхняя черта визуально ограничивают всё тот же двухстрочный блок.
Нет, не так. А вот так:
То есть нижняя скобка сдвигается на строчку вверх. Иначе она так и будет занимать пустую строку. Но поскольку вместо скобки используется подчёркивание, всё выглядит как будто новые «скобки» выше и ниже блока кода.
Смысл в удовлетворении разных желаний. Кто не хочет, тот не будет включать плагин, а кто хочет — сможет экономить много строк и не отказаться от привычного стиля в текстах, которые сохраняются на диск. Прозрачно, бесшовно, легко и непринуждённо. Как-то так.
Но сама структура интересна. Поэтому её стоит изучать, только вот доносить результаты изучения не стоит с упором на алгоритмы, которые не дают практической пользы. Здесь аудитория условно «развлекательная», хотя и с техническим уклоном, поэтому некие закономерности без практической пользы здесь почти никому не нужны. И тем более, если практическая польза всё же предлагается (в виде алгоритмов), а на самом деле она ничтожна, то это ещё сильнее убивает восприятие найденного.
Закономерности натурального числового ряда интересны лишь тем, кто понимает, что даже без практической пользы сейчас они могут помочь при решении практических вопросов в будущем, путём упрощения достижения новых результатов с опорой на ранее достигнутое, хоть и не давшее никакой практической пользы. Я для себя вынес кое-что полезное из вашего подхода, но практическая польза для меня, опять же, лишь в выделении закономерностей, которые, как мне кажется, можно было бы использовать при изучении других направлений теории чисел.
С другой стороны понятно, что хочется заинтересовать читателей упоминанием про факторизацию чисел криптографического порядка, но если такая факторизация, как и прежде, остаётся несбыточной мечтой, то зачем раздражать людей? Неявно вы обманываете их ожидания. Видимо не со зла, но результат именно такой.
Я, не имея каких-то практических результатов или же не умея увлекательно рассказать о неких закономерностях, предпочитаю просто молчать. Зафиксировать результат исследования можно на сайтах вроде arxiv.org, там много подобных работ, а раздражения они не вызывают, поскольку очень мало кто их читает, но вам-то хочется застолбить приоритет? Для этого arxiv вполне подходит. Если же хочется поделится и услышать комментарии, то вы видите результат — без практической пользы и без увлекательной искры вы вряд ли здесь найдёте положительный отклик. Ну а с точки зрения именно математических достижений, подозреваю, что многие вами упоминаемые закономерности уже давно открыты, но так и лежат в каких-то научных статьях, недоступные для массового читателя, а потому с точки зрения математиков ваши выводы неинтересны (ведь давно известны, хотя и в узких кругах).
Ещё вариант — можно просто показать саму структуру и лёгкость обнаружения закономерностей с её помощью, но опять же, без ссылок на существующие работы по математике всё будет выглядеть как некая алхимия, когда рассуждают о математике, а результаты непонятно как классифицировать — то ли это не стоящее затрат времени сочинение очередного изобретателя, то ли это давно известные факты, то ли ещё что. Третий вариант (ещё что, включая открытия) крайне редок, надеюсь вы это понимаете, а потому и реакция ожидаемая — воспринимают как то ли глупость, то ли банальность.
Может быть стоит подойти примерно так — в математике известно, что… и далее сообщить некие закономерности, доказанные неким непонятным для большинства путём (в терминах колец, групп и т.д.), а потом предложить взглянуть на результаты с другой точки зрения и показать, например, ваши таблицы, объяснив, что с их помощью можно получить все перечисленные математические законы по сути на пальцах, без привлечения колец, полей и прочих методов теории чисел, которые не учат в средней школе. Но увлекательно подать такой материал непросто.
Я лишь повторюсь — разговор про определения.
По сути же — вы считаете, что всё нужно получать из результата, но у функций бывают множественные аргументы, от которых вы вот так легко отказываетесь. Отказавшись от аргументов, часть из которых могут быть известными, вы отказываетесь от лёгких способов решения задач, то есть предлагаете найти иголку в многомерном стоге сена вместо, например, простого бинарного поиска. Это неэффективно, а потому традиция здесь очень даже уместна.
И про сложение — если подходить к обратным операциям по вашему, то оно полностью аналогично умножению. Конечный результат разложения на множители предполагает нахождение всех множителей. Конечный результат разложения суммы на слагаемые так же предполагает её разложение на минимальные элементы — единицы. Для умножения действует основная теорема арифметики о единственности полного разложения, для сложения действует самоочевидная теорема о единственности способа разложения суммы на неделимые элементы — единицы.
Разложение на множители, скорее, ближе к разложению в ряд. Хотя это всё вкусовщина о названиях.
Цель и метод её достижения могут очень сильно отличаться внешне. Вы нашли метод в виде изучения структуры сумм и разностей квадратов, при этом сам ряд натуральных чисел предполагает бесконечное количество методов изучения, хотя все они в итоге сведутся к чему-то единому. Но сил одного человека в принципе недостаточно для охвата некоего спектра методов, а потому вы точно не охватите задачу изучения числового ряда. А вот задача изучения структуры таблицы сумм и разностей квадратов вполне может быть решена одним человеком. Поэтому не разбрасывайтесь и дайте себе строгий отчёт в том, что вы изучаете конкретную структуру. Иначе море возможностей разбросает ваши слабые силы по удалённым островкам и результат будет околонулевым.
Да. Но цель факторизации сильно отличается от цели исследования структуры предложенной таблицы. Поэтому нужно выбрать что-то одно. Таблица позволяет охватить её одному человеку, а методы факторизации можно сочинять множеством способов, что означает отказ от концентрации на чём-то одном. Тут как в охоте на сотню зайцев.
Если цель — факторизация, то нужно сконцентрироваться на ней. Если цель — показ структуры, обнаруженной при исследовании сумм и разностей квадратов — нужно забыть о факторизации и подробно (с доказательствами) исследовать структуру, а потом выложить наиболее интересное, дающее возможность, например, выполнить факторизацию. Переход к факторизации должен быть выделен, описание факторизации на основе ранее показанной структуры должно быть кратким, в виде формул.
Длинное описание, смешивающее всё и сразу, плюс ещё числовые примеры, да ещё и не структурированное как следует, заставляет долго вдумываться, а большинство к такому занятию категорически не готово.
Но тем не менее, сама структура интересная. Я в ней увидел, например, доказательство того факта, что любое нечётное число можно представить в виде разности квадратов. А вот, например, доказательства утверждения (№3) про простоту числа, следующую из отсутствия одинаковых чисел в смежных столбцах — не увидел. Ещё увидел два утверждения №4. А в целом, повторюсь, плохо структурированный текст.
Наличие пары одинаковых чисел в смежных столбцах действительно интересно, но природа явления не раскрыта. То есть алгебраическое выражение, соответствующее ситуации с наличием такой пары, не является объяснением природы данной структуры. Непонятно, как появляются такие пары, почему они появляются для одних чисел и почему не появляются для других. Хотя, возможно, на это есть какие-то намёки в объяснениях про «лестницы», но весь текст до «лестниц» настраивает на несколько скептический взгляд, а потому внимательно прочитать далее не хватает мотивации.
По краткому изложению алгоритма в конце статьи видно, что для больших чисел он непригоден. В алгоритме предлагается построить два ряда сумм квадратов и далее искать в них одинаковые значения, но никак не упоминается тот факт, что даже если мы работаем с корнями из исследуемого числа, то при порядках чисел, используемых в криптографии, значения корней становятся столь большими, что никакой последовательный перебор значений в принципе не представляется возможным при сегодняшнем уровне вычислительной техники. Поэтому алгоритм неприменим для факторизации больших чисел (криптографических порядков). Хотя и с точки зрения доказанности данный алгоритм не выглядит впечатляюще.
Скорее всего доказательства (либо опровержение) утверждений из статьи выглядят довольно просто, в рамках алгебры из средней школы, поэтому такие вещи стоит привести. Можно убрать всё лишнее, не касающееся факторизации, но добавить доказательства каждого шага приведённого алгоритма. Правда, даже будучи доказанным, алгоритм так и останется нереализуемым для действительно больших чисел.
Ну и стоит напомнить, что факторизация некоторых очень больших чисел выполняется очень легко просто из-за того, что эти числа удачно попадают в ту нишу, в которой алгоритм факторизации работает превосходно. Но стоит взять другое число — и вся радость тут же куда-то исчезает. Чисто для примера, число Мерсенна 2^100-1 факторизуется чуть ли не на пальцах (сразу видно, что оно делится на 3, 5, 11, 31 и т.д.), а вот следующее (2^101-1) — уже без мощного компьютера не обойдётся.
Почему это сделано? Очевидно, что ради скорости. При этом, если вспомним, что вероятность выбрать систему счисления, ложно свидетельствующую о простоте числа, составляет 1/4. Если принимаем повторные попытки за независимые испытания, то в серии из 2-х испытаний получаем вероятность ложного ответа, равную 1/16. И это против гарантированного результата, хоть и достигаемого за несколько большее время (видимо от 4-5 раз больше). На мой взгляд выбор в данной ситуации абсолютно очевиден и однозначен. Ну а установка такого явного ограничения на количество повторов внутри библиотеки, да ещё и без указания на это в документации, это просто кричащее предупреждение — срочно меняйте подход при генерации простых для криптографии!
Но мне казалось, что раз мы совершаем повторное испытание при условии, что предыдущее дало один конкретный вариант из двух, то и подходить к оценке вероятности повторения ранее случившегося события (на том же испытуемом объекте) нужно с позиций условной вероятности.
Рад, что вы подробно описали свой ход мыслей. Кроме того, почитал ещё раз википедию, там тоже поддерживают ваш подход. Ну и признаюсь — вероятности изучал давно, а потому не уверен и в своей правоте.
Но тем не менее, если всё же говорить о времени выполнения теста, то очевидно, что предлагаемые вами 500 возведений в степень по модулю представляют из себя существенно большую нагрузку на процессор, нежели одно возведение в степень по модулю (для больших чисел) в случае предложенного выше алгоритма. А потому предложенный алгоритм имеет очевидное преимущество перед альтернативой в виде 500 (да пусть даже 10) возведений в степень по модулю.
Вообще, вместе с Java идут и исходники, надо подробнее будет посмотреть, как они реализовали этот тест. Раньше мельком заглядывал и видел какие-то ограничения по количеству возведений в степень.