ⓘ فاکتورگیری منحنی بیضوی لنسترا یا روش فاکتورگیری منحنی بیضوی یک الگوریتم سریع برای عامل‌گیری عدد صحیح در منحنی بیضوی است. در حال حاضر هنوز بهترین الگوریتم برای ت ..

                                     

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

فاکتورگیری منحنی بیضوی لنسترا یا روش فاکتورگیری منحنی بیضوی یک الگوریتم سریع برای عامل‌گیری عدد صحیح در منحنی بیضوی است. در حال حاضر هنوز بهترین الگوریتم برای تقسیم‌کننده‌ها است که بیش از ۲۰ تا ۲۵ رقم نیستند، زیرا زمان اجرای آن تحت تأثیر اندازه کوچکترین عامل p قرار می‌گیرد و نه عدد n که فاکتورگیری می‌شود.

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

                                     

1. فاکتورگیری منحنی بیضوی لنسترا

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

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

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

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

P + Q = R x p, y p + x q, y q = x r, y r {\displaystyle {\begin{aligned}P+Q&=R\\x_{p},y_{p}+x_{q},y_{q}&=x_{r},y_{r}\end{aligned}}}.

s = 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 {\displaystyle {\begin{aligned}s&={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=s^{2}-x_{p}-x_{q}\\y_{r}&=sx_{p}-x_{r}-y_{p}\\\end{aligned}}}.

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

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

                                     

2. مثال

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

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

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

s = 3 x p 2 + a 2 y p m o d n {\displaystyle s={\frac {3x_{p}^{2}+a}{2y_{p}}}modn} پس

s = 3 + 5 2 m o d 455839 {\displaystyle s={\frac {3+5}{2}}mod455839}

خواهد بود یعنی s = 4 {\displaystyle s=4}

x 2 = s 2 − x p − x p y 2 = s x p − x 2 − y p {\displaystyle {\begin{aligned}x_{2}&=s^{2}-x_{p}-x_{p}\\y_{2}&=sx_{p}-x_{2}-y_{p}\\\end{aligned}}}.

x 2 = 4 2 − 1 − 1 = 14 y 2 = 4 1 − 14 − 1 = − 53 {\displaystyle {\begin{aligned}x_{2}&=4^{2}-1-1=14\\y_{2}&=41-14-1=-53\\\end{aligned}}}.

فقط برای بررسی اینکه این 2P در واقع بر روی منحنی است: − 53 2 = 2809 = 14 3 + 5 ∗ 14 − 5 {\displaystyle -53^{2}=2809=14^{3}+5*14-5}

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

به همان روش بالا s = 593 − 106 m o d 455839 {\displaystyle s={\frac {593}{-106}}mod455839}