All streams
Search
Write a publication
Pull to refresh
23
1
Ваулин Арис Ефимович @VAE

Пользователь

Send message

Вы таблицу по порядку строите? 

Да порядок лексикографический. В статьях кроме 2-х последних были только фрагменты таблицы. Колонка Тп содержит ПНЧ, для любых чисел N в ней делитель находится быстрее (это общий случай). Это разьве не очевидно даже школьнику.
> И ничего. Ровно так же, как когда перебор для 629 нашел делитель на 9-ом шаге. Это частный случай
Нет это не частный случай, а общий.

Так-то для 33 тупой перебор найдет делитель 3 уже на третьем шаге. Это значит, что этот наивный, известный сотни лет алгоритм - работает быстро?

Но перебор tп, делитель 3 дает уже на 2-м шаге. и что?

Любая атака начинается с проверки 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.
Доказательства у меня пока нет, но и примера, где это нарушено тоже нет (Быстро?).

>Если она не решена, то откуда вам известно, что это именно инволюция/индепотент без скармливания её в некоторую функцию?
Это известно по определению инволюции (я их обозначаю меньшую (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


>Как помогают инволюции и индепотенты искать факторы не описано. Форма инволюции никогда не была представлена в явном виде
В математике задача вычисления инволюции и идемпотентов кольца не решена. В моей статье "Разложение модели на подмодели. Ч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. Об этом в статье о симметриях.

Не могли бы Вы сменить тональность комментариев (получается, что я что-то вам должен. Не смените общение прекратим. Научитесь уважать собеседника )
Вы с таблицей 77 можете разобраться? Если нет, то я не знаю как помочь.
В таблице модели на РИ указывают КВВ=КВК, т.е. полные квадраты.(их шесть для N = 77).
Первый КВК = 4 примыкает к ТКВК.. Её получаем без построения таблиц. Вычисляем порог (=8) и продолжаем получать КВВ (в (.) 9) КВВ =КВК =4) пока не встретится КВК. Для 33 ответ уже был (признаки делимости используются в любой атаке)
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.

Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ

Согласен, что в последних статьях описания не приводятся. Моей задачей являлось довести смысл Закона распределения делителей (ЗРД). Хочу чтобы он вам всем был понятен. Кстати он доказывается по индукции, но если вы предложите другое доказательство буду рад познакомиться с ним.
ЗРД числа - основа и модели и концепции и направления поиска факторов.

Для примера решение: р=1000082623; q =1000092901 (за доли секунды).
Предположение о факторах нужно не для поиска факторов, а для построения модели поиска (вывода) формул, по которым эти факторы вычисляются.
1. Модель не используется, если формулы получены.
2. Моделью без раскраски кратных строк можно воспользоваться (факторы мы не знаем) для поиска полных квадратов (левых вычетов, т.е. КВВ). Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
3. Я рассматриваю только формульный алгоритм (перебор отвергается), хотя при наличии СММ используются простые делители не до корня из N , а до ближайшего полного квадрата. Используется ЗРД.

Спасибо. Вы не первый, кто об этом пишет, но обо всех претензиях мною уже написано ранее и о раскрасках и о сокращениях. Если вам интересно откройте предыдущую статью. Там комментаторы друг другу помогают из того кто чего уже разобрал. Если есть желание и время ...

>И я повторю: А что делать с N=33?
Если коротко, то разделить на 3.
Готовлю ответ в новой статье, трошки потерпеть надо

Повторю вопрос
Дано только 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.

>Да никак в общем-то.
Это не так. Из модели следует, что с одной стороны rc = (t^2 -1)/4, а с другой rc = 1 + rпо, где rпо = N - rло. Далее, если rc =rccc, то раскладывается в смежные сомножители, т.е. rcсс = t1*tо и модель не строится.

Дано только N = 407 = p*q, p и q - неизвестны, инволюция тоже неизвестна. Что надо сделать и с чем, чтобы найти инволюцию или идемпотенты?

>если вы мне эти закономерности более менее кратко и формально изложите.
Этого я не возьмусь сделать, всего очень много, трудоемко.
Наше общение пока касалось лишь очень частных случаев, т.к. они более прозрачны для понимания, но и они трудно вами воспринимаются. Каждый крючок я вам поясняю. На самом деле все значительно сложнее (иначе бы проблему факторизации давно уже закрыли). Ученики мои все усваивали постепенно и каждое новое явление схватывают сразу.
>про ТКВК и что-то там к чему-то примыкает. 
инволюция (красная) примыкает снизу к желтой ТКВК

Желтая область ТКВК из 11строк порог 11^2<143, уже12^2>143
Желтая область ТКВК из 11строк порог 11^2<143, уже12^2>143

Прекрасно! Перечень вопросов растет. А программу написать слабо?
Или попросить поделиться у того, кто уже написал (см. комментарии).
Обратите внимание, что мне раньше спрашивать было не у кого, как и сейчас тоже. Поэтому списка литературы нет. То чем я располагаю писали разные люди, некоторых уже даже нет в живых. Трогать свои программы я просто боюсь, чтобы не потерять. Храню, что осталось.
На сегодня все, поздно уже. С утра на работу ехать.

Вы ошиблись не для 55, а раньше. Совершенно не поняли мои статьи, но взялись их оценивать и судить, критиковать со своим снобизмом - "барахло". Вас таких на Хабре большинство и ваш почин подхватывают другие. "Не читал, но ставлю минус". Ваши советы можете перечитать. они не к месту. Просто надо мои тексты читать внимательно, там ответы содержатся м.б. не столь обширные как здесь.

N = 143 = 11x13 - 'это "близнецы". Для них инволюция всегда примыкает к ТКВК, т.е. в строке с номером хо =12, т.к. порог ТКВК в хо =11. rk = 121. Так будет для всех "близнецов"

наконец-то проявился (считаю Вас крестником). Не всем и не сразу дано увидеть за табличками алгебраические структуры. Но у вас время еще есть. Это я уже подошел к выходу и не все успею (из задуманного) завершить. Вся надежда на вас. Хотелось бы увидеть реакцию на мой прошлый комментарий, об отсутствии данных о делителях N. Известно только, что N составное. Как определить инволюции, идемпотенты? Есть соображения?

Программист (его уже нет) свои обозначения ввел, а я не умею исправить в тексте программы
Программист (его уже нет) свои обозначения ввел, а я не умею исправить в тексте программы

Для 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 стр.) На Хабре только необходимые для понимания всей картины фрагменты. В мире известны несколько моделей факторизации чисел, не оформленных.
Я с ними знаком и считаю их тупиковыми (не только я). Пришлось создать свою модель и возможно "теорию"

Во всех таблицах и моделях действует один закон. Нашли формулу для одного - можно применить для других. Всегда (для любых 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 арифметических действий получили.

Что-то еще не понято?

Information

Rating
1,701-st
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Date of birth
Registered
Activity