2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение29.04.2007, 07:50 


23/01/07
3415
Новосибирск
Артамонов Ю.Н. писал(а):
Все это очень напоминает факторизацию по Ферма, и вычислительная сложность видимо такого же порядка.

Учитывая специфику раздела форума, хочу попросить Вас напомнить суть факторизации по Ферма.

Ранее я писал, что "вряд ли можно составить компактный тест проверки на простоту числа на основе рассматриваемого свойства".
Но, с другой стороны:
У существующих "быстрых" тестов есть одни соперники - числа Кармайкла, которые либо сами являются треугольными числами, либо довольно легко проверяются на основе рассматриваемого свойства (для проверки, на мой взгляд, можно последовательно использовать $ Q = 1,2,3,4... $). Наверное, можно совместить две проверки?
По крайней мере, мне так казтца... :D
(чисел Кармайкла у меня маловато)

 Профиль  
                  
 
 
Сообщение29.04.2007, 08:14 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Батороев
Почитайте вот это

 Профиль  
                  
 
 
Сообщение29.04.2007, 11:05 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Да, я имел в виду именно то, на что указал RIP

 Профиль  
                  
 
 
Сообщение29.04.2007, 17:22 


23/01/07
3415
Новосибирск
RIP писал(а):
Батороев
Почитайте вот это


С удовольствием посмотрел по Вашей ссылке. Спасибо RIP'у и Ю. Н. Артамонову.
Подобный метод факторизации приходил и мне на ум, что может подтвердить
ссылка.

Но на мой взгляд, это несколько иной метод: суть его можно определить, как
проверка на повторяемость остатков квадратов чисел.
Такая проверка (факторизация) начинается с чисел $ a > \sqrt{N} $ и определяется: не является ли остаток $ a^2\equiv{b^2(modN)} $, т.е. не повторил ли он остаток квадрата числа $ b < \sqrt{N} $, либо не повторяются ли уже проверенные, либо $ a^2\equiv{a(modN)} $,
Для метода Ферма важным является приближенность отношения $ \frac{a}{b} = 1$.
Именно поэтому, я хотел далее предложить совместно применять оба метода, т.к. метод Ферма некоторым образом "заполняет" пробел в указанных мной ранее "приемлемых" диапазонах рассматриваемого способа:
$ 0,33 < \frac{a}{b} < 0,75 $
$ 1,33 < \frac{a}{b} < 3 $
Тем более, что и тот, и другой метод предполагают использование множителей $ Q $.

p.s.1 Условием выполнения факторизации методом Ферма с первого шага
числа $ N = a*b $ по моим тогдашним выводам являлось выполнение неравенства:
$ (a - b)^2 < 8 \sqrt{N} $.
p.s.2 Дополнения к списку определений простых чисел, которые высказал Ю. Н. Артамонов, для меня новы и интересны (не смотря на то, что один из них является производной от предлагаемого, тем не менее является интересным сам по себе). Отдельное спасибо за это Ю. Н. Артамонову :!:

 Профиль  
                  
 
 
Сообщение30.04.2007, 23:06 


16/08/05
1146
Уместно ли далее развить идею Батороева, рассматривая множитель факторизуемого числа как разность k-угольных чисел? Формула для m-ного k-угольного числа:
$T_{m}^{k}=m+(k-2)m(m-1)/2$
Интересно то, что для некоторых k ответ получаем вообще за 1 шаг:
Код:
fc = Compile[x,
  S = 2699*7127;
  For[k = 3, k < 1000,
    m = IntegerPart[(k - 4 + (8(S - 1)(k - 2) + k^2)^0.5)/(2 (k - 2))] + 1;
    a = 1; mm = m;
    While[a ≠ 0 && m - mm < 1000,
      T = m + (k - 2)(m - 1)m/2;
      U = (8(T - S - 1)(k - 2) + k^2)^0.5;
      a = FractionalPart[U];
      m++
    ];
    If[a == 0, Print["k= ", k, " шагов= ", m - mm, " нод= ", GCD[2(k - 2)(m - 1) - (k - 4 + U), S]]];
    k++
  ]];

fc[1]

