2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Быстрая факторизация
Сообщение18.09.2018, 10:35 


29/07/08
536
К сожалению,я не могу часто присутствовать на форуме, но сообщения просматриваю.

Dmitriy40 в сообщении #1339383 писал(а):
Чего-то я не понял, так как найти $k$ по известному $N$? Например для $N=69424939$? Или Вы решили обратную задачу - сформировать множество чисел специального вида, удобно разложимых на пару множителей? Так она вообще ни разу не интересна и тривиальна.

Можно ли находить число $k$, зная вид функции, задающую $N$?
Давайте представим функцию в таком виде:
$(m^2-1)k^2+2mk=N-1$
Числа $m$ и $(m^2-1)$ взаимнопростые.
Следовательно, это выражение можно записать так:
$2k(\frac{1}{2}(m^2-1)k+m)=N-1$
А значит в качестве $k$ выбираем минимальный делитель числа $(N-1)$ (кроме первой двойки).
Перепишем фунцию для $N$ в таком виде:
$m^2k^2+2mk=N-1+k^2$, где число $k$ известно из предыдущего рассуждения.
Но это выражение можно и так представить:
$m(mk^2+2k)=N-1+k^2$
Другими словами, в качестве числа m выбираем минимальный делитель числа $(N-1+k^2)$
Таким образом пара чисел $(k,m)$ задает функцию для $N$, и множитель $p$, соответственно.

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


23/07/05
17982
Москва
Побережный Александр в сообщении #1339869 писал(а):
Можно ли находить число $k$, зная вид функции, задающую $N$?
Давайте представим функцию в таком виде:
$(m^2-1)k^2+2mk=N-1$
Вы на примере покажите. Хотя бы для $N=69\,424\,939$.

 Профиль  
                  
 
 Re: Быстрая факторизация
Сообщение18.09.2018, 11:57 


16/08/05
1153
Код:
km(n)=
{
Dk= divisors(n-1);
K=[];
for(i=1, #Dk, if(Dk[i]>2 && !(Dk[i]%2), K= concat(K,[Dk[i]/2])));
for(i=1, #K,
k= K[i];
M= divisors(n-1+k^2);
for(j=1, #M,
  m=M[j];
  if((n-1+k^2)/m==k*(m*k+2), print("k= ",k,"    m= ",m))
)
)
};



Код:
?
? \r km.gp
?
? km(69424939)
k= 34712469    m= 1
?
? km(8616460799)
k= 4308230399    m= 1

 Профиль  
                  
 
 Re: Быстрая факторизация
Сообщение18.09.2018, 12:51 


21/05/16
4292
Аделаида
Побережный Александр в сообщении #1339379 писал(а):
$N=(m^2-1)k^2+2mk+1$, где m - натуральное число

Это все числа. $m=1$ и $k=\frac{N-1}2$.

-- 18 сен 2018, 19:23 --

Множители при этом тривиальные.
Множетели нетривиальны только для чисел специального вида. А для таких чисел факторизация не важна.

-- 18 сен 2018, 19:27 --

Можно делать перебор m, и проверять, имеет ли решение квадратное уравнение. Перебор делителей и то эффективнее.

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


21/11/12
1968
Санкт-Петербург
Someone в сообщении #1339809 писал(а):
Кстати, Д. Кнут демонстрирует применение метода Ферма с предварительным просеиванием по нескольким модулям на примере именно вот этого числа:
Andrey A в сообщении #1339713 писал(а):
8616460799

Британские ученые идут теперь в Wolfram и пишут Factor 8616460799. Русские придумывают сложности чтобы не платить.

Побережный Александр в сообщении #1339869 писал(а):
Перепишем функцию для $N$ в таком виде:
$m^2k^2+2mk=N-1+k^2$

Лучше в таком виде: $(mk+1)^2-k^2=N.$ Основание старшего квадрата $\equiv 1 \mod k.$ Чем больше $k$, тем меньше вероятность указанного события, в частности для $N=69424939$ оно не происходит. Но если и повезло, дальнейшее предполагает знание делителей числа $N-1$ с последующим перебором. В этом случае есть более надежные способы, например такой https://dxdy.ru/post967926.html#p967926. С его помощью в несколько шагов получаем $N=69424939=\dfrac{857201^2-5^2}{103^2-5^2}$. Квадраты в числителе сравнимы по $\mod N$, отсюда $\gcd (69424939,857201+5)=8747,\ \gcd (69424939,857201-5)=7937$ и $8747\cdot 7937=69424939.$ А перебирать уж всяко легче квадраты по методу Ферма.

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

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



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

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


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

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