Комментарии 11
Почему бы вам не обсудить свою статью на https://dxdy.ru/ ?
Подскажите, пожалуйста, как разложить
1 000 036 000 099
с помощью вашей теории?
Это не теория, а закон распределения делителей составных чисел. Чтобы разложить число находим его делители. Для этого извлекаете кв. корень из числа и начиная с х= 1000018 для возрастающих значений находите КВВ. В некоторой точке хd КВВ станет квадратом, т. е КВВ = КВК.
Делители di = хd ±√КВК
чем это отличается от поиска делителей числа путем перебора? Можно с таким же успехом начинать не с 1000018, а с 1 и идти до 1000018. После нахождения первого делителя задача существенно упрощается
Закон (ЗРД) не нацелен на поиск делителей. Он определяет местоположение кратных делителям чисел в НРЧ, а теперь и в ряде целых чисел (РЦЧ), т. е. утверждается, что делителя содержатся в рядах. Вопрос в том как извлечь делители избегая перебора. Начинать с 1 и идти до 1000018 не получится, надо выйти за пределы тривиальной области квадратов. Все эти объяснения не для комментариев. В моих статьях я все подробно излагаю. То, что в статьях не используется крутая математика, не говорит, о том, что это элементарно для понимания. Первая версия ЗРД опубликована в 2014 году. На Хабре ее оценили -8, а расширенную версию уже -9. Но статья 2014 года в топе уже 10 лет. А на мои запросы выдаются мои же статьи. Кто хочет, что-то почерпнуть надо погрузиться в тему факторизации числа. Я в свое время погрузился и теперь окончательно уяснил, что в теории это тупик. Кое-что удается сделать своими силами, не следуя в хвосте "мировых достижений"
Ваш закон уже был открыт Ферма и глубоко исследован им. В общем все современные методы факторизации основаны на разложении Ферма. Вы не увидели довольно тривиального изложения Вашего ЗРД. А все очень просто. y**2 сравнимо с x**2 по модулю N и частный случай это как раз y**2-x**2=N, то значит, что квадратичный вычет для кадрата большиего N совпадает с квадратом до N. Как только вы это нашли, очевидно, что есть два делителя (y-x) и (y+x) и понятно, что они расположены симметрично относительно квадрата.
Вот для числа 15= 16-1, Ваш ЗРД.
[1] 2 3 [4] 5 6 7 8 [9] 10 11 12 13 14 15
[16] 17 18
для 21= 5**2-2**2, [25] будет под [4].
Но для больших чисел такой перебор будет долгим, это обычный экспоненциальный алгорим. Точнее логарифм от корня из N. Метод квадратичного решета является субэкспоненциальным, а решета числового поля еще более быстрый но все равно очень долог.
Ничто не запрещает существования метода аналитической факторизации, но пока его никто не нашел. Нет даже хорошей гипотезы, какой будет форма подходящего уравнения. Я предполагаю что она будет связана с вычетами по праймориалу подходящего размера, по крайней мере, ускорение порядка корня четвертой степени N возникает уже по праймориалу 23 для чисел порядка 70-80 бит.
Вам (а м. б. мне) повезло. Находим квадратичный вычет по модулю вашего составного числа в
указанной мной точке (1000 018)^2(mod 1000036000099)=225 = 15^2 Делителиdi = хd ±√КВК ;
d1 =1000018 +15 = 1000033; d2 =1000018-15 = 1000003;
d1d2 =1000033 x1000003 = 1000 036000099;
К сожалению, на сегодняшний день действие факторизации не может быть задано какими-то простыми вычислениями, а очень большие числа – результаты (сотни цифр в описании) вообще не могут быть факторизованы.
Есть элементарнейшее действие: перебор делителей. Это очень простые вычисления. Но они медленные для очень больших чисел.
Сможем ли мы увидеть и выделить такие кратные делителей N? Они ведь нам неизвестны.
Сможем! Достаточно посмотреть на все числа от 2 до N-1 и посмотреть, какой остаток от деления на них дает N. Если ваш метод не является принципиально быстрее - он абсолютно бесполезен. Если вы строите всю таблицу из N (или даже N/2) строк - ваш метод нисколько не лучше.
Единственное, если бы вы доказали, что в среднем при поиске по этим строкам, генерируя их в вашем странном порядке, делитель встретится раньше чем при простом переборе i=2..N, то тут бы был хоть какой-то смысл, но у вас даже намека на это нет.
Если смотреть только простые, то это принципиально быстрее или не принципиально? :) Квадратичное решето дает принципиальное ускорение за счет факторной базы и поиска чисел, линейная форма произведения которых дает по модулю N полный квадрат. Решето числового поля за счет операций в числовом поле еще сильнее прореживает возможные кандидаты в факторизацию полного квадрата по модулю N.
Я больше интересуюсь вариантами снижения разрядности искомых квадратов операциями над M=N//(p#)**2. Правда подготовка вычетов по праймориалам чисел больше 43 штука зубодробительная, но на мой взгляд перспективная. Когда все получится выпущу статью здесь.
Кстати, строк нужно меньше N/2, потому что после ((N-1)/2)**2 уже проверять нечего, там тривиально. Берем p, например, 107, проверяем НОД(N,107#)==1, значит делителей до 17 нет, теперь можно проверять только до ((N-107**2)/304)**2. Проверял праймориал с длиной числа сколько хватило памяти на ноуте, как же быстро считается НОД, невероятно, браво Евклид
Закон распределения делителей числа (расширенная версия)