Новый инвариант натурального числа. Теорема и доказательство
Ранее на Хабре была опубликована работа автора об инварианте числа (здесь). Еще ранее в работе [1] приводятся сведения об оригинальной концепции моделирования натурального ряда чисел и отдельного числа с целью установления свойств, слабо зависящих или вообще не зависящих от разрядности чисел. Ранее не приводились теоремы для доказательства истинности положений, которые используются автором в работах. Анализ комментариев к работам показал насколько недоверчиво читательская аудитория относится к подобным работам и утверждениям. Пределы такого недоверия от оценок «Чушь; Осторожно: псевдонаучный бред; Переливание из пустого в порожнее…» до «Да, мне это безусловно покажется интересным, если…». Это лишь немногие мнения читателей, высказавших свое восприятие работы, свое мнение о ней. Спасибо им за проявленное внимание к работе. Кстати, эти мнения и оценки получили одобрение и многих других читателей не оставшихся безучастными. Им тоже спасибо за внимание. Так вот это и побудило меня привести теорему об ф-инварианте и ее доказательство. Очень надеюсь, что возможно приведенное доказательство истинности утверждения об ф-инварианте (новом свойстве числа с вычисляемым показателем), несколько скорректирует мнения читателей и породит у них сомнения в правильности их, возможно, весьма поспешных первоначальных оценок. Каждый автор, посвятивший много времени и сил определенной работе, воспринимает со временем свою работу почти как очевидную, изложение работы при стремлении сделать его кратким, содержит массу деталей «по умолчанию», что делает ее, по-видимому, малодоступной для понимания другими людьми.
О подходе и его новизне Тема этой и других моих опубликованных работ непосредственно касается безопасности и, в частности, информационной безопасности на всех тех уровнях, где используется криптографическая защита. То, что в публикациях приводятся математические соотношения на уровне элементарной математики, не делает проблему менее сложной или более доступной. Просто автор стремится сделать изложение доступным и ясным для более широкого круга читателей-хабровчан. Речь в моих работах идет о совершенно новом подходе к решению частной, но важной проблемы безопасности (здесь), которая связана теснейшим образом со многими другими проблемами. То направление в области факторизации, которое развивается на мировом уровне в настоящее время, автор считает тупиковым, а практика (критерий истины) это подтверждает. Нужен новый взгляд на задачу факторизации, на натуральный ряд чисел (НРЧ), на числовую систему в целом, которая, как оказалось, практически не изучена. Необходима теория НРЧ и отдельного составного нечетного натурального числа (сннч), необходимы модели этих объектов, учитывающие требования и запросы современной практики. Ничего подобного сегодня скопировать просто негде. Автор в меру своих способностей и возможностей творит самостоятельно, то что пока скрыто от внимания других и в серии публикаций делится своими находками с общественностью, понимая, что все новое, чаще всего, во все времена принимается в штыки. Причины этого явления весьма разнообразны и обсуждать их здесь и сейчас не время.
Очень надеюсь найти сподвижников в среде программистов, так как сам программистом не являюсь. Материал о новых результатах и подходах распределен небольшими дозами в статьях автора. Для тех, кто сочтет интересным это новое и перспективное направление есть возможность ознакомиться с содержанием моих работ на Хабре. К числу новых понятий с их определениями относятся: классы (левых и правых) нечетных чисел, контур, предельный контур, полуконтур, интервал НРЧ, их длины, нумерация, границы, ф-инвариант числа, интервальная и нумерационная модели составного нечетного числа [3,4], формулы для вычисления характеристик перечисленных объектов. Введение этих новых понятий и обозначений обеспечивает решение нового круга задач, формулируемых относительно натуральных чисел, главная из которых — факторизация числа.
На простые, казалось бы, вопросы о натуральных или целых числах сегодня негде найти ответы. Примерами вопросов могут быть следующие.Как определить нетривиальные инволюции и идемпотенты конечного числового кольца вычетов по модулю сннч N без предварительного разложения N на множители? Как находить корни сравнения по модулю в таком кольце, без тотального перебора элементов? Как находить четверки квадратичных вычетов, значения которых порождаются единственным квадратом без разложения N на множители? Пока ответы на эти и другие вопросы автору приходится отыскивать самостоятельно. Жду отзыва от заинтересованного читателя (лей) по существу сформулированных вопросов и возможно каких либо других. Для раскрытия сущности вопросов требуется иная менее элементарная математика, но пока касаться ее здесь, по-видимому, преждевременно.
Обоснование подхода Введем обозначения для номеров крайних контуров интервала для сннч N: для меньшего номера s — start, для большего номера f — finish. Очевидно, левая граница многоконтурного интервала, представляющего левое (Nл≡3(mod4)) нечетное число совпадает с левой границей меньшего s-го контура Гл (s) = (2s — 1)2, а правая граница этого многоконтурного интервала с правой границей левого полуконтура контура с большим номером f, т.е. Гп (f) = (2f)2. Левая граница многоконтурного интервала, представляющего правое (Nп≡1(mod4)) нечетное число Nп совпадает с левой границей правого полуконтура меньшего s-го контура Гл (s) = (2s)2, а правая граница интервала для N совпадает с правой границей большего контура с номером f, т.е. Гп (f) = (2f + 1)2. Принятые обозначения несколько громоздкие, но семантически оправданы и удобны для понимания и запоминания.
В предшествующей работе (здесь) для нумерационной модели натурального нечетного составного числа N, т.е. полуконтура в предельном контуре получаем сумму номеров путем перехода от длин контуров к их номерам в виде kд/2 + Σti ki, где t = m-1, i=1(1)t.
ТЕОРЕМА 1. (Об инварианте составного нечетного числа. Одиночный интервал). Произвольному интервалу в НРЧ с длиной N, составленному из последовательных контуров числовой оси и с квадратами натуральных чисел в качестве границ интервала, соответствует сумма kд/2 + Σti ki = kп (N)/2, где t = m-1, i=1(1)t, номеров, образующих интервал контуров, и половины номера контура с дополняющим kд/2 полуконтуром, равная половине номера предельного контура (ф-инварианту) числа N.
Д о к, а з, а т е л ь с т в о выполним отдельно для натуральных нечетных правых Nп и левых Nл составных чисел. Идея доказательства состоит в следующем. С одной стороны, показывается, что число N представляется как разность квадратов (граничных точек интервала) в самом общем виде. С другой стороны, вычисляется сумма номеров контуров и полуконтура, которая путем приравнивания ее к половине номера предельного контура для составного числа N = Nп или N = Nл и последующего преобразования границ также приводится к разности граничных точек крайних элементов суммы, равной числу N.
Начнем с правого числа N = Nп. Подставим в сумму нумерационной модели обозначения s и f для номеров крайних контуров, введенных ранее в модели нечетных составных чисел. Воспользуемся формулой для суммы элементов отрезка НРЧ, приведенной в работе [2, стр. 160]. s/2+(s+1)+(s+2)+…+f =>½(f+s +1)(f-s-1+1)+s/2 =>½(f2+sf+f -sf -s2-s)+s/2 = ½(f2+ f-s2). Преобразуем конечное выражение к виду соответствующему разности границ интервала для исследуемого числа Nп, а именно, (2f + 1)2 — (2s)2. Это достигается приравниванием найденного выражения половине номера предельного контура числа Nп, т. е. kп (N)/2 = (Nп-1)/8 =½(f2+f-s2).Средняя и правая части равенства преобразуются к виду разности границ представляющего число интервала Nп = 4f2 + 4f + 1 — 4s2 =(2f +1)2-(2s)2.Этим доказательство для случая N = Nп завершается.
Теперь выполним доказательство для случая N = Nл. Подставим в сумму нумерационной модели обозначения s и f для номеров крайних контуров, как и ранее. Тогда для этого случая имеем: s+(s+1)+(s+2)+…+ (f-1) + f/2 => ½(f-1+s)(f-s)+f/2 =>½(f2+sf-f-sf-s2+s)+f/2 = ½(f2-s2+s).Выполним преобразование конечного выражения, приводящее его к виду разности границ исследуемого числа N = Nл, а именно, к виду (2f)2 — (2s — 1)2. Это достигается приравниванием найденного выражения половине номера предельного контура числа Nл, т. е. kп (N)/2 = (Nл + 1)/8 =½(f2 + s — s2).Средняя и правая части равенства преобразуются к виду разности границ представляющего число интервала Nл = 4f2 — 4s — 1 — 4s2 = (2f)2 — (2s — 1)2.Этим доказательство для случая N = Nл завершается и теорема полностью доказана.
В основу доказательства положено вычисление границ для многоконтурного интервала и показывается, что разность таких границ у произвольного интервала приводит к одинаковому результату для интервала с длиной равной N. Другой путь доказательства теоремы возможен с использованием принципа формирования разбиений числа kп (N)/2 на разное число частей mi с ограничениями вида (kij+1 = ki (j+1)) на части разбиения. При этом подходе роль разбиваемого числа играет ф-инвариант kп (N)/2 числа N. Действительно, само сннч N можно разбить на части (контуры) несколькими способами, при этом части разбиения будут удовлетворять накладываемым требованиям (ограничениям на значения).
ТЕОРЕМА 2. (Об инварианте составного нечетного числа. Множество интервалов). Всем многоконтурным интервалам с постоянной длиной N и текущими номерами i =1(1)…, представляющими составное нечетное натуральное число N, в разных областях числовой оси, имеющим в качестве границ квадраты натуральных чисел разной четности, соответствуют суммы разного количества mi слагаемых (номеров kij) следующих непрерывно один за другим контуров (kij+1 = ki (j+1)) и одного крайнего полуконтура таких, что значения сумм постоянны и зависят только от числа N. kдi/2 + Σtj kij = kп (N)/2, где t = mi -1, j = 1(1)t, i =1(1)… Д о к, а з, а т е л ь с т в о выполняется с использованием теоремы 1 непосредственным построением таких сумм.
В теореме сформулированы утверждения о нескольких фактах: — во-первых, для сннч N существует (i > 1) более одного представляющего сннч N интервала в разных участках НРЧ; — во-вторых, каждому из таких интервалов соответствует непрерывная последовательность контуров (с номерами kij), каждая сумма номеров которых и номера полуконтура kдi/2, содержит отличное от сумм других интервалов количество mi и состав слагаемых; — в-третьих, границами всех интервалов являются различные пары квадратов натуральных чисел разной четности; — в-четвертых, длина всех представляющих интервалов одинакова, равна N, а соответствующие суммы номеров контуров также постоянны и определяются только значением ф-инварианта числа N, но не местоположением интервала в НРЧ; — в-пятых, все слагаемые в разных суммах (кроме номера крайнего полуконтура) представляют отрезок НРЧ, и монотонно увеличиваются на единицу от одного меньшего слагаемого к следующему большему слагаемому (kij+1 = ki (j+1)).
Другими словами, значение суммы номеров контуров и номера дополнительного полуконтура для сннч N инвариантно по отношению к числу слагаемых, к местоположению интервала в НРЧ, т.е. к значениям границ интервала, к значениям слагаемых в сумме.
Пример 1. Задано сннч N = Nл = 231, крайний полуконтур справа. Числу 231 соответствует номер предельного контура kп (N = 231) = 58. Ф-инвариант сннч равен kп (N)/2 = 29, т.е. половине номера предельного контура. Требуется сформировать разбиения числа 29, подчиненные ограничениям на части, для ф-инварианта.Предварительно выпишем представление ф-инварианта сннч N суммами номеров контуров. Таких сумм три:29 = 3 + 4 + 5 + 6 + 7 + 8/2;29 = 7 + 8 + 9 + 10/2;29 = 19 + 20/2. Так как суммируются номера контуров, следующие подряд один за другим, и половина номера крайнего контура, соответствующего левому полуконтуру контура с большим номером, то легко определяется представляемое число N, как сумма длин примыкающих друг к другу контуров и полуконтура: — для первого разбиения N = 8•3 +8•4 +8•5 +8•6 +8•7 +8•8/2 -1 = 24 +32 +40 +48 +56 +32 -1 = 231; — для второго разбиения N = 8•7 + 8•8 + 8•9 + 8•10/2 — 1 = 56 + 64 + 72 + 40 — 1 = 231; — для третьего разбиения N = 8•19 +8•20/2 — 1 = 152 + 80 — 1 = 231. Такие вычисления показывают, что число 231 представимо в НРЧ двумя многоконтурными интервалами и третий интервал состоит из одного полного контура и одного полуконтура предельного контура, примыкающего справа. Длина каждого интервала равна разности его границ Гп (i) — Гл (i), т. е. число N представляется разностью трех (i = 1(1)3) разных пар квадратов (границ интервалов).
Далее, вспоминая, что границы контуров и полуконтуров — полные квадраты и используя формулы для границ контуров и полуконтуров, определим значения для граничных элементов каждого представляющего интервала.Для 1-го интервала имеем 29 = 3 + 4 + 5 + 6 + 7 + 8/2; Гп1(8/2) = (2•8)2 = 256; Гл1(3) = (2•3 — 1)2 = 25; и Гп (i = 1) — Гл (i = 1) = (16)2 — (5)2 = 256 — 25 = 231 = (16 + 5)(16 — 5) = 21•11 = 231.
Для 2-го интервала имеем 29 = 7 + 8 + 9 + 10/2; Гп2(10/2) = (2•10)2 = 400; Гл2(7) = (2•7 — 1)2 = 169; и Гп (i = 2) — Гл (i = 2) = (20)2 — (13)2 = 400 — 169 = 231 = (20 + 13)(20 — 13) = 33•7 = 231.
Для 3-го интервала имеем 29 = 19 + 20/2; Гп3(20/2) = (2•20)2 = 1600; Гл3(19) = (2•19 — 1)2 = 1369; и тогда Гп (i = 3) — Гл (i = 3) = (40)2 — (37)2 = 1600 — 1369 = 231 = (40 + 37)(40 — 37) = 77•3 = 231.Располагая границами (парами квадратов) для каждого из трех интервалов для одного сннч N, легко получаем разные разложения числа N на сомножители.
Существует еще один интервал с границами — квадратами, между которыми лежит составное нечетное число N = 231. Его границы — границы предельного контура для числа 231 находятся совсем просто: левая Гл4(k = 58) =((231 — 1)/2)2 = (115)2 = 13225, правая Гп4(k = 58) =((231 + 1)/2)2 = (116)2 = 13456, Длина интервала-полуконтура в предельном контуре равнаN = Гп4(k = 58) — Гл4(k = 58) = ((231+1)/2)2 — ((231–1)/2)2 = (116)2 — (115)2 = 13456 — 13225 = 231.
Заключение Рассмотренный материал представляет собой отличный от существующего традиционного подход моделирования НРЧ и сннч N, обладающий новизной. Числовой пример иллюстрирует схему действий, легко преобразуемую в алгоритм с возможностью исключения перебора вариантов. Требуется только закрыть вопрос (создание программы) для получения специальных разбиений (или) даже единственного специального разбиения ф-инварианта. Путь решения этой задачи предложен (здесь). Литература[1] Ваулин А. Е., Пилькевич С.В. «Фундаментальные структуры натурального ряда чисел» — Интеллектуальные системы. Труды Седьмого международного симпозиума. Под ред. К.А. Пупкова.– М.: РУСАКИ, 2006. — с. 384–387[2] Бронштейн И. Н., Семендяев К.А. Справочник по математике для инженеров и учащихся ВТУЗов._М.: ГИТТЛ, 1954. -608с[3] Холл М. Комбинаторика. -М.: Мир, 1970. — 424 с.[4] Эндрюс Г. Теория разбиений. -М.: Наука ГРФМЛ,1982. — 256 с.
