فاکتورگیری خم بیضوی لنسترا

فاکتورگیری خم بیضوی لنسترا (Lenstra elliptic-curve factorization) یا روش فاکتورگیری خم بیضوی (ECM) یک الگوریتم سریع (سرعت اجرای زیرنمایی) برای عامل‌گیری عدد صحیح در خم بیضوی است. در حال حاضر هنوز بهترین الگوریتم برای تقسیم‌کننده‌ها است که بیش از ۲۰ تا ۲۵ رقم (۶۴ تا ۸۳ بیت) نیستند، زیرا زمان اجرای آن تحت تأثیر اندازه کوچکترین عامل p قرار می‌گیرد و نه عدد n که فاکتورگیری می‌شود.

اغلب، ECM برای حذف عوامل کوچک از عدد صحیح بسیار زیاد که عوامل بسیار دارد استفاده می‌شود. بزرگترین عددی که تاکنون با استفاده از ECM فاکتورگیری شده دارای ۸۳ رقم است و در ۷ سپتامبر ۲۰۱۳ توسط R. Propper کشف شد. افزایش تعداد منحنی‌های آزمایش شده، شانس یافتن عامل را بهبود می‌بخشد، اما نسبت این افزایش تعداد خطی نیست.

فاکتورگیری خم بیضوی لنسترا

روش یافتن عوامل عدد n به صورت زیر است:

۱- خم بیضوی تصادفی در $\mathbb {Z} /n\mathbb {Z}$ را با معادله فرم y$y^{2}=x^{3}+ax+b{\pmod {n}}$ را با یک نقطه غیر بدیهی $P(x_{0},y_{0})$ بر روی آن انتخاب کنید.

اینکار را می‌توان با انتخاب تصادفی $x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z}$ و سپس محاسبه $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}$ انجام داد.

2-جمع P و Q بر روی خم که به عنوان گروه عملیاتی P ⊕ Q تعریف می‌شوند. برای جمع به روش زیر عمل میکنیم:

${\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}$.

${\begin{aligned}s&={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=s^{2}-x_{p}-x_{q}\\y_{r}&=s(x_{p}-x_{r})-y_{p}\\\end{aligned}}$.

نکته: اگر خواستیم یک نقطه را با خودش جمع کنیم(P ⊕ P). آنگاه $s={\frac {3x_{p}^{2}+a}{2y_{p}}}$

3-محاسبه eP بر روی خم بیضوی (mod n).

مثال

این مثال از (Trappe و Washington 2006) با کمی توضیحات آورده شده‌است.

ما می خواهیم به عامل $n=455839$ بپردازیم. خم بیضوی $y^{2}=x^{3}+5x-5$ را با نقطه P = (1، 1) بر روی آن انتخاب می‌کنیم و سعی می‌کنیم (10!)P را محاسبه کنیم.

ابتدا 2P=P ⊕ P را محا سبه میکنیم:

$s={\frac {3x_{p}^{2}+a}{2y_{p}}}(modn)$ پس

$s={\frac {3+5}{2}}(mod455839)$ 

خواهد بود یعنی $s=4$

${\begin{aligned}x_{2}&=s^{2}-x_{p}-x_{p}\\y_{2}&=s(x_{p}-x_{2})-y_{p}\\\end{aligned}}$.

${\begin{aligned}x_{2}&=4^{2}-1-1=14\\y_{2}&=4(1-14)-1=-53\\\end{aligned}}$.

فقط برای بررسی اینکه این 2P در واقع بر روی خم است: $(-53)^{2}=2809=14^{3}+5*14-5$

سپس 4P=2P ⊕ 2P را محا سبه میکنیم:

به همان روش بالا $s={\frac {593}{-106}}(mod455839)$

منابع

Lenstra elliptic-curve factorization. (2018). En.wikipedia.org. Retrieved 2 March 2018, from en:Lenstra elliptic-curve factorization