k= 3 шагов= 60 нод= 2699
k= 4 шагов= 528 нод= 2699
k= 5 шагов= 306 нод= 7127
k= 7 шагов= 638 нод= 7127
k= 9 шагов= 24 нод= 7127
k= 14 шагов= 73 нод= 2699
k= 16 шагов= 201 нод= 7127
k= 30 шагов= 803 нод= 2699
k= 32 шагов= 31 нод= 2699
k= 50 шагов= 462 нод= 2699
k= 65 шагов= 1 нод= 2699
k= 68 шагов= 548 нод= 2699
$Aborted


Для $S = 898423*112303$ получилось
Код:
k= 842 шагов= 10 нод= 898423
k= 1742 шагов= 10 нод= 898423
k= 3629 шагов= 81 нод= 898423


Для $S = 6334969*2402537$ уже не дождался.
Но зато при дополнительных множителях $S = 6334969*2402537*3^2*5^2*7^2*11^2$ решение нашлось:
Код:
k= 122 шагов= 886 нод= 1742116475
FactorInteger[1742116475]
{{5, 2}, {11, 1}, {6334969, 1}}

 Профиль  
                  
 
 
Сообщение01.05.2007, 13:28 


23/01/07
3415
Новосибирск
dmd писал(а):

Для $S = 6334969*2402537$ уже не дождался.
Но зато при дополнительных множителях $S = 6334969*2402537*3^2*5^2*7^2*11^2$ решение нашлось:
Код:
k= 122 шагов= 886 нод= 1742116475
FactorInteger[1742116475]
{{5, 2}, {11, 1}, {6334969, 1}}


В общем случае, использование дополнительных множителей может благотворно сказаться, по-видимому, для многих и других способов факторизации.

При этом наличие в числе $ Q = q_1*q_2*q_3*... $ подмножителей во второй степени - требование отнюдь не обязательное, особенно, если Вы уже знаете, что отношение множителей искомого числа друг к другу далеко от оптимального.

Важнее, чтобы возможных отношений подмножителей $ q $ друг к другу было, как можно больше.
Например, при факторизации по Ферма, указанное выше условие выполнения факторизации с первого шага при умножении проверяемого числа на дополнительный множитель трансформируется в следующее:
$ (a*q_2*q_3*... - b*q_1*...)^2 < 8\sqrt{Q*N} $.

 Профиль  
                  
 
 
Сообщение01.05.2007, 19:44 


16/08/05
1146
Сам собою напрашивается вопрос: какой набор подмножителей даст наибольшее количество их соотношений?

 Профиль  
                  
 
 
Сообщение02.05.2007, 09:26 


23/01/07
3415
Новосибирск
dmd писал(а):
Сам собою напрашивается вопрос: какой набор подмножителей даст наибольшее количество их соотношений?

Именно на этом вопросе я чуть не потянул головные связки :D
Чрезмерно большие Q (относительно проверяемого числа N) могут не подойти, по крайней мере для факторизации по Ферма.
В таком случае кажется, что лучше использовать, степени 2 (выше 2-ой) и 3, постепенно добавляя следующие простые числа. Как вариант, по-видимому, можно использовать факториалы чисел ( > 3!).

Если сравнить к примеру два числа
$ Q_1 = 302400 = 2^6*3^3*5^2*7 $
и $ Q_2 = 301687 = 29*101*103 $, то при примерном их равенстве мы получаем для $Q_1$ 61 комбинацию целочисленных соотношений, а для $ Q_2 $ - всего 4.
Хотя, еще раз повторюсь, что здесь требуются серьезные исследования.

 Профиль  
                  
 
 
Сообщение03.05.2007, 09:13 


