Нужно знать, если это уникальный способ деления?

Question

Несколько месяцев назад я задавал вопрос по «Алгоритму нахождения факторов для простых чисел в линейном времени» в StackOverflow.

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

Однако я хотел бы знать, является ли алгоритм уникальным способом деления и поиска факторов;то есть какой-либо подобный / такой же способ деления известен?Я снова публикую алгоритм здесь:

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is found
  End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
  mL = mL-1;
  r = r+ mR;

  temp1 = r/mL;
  mR = mR + temp1;
  r = r%mL;
}
End; //mR and mL has answer

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

Я понимаю и ценю, что вам может потребоваться понять мой забавный алгоритм, чтобы дать ответы!:)

Дальнейшее объяснение: Да, он работает с числами выше 10 (которые я тестировал) и со всеми натуральными числами.Алгоритм зависит от остатка r, чтобы продолжить. Я в основном сформировал идею, что для числа его коэффициенты дают нам стороны прямоугольников, площадь которых является самим числом.Для всех других чисел, которые не являются факторами, остался бы остаток, или, следовательно, прямоугольник не может быть сформирован полностью.Таким образом, идея заключается в том, что для каждого уменьшения ml мы можем увеличить r = mR + r (в основном сдвигая одну mR с mR mL на r), а затем этот большой r делится на ml, чтобы увидеть, насколько мы можем увеличить mR (какмного раз мы можем увеличить mR для одного уменьшения мл).Таким образом, оставшийся r является r mod ml.Я вычислил число циклов while, которое требуется для нахождения факторов, и оно оказывается ниже или равно 5 * N для всех чисел.Пробный раздел займет больше. *

Спасибо за ваше время, Хариш

Answer 1

Основной цикл эквивалентен следующему коду C:

mR = mL = sqrt(N);
...
mR = N/mL; // have the value of mL less than mR
r = N%mL;
while (r) {
  mL = mL-1;
  r += mR;
  mR = mR + r/mL;
  r = r%mL;
}

Обратите внимание, что после каждого оператора r += mR значение r равно r%(mL-1)+mR.Поскольку r%(mL-1) < mL, значение r/mL в следующем операторе равно либо mR/mL, либо 1 + mR/mL.Я согласен (в результате численного тестирования), что mR*mL = N получается, когда вы выходите из цикла, но я не понимаю, почему.Если вы знаете, почему, вы должны объяснить, почему, если вы хотите, чтобы ваш метод воспринимался серьезно.

С точки зрения эффективности, ваш метод использует то же число циклов, что и Факторизация Ферма , хотяВнутренний цикл факторизации Ферма может быть записан без использования делений, где ваш метод использует две операции деления (r/mL и r%mL) внутри своего внутреннего цикла.В худшем случае для обоих методов внутренний цикл выполняется около sqrt (N) раз.

Answer 2

Есть и другие, например, Алгоритм Полларда и GNFS, о которых вам уже говорили в предыдущем вопросе.