Алгоритм факторизации Ленстры

[MaxS]

Помогите,пожалуйста.
Не могу разобраться в алгоритме. Понял его так (если не прав, поправьте):
0)нужно разложить число n.
1)выбираем кривую, точку.
2)задаем В С, высчитываем к.
3)умножаем точку Р на к по модулю: кР mod n
4)в результате получеам либо конечную точку, либо бесконечность...
5)если точка конечная - задаем другую прямую, если бесконечность - то нашли делитель. Где он? Как мы вообще находим делитель?

Написал на си функцию сложения точек в классе Dot ( Dot задается х,у и а-коэффициентом кривой):

   bool Add(int x2, int y2, int mod)
   {
      if (x2==0 && y2==0)
      {
         return true;
      };
      if (x==0 && y==0)
      {
         x = x2;
         y = y2;
         return true;
      };
      if (x==x2 && y!=y2)
      {
         x=0;
         y=0;
         return true;
      };
      if (x==x2 && y==y2)
      {
      int temp;
      int x1 = x;
      temp = Antonim(2*y,mod);
      x = ( (3*x1*x1+a)*temp*(3*x1*x1+a)*temp - 2*x1 ) % mod;
      y = ( ((3*x1*x1+a)*temp)*(x1-x) - y ) % mod;
      return true;
      }
      else
      {
         int temp;
         int x1 = x;

         temp = Antonim(x2-x1,mod);
         x = ( (y2-y)*temp*(y2-y)*temp - x1 - x2 ) % mod;
         y = ( (y2-y)*temp*(x1-x) - y ) % mod;
         return true;
      };
      return false;
   };

Считает она, по-видимому, неправильно, т.к.

   Dot dot(1,1,1);
dot.Add(dot.GetX(),dot.GetY(),35);
dot.Add(dot.GetX(),dot.GetY(),35);

и

   Dot dot(1,1,1);
dot.Add(1,1,35);
dot.Add(1,1,35);
dot.Add(1,1,35);

выдают разные результаты. В чем ошибка?

[Bod]

Было бы неплохо увидеть остальную часть кода. Исходя из того что результаты не совпадают ошибка наверняка там. Проверьте конструктор. А также GetX() и GetY().

[MaxS]

Если в коде есть ошибка, то она есть и в моих рассуждениях, так как программа ститает так же как и я на бумаге:
Пусть нужно поститать 4*P ,P-точка (1,1) на кривой с параметром a=1, вычисления по модулю 13. 4*P можно считать так 4*P = P+P+P+P = 2*P+2*P = 2*(2*P), и результат вроде должен быть одинаковым. Однако у меня результаты получаются различными.
Я бы использовал тег Math, если бы знал как. При попытке открыть ссылку вверху выводит 404 Not Found.
Считаю 4*P = P+P+P+P:
(1,1)+(1,1):
$x = (\frac {3\cdot 1+1} {2})^2-2 = (4\cdot 7)^2-2 = 2$
$y = (4\cdot 7)\cdot (1-2)-1 = -3$
(2,-3)+(1,1):
$x = (\frac {1+3}{1-2})^2-2-1 = (-4)^2-2-1 = 13 = 0$
$y = (-4)\cdot (2+0)+3 = -5$
(0,-5)+(1,1):
$x = (\frac {1+5}{1-0})^2-1 = 9$
$y = 6\cdot (0-9)+5 = -10$

Считаю 4*P = 2*P + 2*P:
(2,-3)+(2-3): $x = ( \frac {3\cdot 2\cdot 2+1}{-2\cdot 3})^2-2\cdot 2 = (13\cdot (-11))^2-4 = 9$
$y = (-143)\cdot (2-9)+3 = 3$

Помогите определить, где ошибка. Идей не осталось...

Формулы сложения точек (x1,y1)+(x2,y2)=(x3,y3):
Если различные:

$x3 = (\frac {y2-y1}{x2-x1})^2-x1-x2$
$y3 = -y1+(\frac {y2-y1}{x2-x1}) \cdot (x1-x3)$
Если совпадают:
$x3=(\frac {3\cdot x1^2+a}{2\cdot y1})^2-2\cdot x1$
$y3=-y1+(\frac{3 \cdot x1^2+a}{2 \cdot y1})\cdot(x1-x3)$

[Jnrty]

Jnrty:

MaxS, на форуме принято записывать формулы в формате \TeX. Будьте любезны исправить своё сообщение, иначе тема отправится в Карантин. О правилах записи формул можно прочесть здесь: http://dxdy.ru/viewtopic.php?t=8355 и http://dxdy.ru/viewtopic.php?t=183. Потратьте несколько минут на изучение.
"Звёздочки" в качестве знака умножения использовать не принято, лучше \cdot или \times: $5\cdot 10^7$ или $5\times 10^7$.

[MaxS]

После многочисленных неудачных попыток вставить формулу нашел тему http://dxdy.ru/viewtopic.php?t=13601 которая все объяснила.

[Echo-Off]

MaxS писал(а):

$y3 = -y1+(\frac {y2-y1}{x2-x1}) \cdot (x1-x3)$

Мне кажется, то, что Вы написали, это $-y_3$. Проверьте.

[RIP]

Echo-Off писал(а):

MaxS писал(а):

$y3 = -y1+(\frac {y2-y1}{x2-x1}) \cdot (x1-x3)$

Мне кажется, то, что Вы написали, это $-y_3$. Проверьте.

Нет, всё верно.

[Echo-Off]

RIP писал(а):

Нет, всё верно

http://en.wikipedia.org/wiki/Elliptic_curve#The_group_law
Формула $y_3$ в случае одинаковых точек тоже неверна (и тоже надо умножить её правую часть на -1)

[RIP]

Echo-Off писал(а):

RIP писал(а):

Нет, всё верно

http://en.wikipedia.org/wiki/Elliptic_curve#The_group_law
Формула $y_3$ в случае одинаковых точек тоже неверна (и тоже надо умножить её правую часть на -1)

В этой статье ошибка. На самом деле $R=(x_R,-y_R)$ (для совпадающих точек написано правильно) и это не то $R$, которое на картинке (на картинке $R=-(P+Q)$).

Добавлено спустя 2 минуты 57 секунд:

Можно посмотреть, например, Коблиц Н. — Введение в эллиптические кривые и модулярные формы, Глава I, $\S7$, формулы (7.1)-(7.4).

[Echo-Off]

Да, был неправ

[MaxS]

Вроде разобрался. Если результат меньше 0, то прибавим к нему mod, тогда результаты совпадают. Я прав?