Быстрая факторизация

[Побережный Александр]

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

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$, соответственно.

[Someone]

Побережный Александр в сообщении #1339869 писал(а):

Можно ли находить число $k$, зная вид функции, задающую $N$?
Давайте представим функцию в таком виде:
$(m^2-1)k^2+2mk=N-1$

Вы на примере покажите. Хотя бы для $N=69\,424\,939$.

[dmd]

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

[kotenok gav]

Побережный Александр в сообщении #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, и проверять, имеет ли решение квадратное уравнение. Перебор делителей и то эффективнее.

[Andrey A]

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.$ А перебирать уж всяко легче квадраты по методу Ферма.