Comments 43
А почему в тегах "поисковая оптимизация"?
Программа модели строит строки,
Ответьте мне пожалуйста, на вопрос, ваша программа строит все строки или используя какие-то свойства Модели, она строит только малую их долю?
Строки строятся все. Я не хочу чего-либо упустить. Что окажется важным я как и другие не знаю. Модель используется только для получения формул (зависимостей) одних от других переменных. Никакой перебор строк не требуется. Откройте модель для N =407 и надо понять, что средний вычет rccc =1+rпо =t1хtо 17x18. После чего находим t = t1+tо =35,а по t находим номер строки нетривиальных инволюций хо = 186 - центр решающего интервала. Далее уже сами делители N по закону распределения делителей.
С практической точки зрения ваша идея бесполезна, если вы строите всю модель. Потому что для поиска инволюций тех же, компьютеру или математику с блокнотом придется выполнить не меньше действий для простроения всей таблицы, чем для просто проверки всех чисел.
Откройте модель для N =407 и надо понять, что средний вычет rccc =1+rпо =t1хtо 17x18.
Как это понять без построения всей таблицы сначала?
Как это понять без построения всей таблицы сначала?
Да никак в общем-то. Большая часть выводится из китайской теоремы об остатках и факторизации Ферма, но оно не решает проблему факторизации примерно никак, то бишь для реально больших чисел работа с таблицой не имеет практического смысла ровно по тем же причинам что и работа с факторизацией Ферма в чистом виде.
Вот и я того же мнения, но хочется автору это объяснить, почему-то.
И тут нет никакой китайской теоремы. Все формулы выведенны методом пристального взгляда на раскрашенные таблицы. Какие-то частные случаи даже работают, потому что выливаются в угадывание формы функции, которая раскладывается на полный квадрат, если ее умножить на N и прибавить 1.
В тех примерах. которые автор указывает, фактически применяется формула для инволюции (N-sqrt(3N+4))/2. Даже школьник сможет возведением в квадрат убедиться, что получится остаток 1 по модулю N. Если формула дает целое число, конечно. И удивительное совпадение - в примерах, которые автор приводит 3N+4 оказывается полным квадратом.
Для другого отдельного случая с числами близнецами всегда действует формула N-sqrt(N+1) для инволюций. Если подставить все эти лево-право-центральные вычеты с примыканиями друг в друга и собрать более чем одну арифметическую операцию вместе, то так и получается.
И тут нет никакой китайской теоремы.
Китайская теорема всплывает, когда пытаешься понять, где искать те самые границы "решающих интервалов". Если формально верифицировать, то связь с ней так или иначе возникает, также как и формула из факторизации Ферма. Но я не углублялся сильнее.
Я имел ввиду, что в этих статьях китайской теоремы об остатках нет. Естественно, ее где-то тут точно можно применить, если речь о вычетах по модулю составного числа. У автора нет никакой формальной верификации. Вообще вся верификация это "мамой клянусь":
Это явление имеет место в СМ-модели для всех исследуемых чисел (не простых и бес- квадратных)
А, так VAE отрицает, что есть связь хоть c CRT или FF, и что это уникальная авторская теория, кою он самолично (не)сформировал в 2014. И да, про формальную верификацию или хотя бы рукописные доказательства у автора нигде речи не идёт, несмотря на запросы сообщества. Мол, "читайте мою папиру, там всё есть"(нет).
CRT и FF всплыли, когда мучал роботов на предмет пруфов и дум касательно нормального формального определения. Не вот эти квв, чсс, ёклмн, а в полноценных сущестующих мат символах, а ещё лучше в виде теорем для Lean. Собственно, потому и сделал себе инструмент для генерации этих его таблиц, чтобы не запутаться во всей этой абвгдэйке.
>Да никак в общем-то.
Это не так. Из модели следует, что с одной стороны rc = (t^2 -1)/4, а с другой rc = 1 + rпо, где rпо = N - rло. Далее, если rc =rccc, то раскладывается в смежные сомножители, т.е. rcсс = t1*tо и модель не строится.
Для N= 33 как не строится модель? rccc на смежные сомножители не раскладывается. Но и числами близнецами не является. Как там инволюция находится?
Ее, кстати, можно найти по формуле N-sqrt(3N+1). Уверен, вы тут сейчас вывалите очередной частный случай и если все подставить, получится именно такая формула.
Только для N=39 и она не работает. И там тоже не упомянутые ранее числа близнецы, или rccc со смежными сомножителями. Там работает формула N-sqrt(5N+1). Вот у вас уже четвертый частный случай. Их таких бесконечно много.
Только пока не переберёшь хотя бы min(p,q) значений получить нужные t/rc/rccc и прочие переменные непосредственно из N не выйдет. Если у вас p или q каких-нибудь 128 бит, то работать с этим становится нереально в таком формате. Да и когда досчитал до сомножителя, то зачем нужны остальные приседания?
Поиск можно выполнить разными путями. Можно в Лоб, а можно короче, как в примерах.
Во всех таблицах и моделях действует один закон. Нашли формулу для одного - можно применить для других. Всегда (для любых N) rc = 1 + rпо.
Еще раз повторю. Модель нужна для поиска не инволюции, а для вывода формул ее отыскания. Когда формулы получены модель не используется, а инволюция находится.
Пример. N = 407 = 203 +204. Левый вычет равен rл= 102,а правый вычет rп=407-102 =305.
Средний вычет rс = rccc= 305 +1 = 306 = 17x18, t = t1+ tо = 17 +18 = 35. Номер строки нетривиальных инволюций находим по t. Номер хо =(N - t)/2 = (407 - 35)/2= 186 для инволюции нашли. К модели не обращались. За 5-6 арифметических действий получили.
Что-то еще не понято?
Спасибо. А можете эти действия еще и для 55 расписать, чтобы я понял формулу?
Для 407 понял вот что: cначала берем (n-1)/2 и получаем 203. Потом rл = 203^2 mod 407 = 102. Потом rп = N - rл = 305. Прибавляем 1, получаем rc 306. Формула получается, если ее чуть-чуть причесать:
Как из 306 получается 17x18? Почему не 34x9?
Из текста я так понял, что вы считаете, что это число раскладывается на делители c разностью 1, потом сумма этих делителей нужна для высчета инволюций.
Но для 55 там получаеся rc=28. Оно не раскладывается на t1*t0. Какое разложение 28 надо тут взять? Их несколько.
Для N = 55 =28+27. Имеем rc =rccc = 1+rпо = 1+41=42, t = t1+t0 =6+7=13, ищем номер строки инволюций хо =(N - t)/2 =(55 - 13)/2 =21. Эта строка окаймляется кратными строками, т.е. обеспечивается поиск делителей.
По вашему rc = 28, но (это х1о=28) это не так rc =1 + rпо единица суммируется с правым вычетом rпо=41, он в нижней строке модели справа. Хотите что-то понять надо читать мои публикации, где я последовательно показываю как делается наука о НРЧ. Хабр вас расслабляет пустяковыми статьями. Мои статьи не развлекаловка, а требуют мозговых усилий и внимательного прочтения текстов. Я же пишу для своих учеников и не допускаю халтуры. У них вопросы также возникают, но совершенно другого уровня, так как они изучают без пропусков и могут вернуться к моим статьям на Хабре, когда им удобно. Я готовлю к издательству книгу (тексты составляют более 200 стр.) На Хабре только необходимые для понимания всей картины фрагменты. В мире известны несколько моделей факторизации чисел, не оформленных.
Я с ними знаком и считаю их тупиковыми (не только я). Пришлось создать свою модель и возможно "теорию"
Для 55 ошибся с вычислением вычета, извиняюсь.
Действительно получается, что надо раскладывать 42. Но для N=143 = 13*11 там уже получается rccc=108, которое так не раскладывается (тут я уже на компьютере проверил). Как ваша модель в этом случае находит инволюцию?
Вы ошиблись не для 55, а раньше. Совершенно не поняли мои статьи, но взялись их оценивать и судить, критиковать со своим снобизмом - "барахло". Вас таких на Хабре большинство и ваш почин подхватывают другие. "Не читал, но ставлю минус". Ваши советы можете перечитать. они не к месту. Просто надо мои тексты читать внимательно, там ответы содержатся м.б. не столь обширные как здесь.
N = 143 = 11x13 - 'это "близнецы". Для них инволюция всегда примыкает к ТКВК, т.е. в строке с номером хо =12, т.к. порог ТКВК в хо =11. rk = 121. Так будет для всех "близнецов"
Как вы понимаете, что это близнецы не строя всю модель-таблицу и не факторизуя изначально N? Как вы находите порог ТКВК?
Вы можете формализовать алгоритм поиска инволюции без построения таблицы?
Это должно быть что-то вроде:
1) считаем rccc= ((N^2-1)/4)%N+1
2) считаем x = floor(sqrt(rccc))
3) Если x(x+1) = rccc , то (N-1)/2 - x - инволюция.
4) Иначе - что?
Эта формула в пункте 3 работает для N=55 и N=407. Это можно даже весьма просто в пару действий доказать алгебраически. Если x(x+1) равно rccc, то просто подсчитайте квадрат предполагаемой инволюции, подставьте rccc вместо x(x+1), чуть-чуть причешите выражение и получите что-то делящееся на N, плюс 1. Но это только если совпало rccc=x(x+1). И так происходит лишь для 171 чисел из всех 168330 с двумя простыми нечетными разными делителями до миллиона. Компьютер проверил. Вы в своих примерах постоянно демонстрируете весьма редкие примеры из 0.1% уникально хороших чисел для вашем модели. Плохие примеры до сотни: 33, 39, 51, 57, 65, 69, 85, 87, 91, 93...
Из оставшихся 168330 чисел лишь 8169 - случай близницов.
Что происходит в оставшихся случаях?
Если вы такой алгоритм формализуете, его уже можно и в журнал какой-нибудь посылать, если его еще и доказать. Но я уверен, что вы ошибаетесь и такой алгоритм составить не сможете. Вы нашли какие-то частные закономерности, и даже их не доказали. Вы проверяли вашу модель для всех чисел хотя бы до миллиарда?
Вот, уже вылез частный случай с близнецами выше и еще 160000 чисел под вопросом. И я уверен, что есть другие случаи, которые вы еще не нашли. Потому что поиск инволюции позволяет факторизовать число. А на невозможности быстрой факторизации чисел с двумя простыми делителями основана половина современной криптографии. Это задача на сотни миллионов долларов, ее пытаются решить величайшие умы современности много десятилетий. Если вы напишите нормальную статью в виде теорем, лемм и без тонны введенных вами терминов, в которых черт ногу сломит, то вы запросто эти сотни миллионов долларов сможете получить.
Но в итоге ваш алгоритм выродится в "если не повезло, то строим всю модель и ищем в ней вот такие-то строки", а это нисколько не быстрее наивного алгоритма факторизации. Даже хуже, ибо ваша модель содержит N/2 строк, а для самого простого алгоритма факторизации надо лишь проверить все делители до sqrt(N).
Прекрасно! Перечень вопросов растет. А программу написать слабо?
Или попросить поделиться у того, кто уже написал (см. комментарии).
Обратите внимание, что мне раньше спрашивать было не у кого, как и сейчас тоже. Поэтому списка литературы нет. То чем я располагаю писали разные люди, некоторых уже даже нет в живых. Трогать свои программы я просто боюсь, чтобы не потерять. Храню, что осталось.
На сегодня все, поздно уже. С утра на работу ехать.
Программу чего? Вывода таблицы? Она тривиальна, ее даже школьник, только изучающий программирование напишет. Вычисления инволюций без применения модели, используя выведенные вами через нее закономерности? С радостью, если вы мне эти закономерности более менее кратко и формально изложите. Продираться через 100500 терминов и слабо формализованные зависимости весьма сложно.
Обратите внимание, я все 9 столбиков и, наверное, несколько абзацев в ваших статьях свел к трем сторкам в предыдущем комментарии, вообще не вводя никаких терминов. Там есть 2 обозначения rccc и x, но им не нужно давать громких названий:
1) считаем rccc= ((N^2-1)/4)%N+1
2) считаем x = floor(sqrt(rccc))
3) Если x(x+1) = rccc , то (N-1)/2 - x - инволюция.
Если вы примерно в таком же виде ужмете ваши статьи то я вам и программу напишу и найду числа, на которых оно не работает. Хотя бы ту часть, где вы инволюции ищите. Вот допустим N=143. Вы сказали, что это близнецы, но это ясно, когда N разложили на множители. А для этого мы инволюцию и ищем. Вот есть N и получилось, что x(x+1) != rccc. Как быть дальше? Вы писали, что-то про ТКВК и что-то там к чему-то примыкает. Можно формулу из этого формализовать как-то? А как оно работает для N = 33, 39?
>если вы мне эти закономерности более менее кратко и формально изложите.
Этого я не возьмусь сделать, всего очень много, трудоемко.
Наше общение пока касалось лишь очень частных случаев, т.к. они более прозрачны для понимания, но и они трудно вами воспринимаются. Каждый крючок я вам поясняю. На самом деле все значительно сложнее (иначе бы проблему факторизации давно уже закрыли). Ученики мои все усваивали постепенно и каждое новое явление схватывают сразу.
>про ТКВК и что-то там к чему-то примыкает.
инволюция (красная) примыкает снизу к желтой ТКВК
Как вы желтую область находите не строя таблицу?
Наше общение пока касалось лишь очень частных случаев,
У вас вся Модель из частных случаев и состоит. Где-то инволюция оказывается в известном месте, если rccc+1 раскладывается на x(x+1). В противном случае, если числа близнецы, то формула другая - надо желтую область брать, в другом случае - вообще по другому.
На самом деле все значительно сложнее
Да, факторизация сложнее. А ваша модель состоит лишь из отдельных арифметических действий и примитивных правил раскраски таблицы. Естественно, она ее никак не решает. Нет тут никакой сложности. Нагромождение кучи всяких терминов для тривиальных вещей, вроде номера строки и формулы 2*k-1 - это лишь напускная сложность. У вас ни в одной статье нет никакой математики, ни одного доказательства.
Если бы вы потрудились подставить ваши формулы друг в друга, вы бы, например, вывели формулу (N-sqrt(3N+4))/2 для инволюции, которую вы фактически применяете для N=55 и N=407. Только вычисляете вы ее за кучу мелких шагов, чтобы выглядело солиднее, навреное? И ее даже школьник запрасто докажет, если ее, таки, записать. И сразу видно, когда она работает (если 3N+4 - полный квадрат).
Для чисел близнецов формула будет N-sqrt(N+1), потому что N+1 - всегда полный квадрат. И не надо никаких желтых областей в таблице, левых, правых, центральных вычетов и примыканий.
И эти формулы работают для любых N - а не только полупростых. Так, по модулю 24, инволюцией будет 24-sqrt(25)=19.
Вы молодцы, конечно, что по разглядыванию закономерностей в таблице смогли эту формулу угадать. Дарю вам: их таких бесконечно много можно нагенерировать: (f(N)*N-sqrt(g(N)*N+k^2))/k. Берете любые целочисленные функции f(N), g(N) и k, и пока эта формула даст целое число - оно будет инволюцией.
Только это бесполезно все, ибо каждая такая формула применима лишь к отпределенному множеству чисел. И заранее угадать какая из них подходит нельзя.
Отдельно хочу высказать вам про ваших студентов. Не стоит их восхищениями вашей Теорией обманываться. Они люди подневольные и им вам что-то еще сдавать, наверное. Поэтому не смеют они вам критику по вашей Модели высказывать. Но вы тут их постоянно упоминаете, как будто это ваши последователи, словно апостолы при Христе. Наверняка, они в куларах про вас гадости говорят и про вашу теорию.
И вообще, скромнее надо быть - это каким самомнением надо обладать, чтобы в своих статьях вставлять историческую спавку, ставя себя на один уровень с Ньютоном, Эйлером и Лаплассом. У них, в отличии от вас были статьи в рецензируемых журналах. У вас я нашел лишь статьи в собрание трудов сотрудников какого-то института. Это такое себе достижение: этим сборникам вообще без разницы что печатать обычно, им надо печататься для отчетности. Поэтому они у сотрудника возьмут что угодно. Есть ли там вообще рецензенты, чтобы по существу математики покритиковать материал?
И книгой вы тут хвастались, аж на 200 страниц. Да хоть 2000. Особенно если писать как вы тут статьи пишите - очень распространенно и одну формулу описывать через 10 терминов. А еще можно страниц на 100 всяких невыдуманных историй написать во введении, как Ньютона не принимали дураки, а он мир изменил. И напечатает вам издательство за ваши деньги хоть новую теорию модели чисел, хоть любовные романы про кротов. Или вы в какой-нибудь университетской типографии по блату публиковаться собираетесь? Это никак не говорит о качестве книги.
Как вы желтую область находите не строя таблицу?
Это просто отметка полных квадратов. Любое начало таблицы начнется с такой жёлтой области. Если знаете как Rust штуки ставить, то можете попробовать моё шаманство, упомянутое в статье. Основные столбцы там отмечены + легенда в заголовке что есть что + есть возможность отрезать куски таблицы. Про отметку инволюций там только нет.
Ага, т.е. последняя желтая строка будет иметь номер floor(sqrt(N)), а следующая, в которой будет инволюция - floor(sqrt(N))+1. Т.е. инволюция будет floor(sqrt(N))+1. Поскольку N+1 - полный квадрат для чисел произведения простых близнецов, то floor(sqrt(N)) = sqrt(N+1)-1. А формула для инволюции - sqrt(N+1). Действительно, очевидно, что это инволюция. При возведении в квадрат получится N+1, что даст остаток 1.
И тут не нужен никакой Закон Распределения Делителей (с Большой Буквы - надо же уважать сложный материал /s). И не нужны никакие решающие интервалы, это все лишняя сущность. Ведь инволюция будет после этой желтой области только для чисел с двумя простыми делителями с разностью 2, у которых N+1 - полный квадрат. Это очень частный и простой случай.
последняя желтая строка будет иметь номер floor(sqrt(N))
Зависит от того какую именно жёлтую строку вы считаете последней. floor(sqrt(N)) судя по всему попадает в последний максимальный квадрат в начальном регионе.
для 85, например
sqrt(85) ~ 9
полный квадрат для чисел произведения простых близнецов
мне кажется их особо рассматривать смысла нет, также как и квадраты простых чисел, ибо их факторизация тривиальна. Либо я не очень понимаю какие числа вы рассматриваете.
ибо я не очень понимаю какие числа вы рассматриваете.
Я рассматриваю все. Автор сказал, что пользуясь Моделью (с Большой Буквы) можно найти инволюции по найденным им закономерностям, не строя всю таблицу.
Автор начал с того, что если rccc+1 раскладывается на x(x+1) и тогда по каким-то формулам находится инволюция. И все примеры в статьях у него такие. На самом деле, если расписать, это выполняется когда 3N+4 полный квадрат и формула для инволюции будет (N-sqrt(3n+4))/2.
Но это не выполняется, например, для 35, что я и привел автору. Тут автор сказал, что надо вот после желтых строк взять следующее число. Потому что это произведение чисел близнецов.
Но это, как вы сказали, и я с вами полностью согласен - тривиальный случай.
Что делается в противном случае, автор пока не ответил.
Вот в случае N=85, можно ли найти инволюцию не строя всю модель? Вы поняли это?
Даже не очень понимаю по какому кольцу оно инволюция, не говоря уже о том чтобы искать её.
Даже не очень понимаю по какому кольцу оно инволюция, не говоря уже о том чтобы искать её.
По модулю N конечно же.
Робот говорит, что существует ровно один способ найти нетривиальные инволюции в
Где
,
это модулярные инверсии, поиск которых равносилен факторизации числа и требует как минимум
шагов.
Пруфов о единственности я конечно делать не буду, ибо подозреваю что там столько теории Галуа придётся навернуть, что моих знаний наверняка не хватит.
Фактически повторил, то что ниже там Naf2000 писал, получается.
Робот говорит, что существует ровно один способ найти нетривиальные инволюции в
Это если вы хотите универсальный быстрый метод, то да. Это кажется самый быстрый метод. Еще, всегда можно тупо перебрать все числа до N и проверить их все. Тут даже не надо знать факторизацию числа.
а и требует как минимум
Вообще есть всякие методы которые сильно быстрее для факторизации. Что-то через эллиптические кривые точно есть. Может за sqrt(min(p,q)), может круче. Но все-равно экспоненциально долго от N.
И именно поэтому я и уверен, что эта Модель Числа (С большой буквы!) не позволяет искать инверсии в общем случае. Но товарищ VAE утверждает обратное, и на все мои контрпримеры пока лишь вводил новый крайний случай и говорил, что я не разобрался в его сложном материале, который требует осмысления. Аргументы, что он тут аналог вечного двигателя изобрел, отлетают как от стены.
Еще, всегда можно тупо перебрать все числа до N
Собственно потому оно и min(p,q) т.к. вам достаточно досчитать до минимального делителя N, второй делительно получается тривиально. Более продвинутые алгоритмы брутфорса не рассматривал в контексте темы статьи ибо они там сильно непростые и никак не связаны (вроде).
Все-таки математика это не про таблички конкретных примеров. Безусловно хорошо разобранный пример это прекрасно. Но хотелось бы видеть какие-то общие выводы в виде утверждений, лемм и теорем, естественно с доказательствами.
наконец-то проявился (считаю Вас крестником). Не всем и не сразу дано увидеть за табличками алгебраические структуры. Но у вас время еще есть. Это я уже подошел к выходу и не все успею (из задуманного) завершить. Вся надежда на вас. Хотелось бы увидеть реакцию на мой прошлый комментарий, об отсутствии данных о делителях N. Известно только, что N составное. Как определить инволюции, идемпотенты? Есть соображения?
Ну вот в вашем случае N=p*q, где p, q - простые.
Поэтому инволюции это элементы вида
При этом нетривиальные случаи имеют разные знаки. Если x - инволюция, то (x-1) делится на p, а (x+1) на q или наоборот. Следовательно стоит поискать (алгоритм Евклида) общие делители у пар (N, x-1) и (N,x+1) такие что их произведение даст N. В случае N произведения двух простых делителей эти делители находятся однозначно.
Пример: N=407, x=186.
НОД(407,185) = 37, НОД(407,187) = 11 37*11 = 407.
Если мы хотим для каких вообще колец 186 является нетривиальной инволюцией, то следует факторизовать числа 185 = 5*37, 187 = 11*17.
Получаем, что 186 будет нетривиальной инволюцией для колец по модулям 5*11=55, 5*17=85, 37*11=407, 37*17=629. Вот это и есть те самые пары.
В общем "модель числа" это кольцо вычетов.
Дано только N = 407 = p*q, p и q - неизвестны, инволюция тоже неизвестна. Что надо сделать и с чем, чтобы найти инволюцию или идемпотенты?
Не совсем понял... Для N = 55 как может быть инволюция In =186 и для N = 85.
Для N = 629 и других я и нашел с использованием модели, которая кольцом мной и объявлена была сразу. То, что вы написали все в статье и приводится кроме того, что для N = 55, In (55) =34 и 21, а для N = 85, In = 69 и 16.
Для кольца вычетов по модулю 55 число 186 лежит в одном классе с числом 186-3*55=21 - так что 21 и 186 это представители одного и того же класса вычетов.
Повторю вопрос
Дано только N = 407 = p*q, p и q - неизвестны, инволюция тоже неизвестна. Что надо сделать и с чем, чтобы найти инволюцию или идемпотенты?
И я повторю: А что делать с N=33?
>И я повторю: А что делать с N=33?
Если коротко, то разделить на 3.
Готовлю ответ в новой статье, трошки потерпеть надо
Эм... разложение N неизвестно же. Как вы 3 найдете? Или все числа, делящееся на 3 - особый случай?
Ну ладно. Заодно сразу же подумайте, что делать для N=65 и N=91?
Выпишите, пожалуйста, все случаи четко. Напоминаю, у вас уже были 2 случая: rccc=1 раскладывается на смежные сомножители (можете убедиться сами, это когда 3N+4 - полный квадрат); N - произведение близнецов (эквивалентно N+1 - полный квадрат). Вот теперь у вас какой-то новый случай, когда надо разделить на 3. Но 65 на 3 уже не делится и случаи выше не подходят тоже. Это будет уже четвертый случай? Сколько их всего?
Арис Ефимович, вы перестали отвечать. Не рабоатет ваша модель для 33, да?
Как работать с моделью числа I