Comments 29
Моя расшифровка первых двух параграфов:
Для числа N (подразумеваемого вида N=pq, p, q различные нечётные простые, для примера рассматривается 323=17*19) рассматриваются кортежи
(k² mod N, N-k, k, N-2k, (N²-1)/4 + k²-kN, [(N²-1)/4 + k²] mod N, 2k-1, (N-k²) mod N) , k пробегает значения от 1 до (N-1)/2.
Наблюдение: если (N²-1)/4 + k² делится на p, то либо (N²-1)/4 + (k-1)² делится на p, либо (N²-1)/4 + (k+1)² делится на p. (доказательство очевидно, автору по-видимому тоже)
Кортежи для k, для которых k² < N либо [(N²-1)/4 + k²-kN] < N названы "тривиальными", дальше автор немного размышляет что при некоторых N тривиальными могут оказаться все кортежи.
Наблюдение: существует последовательные четыре значения k, такие что (N²-1)/4 + k² делится на p/q для первых двух и q/p для вторых двух (опять же очевидно, но рассуждение автора не выглядит строгим доказательством).
Наблюдение: для пары k1 = ap, k2 = bq = ap + 2m, существует l : l²<N, (ap+m)² = sN+l² ("квадратичные вычеты в этих центральных точках всегда оказываются полными квадратами").
Утверждение без ограничений тривиально неверно для p=17, q=19, a=1, b=3: k1=17, k2=57, "центральная точка" 37, 37² mod 323 = 77. (ap+m)² сравнимо с m² ((ap+m)² = [(ap+bq)/2]² ~ [(ap+bq)/2]²-abN = [(bq-ap)/2]² = m²), а потому утверждение верно при m²<N.
Наблюдение: если 2k-1 кратно p, то (N²-1)/4 + k² также кратно p, равно как и (N²-1)/4 + (k-1)². Автором представлено без доказательства, проверяется тупой подстановкой k=(ap+1)/2.
Все пересказанные утверждения математически тривиальны, обильно пересыпаны авторской терминологией, какими-то дикими аббревиатурами и обозначениями с кириллицей.
Мой личный вердикт: барахло.
Как обычно у подобных статей, надо обязательно ввернуть историческую справку, сравнить себя со всякими гигантами прошлого и упомянуть про актуальность задачи. Автор, вам ЧСВ не жмет? Если есть что-то реально интересное/полезное в статье, то ничем этим ее разбавлять не надо.
Что касается статьи, то автор лишь заметил какие-то красивые на его взгляд паттерны без какого-либо объяснения их. Это уровень: Давайте выпишем все числа по спирализаметим, что простые числа выстариваются в прямые, навернем каких-то странных названий для них. Многие начинающие математики этим занимаются, но городить из этого аж статьи - это такое себе.
Какие-то аж таблицы навернули. Але, у вас там фактически только четвертая колонка хоть какой-то смысл несет (Квадратичные вычеты), остальные тривиальны - это i, N-i и N-2i. Но зато можно разными цветами что-то раскрасить, да. Ну вот выписали вы квадратичные вычеты. Ой, они повторяются! Сами же сослались на то, что это известный факт. Поэтому у вас строки "дублируются".
Попытки визуально что-то доказать в теории чисел - редко работают. И если какой-то паттерн и оказывается правильным, то за ним стоит простое алгебраическое совйство, которое и надо вы писать. вы же оперируете только строками и таблицами. У вас там половина утверждений рассыпется, рассмотрите вы побольше вариантов.
Ваши "циклические подгруппы" строк - там квадратиченые вычеты вообще не при чем. У вас x0=i, t=N-2i. При каком-то i вы берете N-2i в качестве i' или N-i' для новой строки i' (в зависимости от того N-2i < N/2 или нет).
И ваши переходы есть применение функции 
, если i >N/4 или 
, если i < N/4. Это почти умножение на 2 и взятие по модулю, но гораздо проще. Тут у функции есть обратная, ведь по четности результата однозначно понятно, какой из двух варинатов применялся. Поэтому f - это перестановка. Поэтому, действительно, все строки разобьются на циклы. Тут не нужны никакие программы, это свойство перестановок вообще. И к пирсоновскому разложению это не имеет вообще никакого отношения. Воткнули умный термин, чтобы придать вашим игрищам какую-то серхезность?
И да, эта перестановка никакого отношения квадратичным вычетам не имеет. Это перестановка элементов 1..N/2.
Согласен с автором выше - в статье ничего полезного нет.
Вы разбираетесь в теории чисел, в математике. Можете построить какие-то перестановки,
покажите мне, что вы нашли корни всех квадратичных сравнений для составного модуля N=989, Запишите нетривиальные инволюции и идемпотенты кольца по этому модулю. Кто-то
собирается построить свою таблицу (модель), решающую эти задачи. В моей статье все это есть в явном виде и получено не перебором, на котором вы настаиваете. Вы же не сможете этого сделать, или вам придется повторить мои результаты. Я утверждаю это потому, что на настоящий момент эти задачи не решены ни теорией чисел, ни кем-то еще. Разложение модели - это не перебор вариантов. И вообще я противник перебора. Ну, что принимаете вызов или сдаете позиции?
Для начала, определите пожалуйста формально, что за квадратичные сравнения вы имеете ввиду? Вы просите найти все квадратные корни для всех квадратичных вычетов?
Идемпонетны - это отличные от 0 и 1 решения уравнения 
?
Если так, то какого-то быстрого метода не имея разложение N на множители мне неизвестно. Ведь (это легко доказывается), решения этих уравнений не взимно просты с N, а значит, если бы такой метод существовал, то это был бы заодно и быстрый метод разложения числа на множители.
Если вы имеете ввиду имено эти уравнения, и действительно умеете их решать быстро, то пожалуйста приведите ваше решение для N=989 по шагам. Я очень хочу его понять, но из статьи так и не понял. Можно даже взять N поменьше. Скажем, 77, чтобы все решение было короче.
Это, во-первых, не уравнение, а сравнение 
. Во-вторых, пишется не = , а ≡ Вместо х пишется вычет - элемент b кольца. В кольце их много. Для каждого b требуется найти четверку значений хi, i =1(1)4, удовлетворяющих сравнению.
Задается составное число N=711 = 77, загружается в СММ, раскладывается в подмодели и опа !
программа выдает таблички. Сверху получаем некратные строки СММ 2х15 = 30 строк, т.к. функция Эйлера ф = 60. Это порядок мультипликативной группы кольца вычетов по mod 77.
В модели список элементов кольца складывается вдвое, поэтому строк только 60:2=30. Ниже разделены по значениям делителей кратные строки: цикловое множество меньшего делителя (М)
ЦМС М7 - 5 строк и ЦМС Б11 - 3 строки. В каждой строке свой вычет, но решений сравнения уже не 4, только по два на строку. Итого, найдено 76 корней квадратичных сравнений, исключается 0.
В верхней таблице в 1-й строке (левая часть) х1=1 и хо =77 -1 =76 тривиальные инволюции, в правой половине 1-й строки х1 = 43 и хо = 34 - нетривиальные инволюции вычет b = 1.
Идемпотенты ортогональные и центральные всегда кратны разным делителям модуля. Они в нижних (малых) табличках. В строках, где хi равен вычету этот хi и есть идемпотент. В левой табличке это х1 = 56, а в правой хо = 22. Всё.
Как что делается это целая лекция и не одна, хотя в моих публикациях со всем этим можно
познакомиться. Надо только внимательно читать и желательно с карандашом в руках. Я писал для своих учеников без халтуры, иначе они не научились бы ничему, и ...
В статье тоже есть ответы на многие вопросы, надо просто внимательно читать, не спешить.
По поводу главных результатов публикации читатели пока не дошли, одна ругань без понятия.
Снобизм без оснований. Утверждения от лица всех ("никому не нужны"). Как на такие комменты отвечать? Комментатору никто не поручал говорить от имени общественности, но он присвоил себе это право. Спасибо за внимание.
Задается составное число N=711 = 77, загружается в СММ, раскладывается в подмодели и опа !
Я так понял, вы начали с i=1, потом по описанной вами процедуре получаете следующие строчки таблицы. Я понимаю как вы получаете последовательность 1,2,4,8,16,32,13,26,25,27, в третьем столбце. Кажеться, вы останавливаетесь, когда вернетесь назад в x0=1. Так?
Ок.
Сверху получаем некратные строки СММ 2х15 = 30 строк, т.к. функция Эйлера ф = 60
В модели список элементов кольца складывается вдвое,
Почему тут ровно 30 строк? Вы это как-то высчитываете заранее или в процессе построения видите, что у вас получилось 30 строк? Для N=33 получается 5 строк, т.е. ф/4 а не ф/2, как для 77. Я погонял числа, получается, что количество строк всегда делитель ф. Но вот там по разному: где-то делиться на 4, где-то на 2, а где-то на 48, 26, 64, 6. Совсем разные варианты, а не только "складывается вдвое". Похоже, что количество строк всегда делитель ф/2, но это стоило бы доказать.
Ниже разделены по значениям делителей кратные строки
Вы эти делители как нашли? Используя идемпотенты или инволюции? Это ясно, как их использовать для разложения. Или у вас что-то другое, напрямую вытекающее из вашей модели? Вы взяли все оставшиеся, не пройденные строки? Как оно тогда работает для N=33, ведь там будет несколько циклов, а не только один большой, содержащий x0=1 да два мелких для каждого делителя?
Однако, этот ваш алгоритм для N=77 прошел аж 30 строк. Что сильно больше корня N. Или вы можете записать нетривиальные инволюции и идемпотенты кольца не выписывая всю таблицу? Поскольку таблица по размеру не сильно меньше N, то это фактически и есть перебор. Тривиально можно сократить перебор в 2 раза рассматривая только числа до N/2, ведь x^2=(N-x)^2 (mod N). Вы не сильно перебили эту оптимизацию.
Прямого применения в разложении числа на множители или даже поиска идемпотент с инволюциями ваш метод не имеет, ибо это все еще перебор чисел. Я построил таблицы для разных N, пока не встретиться первая идемпотента или инволюция и там в 25% случаев проходится почти N/4 строк до первой такой строки. И в 90% случаев проходться больше, чем корень из N строк. Т.е. тупой перебор чисел от 1 и проверки на делимость будет быстрее для разложения числа на множители, чем ваш метод.
Более того, для того же N=33 ваш метод не найдет ни одной нетривиальной инволюции в основном цикле:
x0 = 1, 2, 4, 8, 16
r = 1, 4, 16, 31, 25
Вообще, постройте таблицу для N=33 и проверьте, а все ли ваши утверждения про дубли, интервалы и подмодели выполняются.
Как что делается это целая лекция и не одна,
Тут два предложения нужны для описания всей процедуры вообще-то. Строим последовательность 
, 
, пока не получим опять 1. Все числа в ней будут взаимнопросты с N. Вот и вся ваша "модель".
Никаких свойств этой последовательности вы не доказали. Ничего про длины таблиц в вашей статье нет.
Что касается негатива, то позиционировали бы вы себя поприземленнее, было бы и читателей больше и негатива поменьше. А то, вы тут себя нарисовали великим профессором, предрекли решение нерешенных проблем, да еще про учеников пассажи вворачиваете. А на любые вопросы вместо разяснения в основном кидаетесь презрительными репликами. Видя уровень ваших рассуждений так и хочется поставить вас на место.
Если бы вы начали статью не с исторической справки, а
Я тут нашел вот такое вот интересное свойство такой таблицы: если вот так вот выписывать строки, то она пройдет ф/2k чисел и вернется в начало. Доказательства пока нет (или вот мои идеи доказательства)
То к вам бы не было претензий. Наоборот народ бы накидал вам идей. А у вас тут аж Модель числа (модель - это что-то описывающее объект. Вы фактически претендуете на решение всей теории чисел этим термином). Хорошо хоть, вам хватило стыда не называть этот интересный, но весьма простой объект "Модель Ваулина".
Давайте попробуем по шагам. Вы остаетесь с прежним мнением своего 1го коммента?
Согласен с автором выше - в статье ничего полезного нет, она барахло
Почти того же мнения. Что-то в статье, действительно, есть. Хоть и описано не очень понятно. Но в целом пользы все так же нет.
В соседней ветке вы мне объяснили, что и как вы делаете. Я даже вижу в этом логику, но вы сильно преувеличиваете значимость. У вас метод состоит в том, чтобы выписать почти все строчки таблицы из (N-1)/2 строк и там посмотреть на квадратичные вычеты, таким побразом найдя инволюцию фактически перебором.
Для 77 вам там повезло и инволюция даже встретилась в таблице. Правда, весьма далеко. Но вот для N=33 уже все будет не так. Вы выпишите лишь 5 строк среди которых инволюции нет. Что делать дальше? Брать какую-то другую пока не выписанную строчку и начинать выписвать с нее? Чем это лучше простого перебора x0 подряд с 0 до (N-1)/2, а не в порядке, порождаемом вашей формулой?
>Но вот для N=33 уже все будет не так. Вы выпишите лишь 5 строк среди которых инволюции нет. Что делать дальше?
Это не мне повезло, а вам, что я начал помогать преодолевать дремучесть.
Это у вас все не так, а я знаю, что делать дальше. Вы до сих пор в плену своих ошибочных представлений о модели числа. Вы поддерживаете человека склонного к оскорблениям (вместо того, чтобы поставить не меня - автора, а его на место. Вы его поддерживаете, становясь таким же как он ?)
Мне идет 87 год и я насмотрелся на таких людей за свою жизнь. !0 лет назад статью на Хабре о ЗРД оценили (-8). но ее тут же скопировали другие сайты (люди имели собственные мнения и чужие оценки их не волновали, не как вы прилипли к чужой). А статья до сих пор в топе статей по этой проблеме. Дело в том, до этой статьи ни в алгебре , ни в теории чисел не знали и не умели находить не только делители, но даже области их размещения, да хватит об этом...
Вставил 33, программа выводит то, что надо, но для вас это "барахло".
Это поколение такое оскорбляют походя и совести не имеют, но других норовят пристыдить?
Ну так вам не составит же труда заткнуть неуча, и привести вывод программы?
>Ну так вам не осставит же труда заткнуть неуча, и привести вывод программы?
Труда не составит, но необходимости не вижу
Кстати, вы не туда отвечаете. Смотрите внимательнее.
Вы же учитель? И вы же тут утверждали, что у вас есть непереборный метод поиска инволюций без разложения числа на множители. Это звучит как настоящая революция! Интересно же, я хочу в нем разобраться. Но вот мне непонятно, что вы делаете для 33, ведь там, если начать цикл с 1, он обойдет всего 5 элементов. Совсем не так, как в примере с N=77. Никаких двух колонок в таблице там быть не может. И инволюции в этом цикле просто нет. Что вы делаете в этом случае? Приведите, пожалуйста, таблицу.
Использование возможностей ЗРД обеспечивает определение искомых факторов при факторизации составного модуля.
Отлично. Определите, пожалуйста, факторы числа 2014096878945207511726700485783442547915321782072704356103039129009966793396141985086509455102260403208695558793091390340438867513766123418942845301603261911930567685648626153212566300102683464717478365971313989431406854640516317519403149294308737302321684840956395183222117468443578509847947119995373645360710979599471328761075043464682551112058642299370598078702810603300890715874500584758146849481 (RSA-400). После этого будет смысл пытаться разбираться в Ваших обозначениях.
Если этого пока не можете - сформулируйте в общепринятых терминах хоть какой-то результат, который вся эта Ваша "система" может доказать. Не обязательно даже какой-то открытый вопрос, но хотя бы выходящий за рамки школьной олимпиады.
В границах таких подходов остается только надеяться на рост быстродействия вычислителей (на квантовые компьютеры), что представляется слабо обоснованным
Правильно, потому что ключевое ожидаемое отличие это не "быстродействие", а другая модель вычислений, которую нельзя эффективно чвести к классической.
>сформулируйте в общепринятых терминах хоть какой-то результат,
Вне пределов примитивной области квадратичных вычетов - полных квадратов (ТКВК), ее граница Гтквк = √КВК, организуем для х = Гтквк + i цикл вычисления квадратичного вычета
rл(х) = x²(mod N) по возрастающему i =1(1)..., до тех пор, пока rл(х) не станет полным квадратом, т.е. rл(х) = k² в некоторой точке хоц. Эта точка хоц - центр решающего интервала (РИ), границы которого левая и правая Гл,п = хоц ± k будут кратными разным делителям N,
Далее сами делители находятся без труда.
Полагаем, что x²(mod N) из ТКВК дублируются в списке модели. Другими словами, перебор по переменной х осуществляется лишь до ближайшего полного квадрата после границы √КВК
Прошу прощения, допустил оплошность вместо Гтквк = √КВК, конечно д.б. Гтквк = √N,
>примитивной области квадратичных вычетов
Это не является общепринятой терминологией. "Квадратичные вычеты" - да, "примитивная область квадратичных вычетов" - нет. Можете указать источник термина?
А вы, можете указать источник, в котором такая область непрерывно следующих малых квадратов как-то названа? Думаю, что нет. У других авторов даже нужды в этом не возникало. Вообще любое исследование это не поиск чужих терминов для возникающих в голове понятий, а нечто другое. Все понятия были названы когда-то впервые, а кто их ввел и назвал мало кого интересует. Не все оказались удачными.
Я построил модель составного нечетного натурального числа (СННЧ), которая мне позволяет проводить исследования чисел не только ради их факторизации, а значительно более широкий круг задач. В частности типы чисел 1961 и 1963 стоят рядом, но имеют разный тип, на что отреагировала моя модель.
Вообще я задаю Интернету вопросы, например, о моделях числа. И что, в ответах получаю ссылки на свои статьи. Впечатление, что модели чисел теорию не волнуют и не интересуют. Может Вы предложите такую модель? С интересом познакомлюсь и сравню со своей по разным показателям.
Модель числа - оксюморон какой-то. Число - есть число. Не надо строить его модель. Потому вы и не находите ничего, что взяли неправильный термин.
Вы строите какую-то таблицу для числа, она не является моделью числа. Это какой-то объект, свойства которого как-то зависят от количества строк в нем. Вот как, например, размер групп определяет некоторые их свойства и как через группы Галуа доказывается, что не бывает решения уравнений 6-ой и более степени в радикалах. Там есть объект - группа Галуа. И исследуется ее свойство. И это никакая не модель числа, хотя она строится для каждого числа.
Вы строите какую-то последовательность квадратичных вычетов, а точнее рассматриваете riffle-shuffle перестановку чисел от 1 до (N-1)/2, смотрите на ее циклы.
Самое ближайшее к "модели" чисел - это какая-нибудь аксиоматика Пеано. Но это совсем не то, что вам надо.
>Вы строите какую-то последовательность квадратичных вычетов, .
Вы опять заблуждаетесь. Я не строю ничего из того, что вы называете.
Я построил модель (универсальную) для исследования числа. Это модель строит для заданных мной чисел таблицы, а я просто анализирую их и порой удивляюсь.
Как правила, заложенные в модель, без конкретного указания цели раскрывают сущность внутренней структуры НРЧ и его элементов - чисел. Выдаются решения задач, которые я не заказывал, но знаю, что они сложно решаются и модель подарила мне их решения, которые ни вам, ни кому-то другому пока не ведомы.
Разложение модели обеспечивает нахождение корней квадратичных сравнений. они просто выстраиваются в таблицах. Думаю, что у вас нет метода (кроме перебора) находить такие корни, и не только у вас. А указать инволюцию или идемпотенты кольца, если делители N не заданы вы тоже не сможете. Мне это известно. Математические форумы с их профессионалами это демонстрируют явно. Там что ошибка на ошибке, что-то неправомерно приписывается мною.
Вы не поняли существа работы, сужу по вашим замечаниям. Есть люди, которым она понятна и они обращаются ко мне за разъяснениями того, что осталось неясным для них.
Мне не совсем понятно, что вы хотите от меня, от моей модели, от ЗРД, открытого мной еще в 2014 году. Я опираюсь на него и конечно буду продолжать эту работу. Огромное Вам спасибо, что уделили внимание моей работе и как-то ее комментировали.
Я построил модель (универсальную) для исследования числа.
Модель чего-то - это математическое описание чего-то.
У вас же нет описания числа. По вашей "модели" числа нельзя складывать, умножать, извлекать корни. Вы лишь построили какой-то объект, параметризованный целым нечетным положительным состовным числом без квадратов в делителях. Это не модель.
Выдаются решения задач, которые я не заказывал, но знаю, что они сложно решаются и модель подарила мне их решения, которые ни вам, ни кому-то другому пока не ведомы.
Ну сформулируйте четко хоть одну задачу и хоть один результат тогда. По вашей статье ничего этого не видно.
Разложение модели обеспечивает нахождение корней квадратичных сравнений. они просто выстраиваются в таблицах. Думаю, что у вас нет метода (кроме перебора) находить такие корни
Так ваше разложение - это и есть перебор. Я тоже могу построить таблицу, где в первой колонке будет i, а во второй - N mod i. Можно заметить, что в этой таблице во второй колонке встречаются 0 только для делителей N. Вот такая вот шикарная модель, очень полезная и описывающая Закон Деления Чисел! У вас такой же подход получается.
инволюцию или идемпотенты кольца
Что за инволюция кольца? Это вы тоже сами что-то придумали и извратили общепринятый термин? Что у вас там за преобразование вообще берется? И заодно, о каком кольце вы говорите? Кольцо - вычеты по модулю N? Идемпотента, это элемент, который при умножении на себя не меняется. Мы все еще про вычеты по модулю N говорим? Вы имеете в виду те числа, которые равны своему квадрату по модулю N? Как вы с помощью вашей таблицы находите их (не строя всю таблицу! Ведь это тот же перебор получается)?
Какой-то результат сформулировать можете, или ваши "модели" только про себя говорят, и с общеизвестными вопросами никак не связаны?
Исследование - это поиск ответов на уже имеющиеся вопросы. Иногда для этого да, нужно вводить новые термины. Но хорошо бы продемонстрировать, что это введение полезно для чего-то кроме запутывания читателя. В связи с этим и есть вопрос - какой у Вас получается результат?
Понятия "модели числа" в ТЧ нет, и оно так же никого не интересует, как и понятие "сепулек".
Хм... Т.е. вы находите делитель числа N за sqrt(N) проверок? Ну так можно же просто проверять числа от 2 до sqrt(N), потому что из двух делителей хотябы один-то да будет меньше корня. Стоило ради этого рисовать таблицы и вводить параллельную терминологию?
Модель СММ содержит вне примитивной области sqrt(N) полных квадратов. Любой из них служит центром решающего интервала (РИ) с границами кратными делителям N. Можно отыскивать ближайший к границе Гтквк. Для числа N = 323 такой квадрат получаем на первом же шаге. Это k=1 в точке хоц =18. Тогда границы РИ
Гл,п = хоц ± k. Совсем не требуется sqrt(N) проверок. Ваше утверждение следует из допущения, что в модели только два числа являются делителями. Но это не так. Список СММ содержит множество кратных делителей, из которых делители получаем простым путем без переборов.
1) Если на интервале в O(N) значений есть O(√N) требуемых элементов, то среднее расстояние между ними - O(√N).
2) Вы фактически полагаетесь на то, что из k² = aN + b² следует разложение aN = (k-b)(k+b). Этот способ называется "методом факторизации Ферма", и его оценка эффективности хорошо известна (спойлер: O(N) в плохих случаях для "базового" метода, надо доказывать если ваша модификация лучше). В любом случае, при 2q > p > q, перебирать придётся p-q строк, для больших множителей это непрактично много.
>Т.е. вы находите делитель числа N за sqrt(N) проверок? ... Ну так можно же просто проверять числа от 2 до sqrt(N),
Т.е. мой ответ изменил ваше мнение "но цена за это -1" .Сколько еще минусов мне предстоит получить за Ваше невнимательное прочтение. НРЧ - детерминированная вещь (см. Статью В,И. Арнольда Случайны ли КВВ?).
Никаких средних расстояний там нет. По пункту 2 могу ответить, если минусы будут убраны.
Решили разобраться в "барахле", странно, что это с Вами произошло?
Разложение модели числа на подмодели. Часть I