Обсуждение:Метод Лемана

А метод то не работает! (по крайней мере в том изложении, что приведено в статье).

Контрпример: $n=15=3\cdot 5$. Диапазон изменения k: $15^{1/3}=2.466$, k = 1 ... 2 Имеем:

k=1, ${\frac {15^{1/6}}{4\cdot 1^{1/2}}}=0.393$, d = 0 ... 1

• d=0 A=7 B=-11
• d=1 A=8 B=4

k=2, ${\frac {15^{1/6}}{4\cdot 2^{1/2}}}=0.278$, d = 0 ... 1

• d=0 A=10 B=-20
• d=1 A=11 B=1

Множитель не найден, значить 15 — простое число!

PS. На всякий случай привожу программу (после корректировки ее можно добавить в статью):

program Project1;
{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

var
  N, I, k, d, B, A, sqrt_B: Integer;
  Found: Boolean;

begin
  N := 15;

  Writeln('N=', N);

  Found := False;
  for I := 2 to Trunc(Power(N, 1/3)) do
    if N mod I = 0 then begin
      Writeln('Factor found: ', I);
      Found := True;
      break;
    end;

  if not Found then begin
    Writeln('Factor not found at first step');

    for k := 1 to Trunc(Power(N, 1/3)) do
      for d := 0 to Trunc( Power(N, 1/6) / (4 * Sqrt(k)) ) + 1 do begin
        Write('  k=', k, ' d=', d);

        A := Trunc(Sqrt(4*k*N)) + d;
        B := Sqr(A) - 4*k*N;

        Writeln(' A=', A, ' B=', B);

        if B < 0 then
          continue;

        sqrt_B := Trunc(Sqrt(B));
        if Sqr(sqrt_B) = B then
          if (1 < d) and (d < N) then begin
            Writeln('Factor found on second step: ', d);
            Found := True;
            Readln;
            exit;
          end;
      end;
  end;

  Readln;
end.

Evatutin 09:33, 7 ноября 2010 (UTC)

Уважаемый Evatutin, проверьте ещё раз свои вычисления, ибо для Вашего «контрпримера» всё срабатывает. Идём по алгоритму Лемана:

• Шаг 1. $\lfloor n^{1/3}\rfloor =\lfloor 15^{1/3}\rfloor =\lfloor 2{,}466\ldots \rfloor =2$. Для $a=2$ проверяем, что 15 не делится на 2. Переходим на Шаг 2.
• Шаг 2. Значит число составное. $\lfloor n^{1/3}\rfloor =\lfloor 15^{1/3}\rfloor =2$, $k=1,\;2.$
  • Случай $k=1$. $\left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1=\left\lfloor {\frac {15^{1/6}}{4{\sqrt {1}}}}\right\rfloor +1=\lfloor 0{,}393\ldots \rfloor +1=0+1=1$. Значит $d=0,\;1$.
    • Случай $d=0$. Проверяем, $\left(\lfloor {\sqrt {4kn}}\rfloor +d\right)^{2}-4kn=\left(\lfloor {\sqrt {4\cdot 1\cdot 15}}\rfloor +0\right)^{2}-4\cdot 1\cdot 15=(\lfloor 7{,}746\ldots \rfloor )^{2}-60=7^{2}-60=49-60=-11$. Не является квадратом натурального числа!
    • Случай $d=1$. Проверяем, $\left(\lfloor {\sqrt {4kn}}\rfloor +d\right)^{2}-4kn=\left(\lfloor {\sqrt {4\cdot 1\cdot 15}}\rfloor +1\right)^{2}-4\cdot 1\cdot 15=(\lfloor 7{,}746\ldots \rfloor +1)^{2}-60=(7+1)^{2}-60=64-60=4$ — квадрат натурального числа. Значит вычисляем $A=\left\lfloor {\sqrt {4kn}}\right\rfloor +d=\left\lfloor {\sqrt {4\cdot 1\cdot 15}}\right\rfloor +1=7+1=8$ и $B={\sqrt {A^{2}-4kn}}={\sqrt {8^{2}-4\cdot 1\cdot 15}}={\sqrt {64-60}}={\sqrt {4}}=2$. Сравнение $(A-B)(A+B)\equiv 0{\pmod {n}};\;(8-2)\cdot (8+2)\equiv 0{\pmod {15}};\;6\cdot 10\equiv 0{\pmod {15}};\;60\equiv 0{\pmod {15}}$ даёт положительный результат. Находим $d=\gcd(A-B,\;n)=\gcd(8-2,\;15)=\gcd(6,\;15)=3$. $d=3$ удовлетворяет $1<3<15$. Значит факторизация найдена $15=3\cdot 5$.

— KleverI 10:35, 7 ноября 2010 (UTC)

Спасибо за развернутый ответ, код я поправил, работает! Исходя из описания я неправильно интерпретировал значение d (оно встречается в двух местах, я бы в одном из них заменил на другую букву — в коде у меня dd — в статье исправлю). Evatutin 19:54, 7 ноября 2010 (UTC)

Откат правки с программным кодом

Чтобы не развязывать войну правок, хотелось бы узнать мнение остальных участников о целосообразности включения программного кода в статью (а потом, если не понравится, откатить). На мой взгляд отлаженный и протестированный программный код позволяет легче разобраться с методом, чем описание на псевдокоде. Подобная практика встречается в других статьях: Числа Стирлинга второго рода, Одномерное стационарное уравнение Шрёдингера, Метод бисекции, Алгоритм_DDA-линии, en:Euler spiral и т.д. Ваше мнение? Evatutin 09:37, 11 ноября 2010 (UTC)

Во-первых, если сопроводите программный код ВП:АИ с этим кодом, — возражений на добавление его в статью нет. Но коду, написанному абы кем-то на его любимом языке программирования — отказать. Во-вторых, алгоритмы нужно иллюстрировать псевдокодом, как например, это сделано в Тест Миллера-Рабина. Тогда вопрос предпочтения языка снимется сам собой. Maxal 14:26, 11 ноября 2010 (UTC)

Во-первых, код написан мной, а не абы кем, и ссылку на него я дать не смогу. Если вы сомневаетесь в моей квалификации или в правильности кода, можете взять Pascal или Delphi и проверить (я проверял, он работает). Если не умеете программировать, можно попросить еще кого-нибудь, кто умеет... Во-вторых, это ваше личное мнение, что алгоритмы необходимо иллюстрировать псевдокодом, или вы можете поделиться ссылкой на ВП:ПУ? В программе на псевдокоде сложнее найти ошибку, т.к. ее невозможно напрямую подвергнуть отладке... В третьих, в вы сами ВП:АИ читали? Там ни слова не сказано о коде программ, зато есть вот что:

Если вы сомневаетесь в достоверности какой-либо информации, но не имеете полной, основанной на источниках уверенности в ошибке, не следует сразу удалять сомнительный фрагмент, так как некоторые участники могут обвинить вас в том, что вы не дали им шанса на улучшение статьи (в целом это производит впечатление агрессивных действий). Поэтому лучше ставить после сомнительных высказываний шаблон {{нет источника}}. Удалять сомнительную информацию (без достоверных источников) следует лишь в том случае, если вы уверены в том, что она неверна, или если на шаблон {{нет источника}} не было реакции в течение как минимум двух недель. Также возможно удаление сомнительной информации, если к такому решению авторы статьи придут в обсуждении.

Прошу перестать откатывать мою правку (по крайней мере до завершения обсуждения)...

Во-первых, да, я сомневаюсь в вашей квалификации, пока она не подтверждена независимыми ВП:АИ. И работа кода на каком-то примере не доказывает его правильность. Во-вторых, предупреждаю вас о ВП:ЭП. В третьих, вы сами признались, что код лично ваш (что попахивает ВП:ОРИСС). Но как бы там ни было, пусть код побудет пару недель, но если вы не приведете для него ВП:АИ, он будет удален. Maxal 16:59, 11 ноября 2010 (UTC)