Комментарии 23
Статья непонятна даже для продвинутого читателя без подготовки в авторской нотации, перегруженность аббривеатурами — даже при наличии их списка. Много интуитивных, но недоказанных утверждений, похоже на попытку на частных примерах построить алгоритм факторизации "любого" числа. Скриншоты низкого качества в середине статьи не помогают, содержат неясные цветовые пометки без легенды. Очень похоже на работу энтузиаста, который не слышит окружающих и поэтому не может донести свою идею (очень редко на хабре вижу статьи с негативным рейтингом). Видно что проблема автором разрабатывается по меньшей мере с 2015 года. Есть ли псевдокод? Есть ли демонстрация выигрыша по сложности предлагаемого метода по сравнению, например, с методом квадратичного решета?
В работе показано направление моделирования числа, отличное от известных, и его возможности решать задачу факторизации составного числа, рассматриваемого как модуль приведения кольца.
решать задачу факторизации с предположением о том что мы знаем это разложение как-то странно.
Пусть A1 будет предположением, что мы не знаем факторов.
Следствием С1 будет то, что мы не можем раскрашивать что-то, кроме квадратов и смежных сомножителей, которые имеют тривиальную проверку.
Алгоритма нахождения любого из центров решающих интервалов за пределами тривиальной области при истинности A1 не описано.
Алгоритма нахождение секции "четверки" при истинности A1 не описано.
Доказательств, что область четверок всегда существует нет.
Как помогают инволюции и индепотенты искать факторы не описано. Форма инволюции никогда не была представлена в явном виде.
Алгоритма нахождения индепотентов при истинности A1 не описано.
Алгоритма нахождения секвенций, которые суммируются в N при истинности A1 не описано.
Попытка найти любое из этих значений при помощи таблицы пока что сводится к брутфорсу значений до меньшего из факторов, либо использование вышеупомянутых способов продвинутой факторизации.
Ну и было бы неплохо взять пример побольше. Как например факторизовать 1000175531675759323?
Для примера решение: р=1000082623; q =1000092901 (за доли секунды).
Предположение о факторах нужно не для поиска факторов, а для построения модели поиска (вывода) формул, по которым эти факторы вычисляются.
1. Модель не используется, если формулы получены.
2. Моделью без раскраски кратных строк можно воспользоваться (факторы мы не знаем) для поиска полных квадратов (левых вычетов, т.е. КВВ). Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
3. Я рассматриваю только формульный алгоритм (перебор отвергается), хотя при наличии СММ используются простые делители не до корня из N , а до ближайшего полного квадрата. Используется ЗРД.
Вопрос был как пользоваться тем что вы описываете, а не какой ответ. Мы можем взять произвольное число до корня из N и получить полный квадрат из тривиальной области, только как это помогает находить факторы? Вы буквально четвёртым шагом дорисовываете остатки совы.
Рисуем круг: Берём x1 * x1 mod N == k * k
Рисуем второй круг: Смотрим в столбец 5
???
Дорисовываем остатки совы: Фактор p = число1, q = число2, в строке число3 - индепотент, инволюция
PROFITКонечно может вы савант и как-то из рукава все эти числа спавните, но нам-то калькуляторам как это обходить?
По какой формуле вы получили эти 2 числа?
(за доли секунды)
Простенькая переборная программа по самому наивному, известному сотни лет методу, тоже работает за доли секунды.
Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
Вы просто описали полный перебор для поиска КВК. Это тривиальная идея. На практике обычно не используемая, потому что она не быстрее самого наивного перебора выше в общем случае.
Тут вся ваша таблица, раскраски и определения не нужны вообще. 99.99% текста из ваших статей можно взять и выкинуть, ибо они для этого не нужны вообще.
Все это одна формула:
нашли такой x - можем разделить. Как искать такой x вы не придумали.
Согласен, что в последних статьях описания не приводятся. Моей задачей являлось довести смысл Закона распределения делителей (ЗРД). Хочу чтобы он вам всем был понятен. Кстати он доказывается по индукции, но если вы предложите другое доказательство буду рад познакомиться с ним.
ЗРД числа - основа и модели и концепции и направления поиска факторов.
>Как помогают инволюции и индепотенты искать факторы не описано. Форма инволюции никогда не была представлена в явном виде
В математике задача вычисления инволюции и идемпотентов кольца не решена. В моей статье "Разложение модели на подмодели. Ч1" показано явно, что нетривиальная инволюция попадает в строку с тривиальной инволюцией. Программа сама ее нашла, что не планировалось и не ожидалось (там см табл.2 и табл.3) Что дало такой результат я не знаю, пока обдумываю.
Номера строк идемпотентов (они смежные, для N = 629, это хо=221 и хо =222) в СММ в сумме всегда дают нечетную нетривиальную инволюцию (IN = 221 +222 = 443). Для N =407, хо = 110 и xо = 111, IN = 110+ 111 = 221 Её окаймляющие строки (х1 и хо) кратны разным делителям
>Алгоритма нахождение секции "четверки" при истинности A1 не описано
Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157). Строка четверки хо =128 в строке окаймления (сверху), её КВВ =30, а разность КВВ =КВК =1 инволюции и КВВ 128 строки равна номеру слоя: окаймления центра КВВ(128) - КВВ (186) = 30 - 1 = 29. Об этом я писал в статье о симметриях.
Для N = 407 нетр. инволюция лежит в строке 186 - 102 = 84 слоя окаймления (снизу) номер центральной строки (хо = 102). Строка четверки хо=102 - 84 =18 в строке окаймления (сверху), её КВВ =324, а разность КВВ =КВК =1 инволюции и КВВ 18 строки равна номеру слоя: КВВ(186) - КВВ (18) = 1 - 324 = -323 = 84. Об этом в статье о симметриях.
В математике задача вычисления инволюции и идемпотентов кольца не решена
Если она не решена, то откуда вам известно, что это именно инволюция/индепотент без скармливания её в некоторую функцию?
Номера строк идемпотентов
откуда они появились?
Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157).
Меня абсолютно не интересует где они лежат, меня интересует как вы получили значение 157 или 29, 186, 102 и тп. Почему 102 подошла, а 177 нет? Половина этих строки находят дальше N/2 и для больших чисел и если у нас число в тысячах бит, то мы не можем ожидать, что мы пробежим эту половину с каким-то фильтром как вы их выбрали для произвольного N?
>Если она не решена, то откуда вам известно, что это именно инволюция/индепотент без скармливания её в некоторую функцию?
Это известно по определению инволюции (я их обозначаю меньшую (In) и большую (IN)) и идемпотентов (не индепотентов, они обозначены (Id) - меньший и (ID) -больший)
> Номера строк идемпотентов откуда они появились?
В списке СММ строки идемпотентов смежные. Для меньшего Id = хо^2 (modN) =xо, для большего ID =хо -1
>Для N =629 нетр. инволюция лежит в строке 29-го слоя окаймления (снизу) центральной строки (хо = 157).
Центральная строка - это центр списка в ней для N =407, t = tп = 203 или могут различаться на 2 для N = 629, t=315 и tп =313. Можно найти иначе хц = rпо=157.
хц = 102 = rло для N =407 потому и подошла. Для N = 629 xц =157= rпо. Для центральной строки окаймляющие строки расположены в слоях 1-ом, 2-ом и т. д. симметрично. Для инволюции имеем номер хо(In) =186 т.к. ее левый вычет (rл = 1) и она лежит в 186 - 157 = 29 слое. Номер слоя всегда равен разности левых вычетов окаймляющих строк слоя. Одна из строк (четверки кратных) имеет хо =157- 29 =128 и её левый вычет rл = 30. Эта строка симметрична инволюции относительно центра. Разность rл -rл = 30 -1 =29 показывает, что это именно так.
> мы не можем ожидать, что мы пробежим эту половину с каким-то фильтром как вы их выбрали для произвольного N?
Пока выбирал визуально, формулы надо искать для инволюции, о чем уже говорилось.
Ответить domix32
Это известно по определению инволюции
по определению инволюции вы можете скормить некоторых x в функцию f(x), положить полученный результат в ту же функцию и получить x обратно. Вы не можете коронвать конкретные числа инволюциями "по определению" не имея функции.
Для меньшего Id = хо^2 (modN) =xо, для большего ID =хо -1
Есть контакт.
это центр списка в ней для N =407, t = tп = 203 или могут различаться на 2 для N = 629, t=315 и tп =313. Можно найти иначе хц = rпо=157.хц = 102 = rло для N =407 потому и подошла.
То бишь
Пока выбирал визуально
и для 1000175531675759323?
Этот пример иллюстрирует возможность факторизации любого составного числа (и 33, и 65, и пр.)
И как же раскладывается 33? Без постройки таблицы. Как вы эти интервалы решающие-то ищите?
Для модуля кольца N = 629 найти делители (разложение на простые сомножители).Решение можно получить в любом решающем интервале. Выбираем РИ, например, с центром в х = 44.
Вот как мы выибираем РИ - это и есть основной вопрос. Если вам выдать КВК, то факторизация понятно как делается. Вы тут перебором же ищите? До корня из N вариантов, похоже:
Здесь мы используем перебор строк, но не тотальный, так как квадратов в модели √N.
Так ведь тривиальный метод факторизации такой и есть: перебираем все числа до √N, смотритм, делится ли на них N. Все. Ваша модель тут вообще не нужна, ничего не ускоряет и не помогает и смысла не несет.
такого перебора можно избежать, используя свойства модели, построив зависимости переменных модели (частные случаи)
Ага, вот уже и не "модель позволяет решать проблему факторизации", а некоторые частные случаи можно по каким-то зависимостям, выведенным на частных случаях таблицы, решить.
Скажите, а вот случай, что если число заканчивается на цифру 5, то можно поделить на 5 - он достоин звания Модели? Он вообще полезен?
Что бы показать ценность вашей модели, вы не подбирайте примеры, на которых они работают, а формализуйте их, выпишите критерии в виде формул и оцените, как часто они встречаются. Например ваш пример с rccc+1 раскладывающимся на множители работает для N, т.ч. √(3N+4) - целое.
Не могли бы Вы сменить тональность комментариев (получается, что я что-то вам должен. Не смените общение прекратим. Научитесь уважать собеседника )
Вы с таблицей 77 можете разобраться? Если нет, то я не знаю как помочь.
В таблице модели на РИ указывают КВВ=КВК, т.е. полные квадраты.(их шесть для N = 77).
Первый КВК = 4 примыкает к ТКВК.. Её получаем без построения таблиц. Вычисляем порог (=8) и продолжаем получать КВВ (в (.) 9) КВВ =КВК =4) пока не встретится КВК. Для 33 ответ уже был (признаки делимости используются в любой атаке)
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.
Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ
Для 33 ответ уже был (признаки делимости используются в любой атаке)
Но ведь 33 - это лишь пример, в котором ваши частные случаи не сработали. Если вы эти частные случаи опишите, я вам могу и 15-значное число найти, которое под них не подходит, где признаки делимости не сработают.
В прошлых статьях вы не указывали, что в общем случае у вас будет перебор для поиска КВК, а лишь фокусировались на удачных примерах. Для 33 методы из ваших примеров не работали и это должно было или заставить вас описать другой частный случай, или признать перебор. Тут вы уже перебор признали, так что 33 уже не так важно.
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.
Тривиальный перебор тоже не всегда требует корня из N. Он идет до минимального из двух делителей p и q. В худшем случае это может быть примерно до конрня из N.
ЗРД - это про то что КВК в центре с двумя числами, кратными делителям N? Это очевидный факт, показанный в формулах в моем комментарии выше: https://habr.com/ru/articles/908714/comments/#comment_28306208. Да, если у вас есть КВК, ясно как его использовать для получения делителей. ЗРД у вас нигде не говорит о распределении КВК, как далеко они друг от друга расположенны и как долго их искать.
Для 77, вы пишите:
Первый КВК = 4 примыкает к ТКВК.
За ТКВК идет 9. Вот мы уже знаем, что 9^2 = 4 (mod 77), или 9^2 = N+4. Отсюда сразу можно найти N=9^2 - 2^2= (9-2)(9+2) = 7*11. Вы в тексте что-то вычисляете в ваших терминах, но это излишне запутанные терминами вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше.
Тут нам очень повезло, что КВК оказался сразу за ТКВК (иными словами, ceil(sqrt(N)) оказался КВК). Это редкий частный случай. Для чисел до миллиона из двух простых делителей таких чисел 1409 из 288533. Всего 0.4%. Для чисел до 100 миллионов этот процент снижается до 0.1%. Чем больше числа, тем реже такие удачные встречаются.
В общем случае, где за ТКВК не стоит КВК, вам придется перебирать строки вашей таблицы, чтобы найти КВК.
Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ
Вы утверждаете, что это быстрый перебор короче корня из N в общем случае? Я этого не вижу. Могли бы вы, пожалуйста, формализовать как именно вы перебираете строки таблицы в поисках КВК в общем случае, и как-то оценить, сколько строк он переберет? Может, вы вывели какое-то ограничение на то, как далеко от начала таблицы лежит первый РИ? Пока кажется, что они встречаются раз в min(p,q) строк, поэтому поиск РИ нисколько не быстрее тривиального перебора, потому что в худшем случае min(p,q) ~ sqrt(N).
Любая атака начинается с проверки N на признаки делимости и деления на известные простые, когда они заканчиваются можно переходить на псевдопростые, но на практике это не делают. Ищут более короткие пути. Отсюда и множество разных подходов.
Я предложил очередной подход (модель), в котором имеется обоснование для успешной факторизации. Модель - фрагмент НРЧ, содержащий кратные делителей модуля кольца.
Задача как извлечь, "вытащить" хотя бы один делитель. Что удалось сделать - это найти как распределены кратные делителей по фрагменту. КВВ полные квадраты указывают на положение таких кратных, ЗРД. Вы утверждаете о его тривиальности, но пруфов этого я пока не вижу. Все законы, например, Ома для кого-то тривиальны, но не перестают быть законами.
> вы не указывали, что в общем случае у вас будет перебор для поиска КВК.
Это самое простое. Вы все время настаивали, что кроме перебора других возможностей я не демонстрирую. Мне пришлось найти "частные" случаи, когда факторизация возможна без тотального перебора.
>вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше
При N = 77, за 4 следует КВК 25 (в хо =16) и 77+25 =102 уже так не получится
> быстрый перебор короче корня из N в общем случае? Я этого не вижу.
Для N=629 в пределах ТКВК перебираем колонку tп, т.е. N:tп, на шаге 9, tп=17и 629:17=37
Другая возможность: в колонке rс генерируем (rс = rссс =182 = 13х14) и раскладываем в смежные сомножители. Находим хо =13+14 = 27.Получаем КВВ=КВК 27^2(mod 629) =100.
Доказательства у меня пока нет, но и примера, где это нарушено тоже нет (Быстро?).
Вы утверждаете о его тривиальности, но пруфов этого я пока не вижу
Вы этот факт заметили в табличке, но даже не доказали. Вот вам все доказательство по шагам.
Пусть x - "КВК", т.е. x^2 = k^2 (mod N) для какого-то k^2 < N. По определению остатка от деления получаем x^2 = m*N + k^2. Перенесем известное k^2 и применим формулу разности квадратов: (x-k)(x+k) = m*N. Каждый простой делитель N должен встретиться или в x-k или в x+k. Если x-k > 0 и x+k < N (x не из тривиальной что-там у вас было), то делители N попадают в разные множетиели, а значит x-k и x+k делятся на делители N. Вот x - КВК - по середине между двумя делящимеся x-k и x+k. Вот ваш решающий интервал и его середина.
Вся суть и основная идея в школьной формуле a^2-b^2 = (a-b)(a+b). Это тривиальная идея. Все ее доказательство - одна-две строчки школькой математики. Это не может быть сложным не очевидным профессианальному математику факт.
Я предложил очередной подход (модель), в котором имеется обоснование для успешной факторизации
Вы его даже не формализовали, чтобы говорить о том, что вы что-то предложили. Вы научились раскрашивать таблицу, нашли какие-то закономерности, которые на самом деле описываются тривиальными школьными формулами и все.
Ваша работа имела бы ценность, если бы вы все ваши закономерности, вроде ЗРД (он же формула разности квадратов), или случая, когда rccc+1 раскладывается на смежные сомножители, или чисел близнецов, формализовали и доказали, записали в виде четкого и понятного метода (вроде - если А, то применяем формулу B, если C, то формулу D, и т.д.) После чего доказали какие-то факты о применимости вашего метода. Скажем, rccc+1 применим ко всем числам вида (k^2-4)/3 (Это ваши излюбленные примеры N=407 и N=55).
Потом уже вашу охапку критериев надо будет систематизировать и обобщить. Например все ваши частные случаи фактически применимы к числам, у которых фиксированна разность делителей. Вот уже вы решили задачу, когда разность делителей относительно небольшая, что хорошо дополняет тривиальный метод, при котором маленькие делители быстро находятся (ведь, если они большие, то их разность мала). Как-то их оба скрестив вы, может быть, могли бы вывести переборный метод с N^0.(3) в худшем случае. Пришлось бы какие-нибудь суммы рядов или интегралы и теорию чисел с теорией вероятности применить наверняка. Хотя это вряд ли. Но вот это был бы результат и сложный материал, а не вот эти ваши таблицы без единой формулы и доказательства. И фактически без математики.
Для N=629 в пределах ТКВК перебираем колонку tп, т.е. N:tп, на шаге 9, tп=17и
Это не доказательство общего случая. Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро? Все, ваш метод не нужен, ибо вот уже метод, который аж за 3 шага находит делители?
Для какого-нибудь числа из 20 знаков вашему методу понадобится условных 5 миллиардов строк перебрать, что фактически и есть sqrt(N). Если вы опишите мне ваш метод перебора (хоть раз его опишите уже, наконец-то! Часть про КВК мне очевидна, вопрос, как этот КВК найти), я вам смогу нагенерировать на компьютере сколько угодно чисел, где ваш перебор почти корень из N строк посмотрит.
Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро?
Но перебор tп, делитель 3 дает уже на 2-м шаге. и что?
И ничего. Ровно так же, как когда перебор для 629 нашел делитель на 9-ом шаге. Это частный случай. Надо смотреть, сколько там шагов будет для всех чисел в среднем или в худшем случае. Но у вас этих оценок нет, как нет и описания собственно перебора. Вы таблицу по порядку строите? Или генерируете строки, как в какой-то вашей прошлой статье?
Нет не полный, а до 1-го РИ
То есть примерно min(p,q) значений
Как работать с моделью числа II