23/01/07
3415
Новосибирск
Батороев писал(а):
[У существующих "быстрых" тестов есть одни соперники - числа Кармайкла...
...(чисел Кармайкла у меня маловато)

Интересно, а можно ли доказать, что составное число, преодолевшее хотя бы один раунд проверки тестом Миллера-Рабина, является именно числом Кармайкла, а не каким-либо другим псевдопростым?
Если это возможно, то добавив к тесту Миллера-Рабина последующую проверку на делимость проверяемого числа m на числа
от $ 3 $ до $ \sqrt{\frac{4m}{1+ \sqrt{1 + 8m}} $ можно было бы получить точный тест с числом операций меньшим, чем у классического (проверка делимости числа m на числа от $ 3 $ до $ \sqrt{m} $).

p.s. А какие другие точные тесты еще существуют?
Насколько я слышал, что детерминированный полиномиальный тест еще не доведен до состояния "точный"?

 Профиль  
                  
 
 
Сообщение04.05.2007, 12:15 


23/01/07
3415
Новосибирск
Батороев писал(а):
Интересно, а можно ли доказать, что составное число, преодолевшее хотя бы один раунд проверки тестом Миллера-Рабина, является именно числом Кармайкла, а не каким-либо другим псевдопростым?

Действительно, если множители составного числа $ m = p*q*r*... $ представить в виде:
$ p = x2^f  + 1 $
$ q = y2^g + 1 $
$  r = z2^h + 1 $,
. . . . .
(где x, y, z - нечетные целые числа, f, g, h - целые числа)
то условие $ a^{{2^k}{t}}\equiv{-1} (mod m) $ теста Миллера-Рабина (см. здесь) выполнимо, если $ k $ нацело делится на x, y, z...(минимальное требование), что невозможно без свойства, которое присуще только числам Кармайкла, а именно:
"$ (m -1) $ без остатка делится на $ (p - 1) $, $ (q - 1) $, $ (r - 1) $...".

Остается только изменить определение раунда :)



p.s. Еще одно определение простых чисел:
5. Простое число - это число, которое не удовлетворяет условию сравнения:
$ (\frac{N}{3})!\equiv{0} (mod N) $ :D
К этому свойству я прибегаю тогда, когда необходимо быстро выяснить простое ли число до 100000 (максимум возможностей инженерного калькулятора Windows).

 Профиль  
                  
 
 
Сообщение08.05.2007, 11:26 


23/01/07
3415
Новосибирск
Батороев писал(а):
Например, дано число $ N = 19235773 $
Ближайшее треугольное число $ T_m $ , превосходящее N:
$ \sqrt{2*19235773} = 6203 $
$ T_m = T_{6203} = \frac{m*(m+1)}{2} = \frac{6203*6204}{2} = 19241706 $
Проверяем, является ли разность$ (T_m - N) $ треугольным числом, т.е. целочисленно ли $ \sqrt{8(T_m - N) + 1} ?$


Здесь, пожалуй, можно немного сэкономить усилия, введя предварительную проверку:
Если $ (T_m - N) $ не удовлетворяет условию одного из сравнений:
$ (T_m - N) \equiv{0}(mod 7) $
$ (T_m - N) \equiv{1}(mod 7) $
$ (T_m - N) \equiv{3}(mod 7) $
$ (T_m - N) \equiv{6}(mod 7) $,
то это - не треугольное число.
Исходя из этого свойства, в рассматриваемом примере можно было сократить 26 шагов.

 Профиль  
                  
 
 
Сообщение02.06.2007, 11:24 


23/01/07
3415
Новосибирск
Тем, кто пользуется методом факторизации по Ферма, по-видимому, может пригодиться следующее мое предположение (естественно, если оно верно):

Для всех нечетных составных чисел m = p*q (где p и q - числа, взаимнопростые с числом 144), имеющих по основанию 144 одинаковые остатки,
остатки чисел $ (\frac{p + q}{2})^2 $ и $ (\frac{p - q}{2})^2 $ определены единственным образом.


В виду корявости формулировки приведу пример:
Дано число $ m = 4 398 693 379 $
$ m\equiv{115}(mod 144) $
На малых числах (в данном случае, на числе 115) можно видеть, что числа с таким остатком имеют
$ (\frac{115 + 1}{2})^2\equiv{52}(mod 144) $ или
$ (\frac{23 + 5}{2})^2\equiv{52}(mod 144) $.

Остаток $ {52}(mod 144) $ имеют квадраты чисел $ (72*k\pm{14}) $, где $ k $ - целое число.

Проверяя методом Ферма только такие числа, мы на 135-м ходу получим положительный результат (против 4827 шагов по обычному пути метода Ферма) в виде
$ 71150^2\equiv{25761^2}(mod 4 398 693 379) $.

 Профиль  
                  
 
 
Сообщение04.06.2007, 09:04 


23/01/07
3415
Новосибирск
Батороев писал(а):
Тем, кто пользуется методом факторизации по Ферма, по-видимому, может пригодиться следующее мое предположение (естественно, если оно верно):

Для всех нечетных составных чисел m = p*q (где p и q - числа, взаимнопростые с числом 144), имеющих по основанию 144 одинаковые остатки,
остатки чисел $ (\frac{p + q}{2})^2 $ и $ (\frac{p - q}{2})^2 $ по основанию 144 определены единственным образом.


Не научился я доказывать что-либо математически, но попытаюсь:
Имеются два числа $ m = pq $ и $ n = ab $, имеющие одинаковый остаток по основанию 144, где
$ a, b, p, q $ - числа, взаимнопростые с числом $ 144 = 2^4*3^2 $.
Представление этих чисел в виде разности квадратов следующее:
$ m = (\frac{pq +1}{2})^2 - (\frac{pq - 1}{2})^2 = (\frac{p + q}{2})^2 - (\frac{p - q}{2})^2 $
$ n = (\frac{ab +1}{2})^2 - (\frac{ab - 1}{2})^2 = (\frac{a + b}{2})^2 - (\frac{a - b}{2})^2 $
Т.к. рассматриваемые числа имеют одинаковые остатки по основанию 144, то одинаковые остатки имеют и выражения:
$ (\frac{pq +1}{2})^2\equiv{s}(mod 144) $
$ (\frac{ab +1}{2})^2\equiv{s}(mod 144) $,

Аналогично:
$ (\frac{pq - 1}{2})^2\equiv{t}(mod 144) $
$ (\frac{ab -1}{2})^2\equiv{t}(mod 144) $

Т.к. $ [(\frac{pq +1}{2})^2 - (\frac{p + q}{2})^2] = \frac{(p^2 - 1)(q^2 - 1)}{4}\equiv{0}(mod 144) $
$ [(\frac{ab +1}{2})^2 - (\frac{a + b}{2})^2] = \frac{(a^2 - 1)(b^2 - 1)}{4}\equiv{0}(mod 144)  $,
то
$ (\frac{p + q}{2})^2\equiv{s}(mod 144) $
$ (\frac{a + b}{2})^2\equiv{s}(mod 144) $.

Т.к. $ [(\frac{pq - 1}{2})^2 - (\frac{p - q}{2})^2] = \frac{(p^2 - 1)(q^2 - 1)}{4}\equiv{0}(mod 144) $
$ [(\frac{ab - 1}{2})^2 - (\frac{a - b}{2})^2] = \frac{(a^2 - 1)(b^2 - 1)}{4}\equiv{0}(mod 144)  $,
то
$ (\frac{p - q}{2})^2\equiv{t}(mod 144) $
$ (\frac{a - b}{2})^2\equiv{t}(mod 144) $.

Не уверен, что это - хорошее доказательство (а может и не доказательство вообще),
но важнее другое:

Аналогичным образом можно рассматривать и другие основания, такие как
$ 14400 = 2^6*3^2*5^2 $
$ 7056 = 2^4*3^2*7^2 $
$ 66585600 = 2^{10}*3^2*5^2*17^2 $ и т.д.


Это утверждение дает возможность оптимизировать метод факторизации Ферма, имея в виду, что:

$ (pq)^{n} = (\frac{p^n + q^n}{2})^2 - (\frac{p^n - q^n}{2})^2 $.

 Профиль  
                  
 
 
Сообщение06.06.2007, 19:23 
Аватара пользователя


27/05/07
115
Строим полуокружность на ее диаметре AB.
Все следующие ломаные имеют начальную точку A и конечную точку B.
k(1)=2.
В полуокружность вписываем равносторонний k(1)-сторонник.
Вписываем в ту же полуокружность равносторонний k(2)-сторонник с наименьшим периметром такой, что k(2)-сторонник не имеет общих вершин с k(1)-сторонником кроме A и B.
Вписываем в ту же полуокружность равносторонний k(3)-сторонник с наименьшим периметром такой, что k(3)-сторонник не имеет общих вершин с k(1)-сторонником и k(2)-сторонником кроме A и B.
Вписываем в ту же полуокружность равносторонний k(4)-сторонник с наименьшим периметром такой, что k(4)-сторонник не имеет общих вершин с k(1)-сторонником, k(2)-сторонником и k(3)-сторонником кроме A и B.
...
Пусть таким образом построены все k(1)-,...,k(n-1)-сторонники.
Сколько сторон будет у k(n)-сторонника?

 Профиль  
                  
 
 
Сообщение06.06.2007, 20:07 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Боян. http://dxdy.ru/viewtopic.php?p=67394
С другой стороны, если рассматривать в контексте данной темы, то может, и не боян...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group