غربال عمومی میدان اعداد

در نظریه اعداد ، غربال عمومی میدان اعداد (GNFS) کارآمدترین الگوریتم کلاسیک شناخته شده برای تجزیه اعداد صحیح بزرگتر از [[گوگول|الگو:ریاضی]] است. از نظر رهیافت آنی (اکتشافی) ، پیچیدگی آن برای تجزیه یک عدد صحیح الگو:Mvar (شامل الگو:ریاضی بیت) به شکل زیر است

$\begin{array}{cc}& \exp \left(((64/9{)}^{1/3}+o(1)){(\log n)}^{1/3}{(\log \log n)}^{2/3}\right)\\ =& L_n[1/3,(64/9{)}^{1/3}]\end{array}$

در نمادهای O و L . این یک تعمیم از غربال خاص میدان اعداد است: در حالی که دومی فقط می تواند اعداد یک شکل از اعداد خاص را تجزیه کند، غربال عمومی میدان اعداد می تواند هر عددی را به غیر از نماهای اول (که با گرفتن ریشه به راحتی تجزیه می‌شوند) تجزیه کند.

در اصل غربال میدان اعداد (شامل خاص و عمومی) را می توان به عنوان بهبودی برای غربال ساده تر منطقی یا غربال درجه دوم شناخت و درک کرد. هنگام استفاده از چنین الگوریتم‌هایی برای تجزیه کردن یک عدد بزرگ الگو:Mvar، لازم است اعداد نرم (یعنی اعدادی با فاکتورهای اول کوچک) با مرتبه الگو:ریاضی را پیدا کرد. اندازه این مقادیر به صورت نمایی در اندازه الگو:Mvar است (به زیر مراجعه کنید). از سوی دیگر، غربال عمومی میدان اعداد، موفق به جستجوی اعداد نرمی می شود که به اندازه الگو:Mvar زیر نمایی هستند. از آنجایی که این اعداد کوچکتر هستند، به احتمال زیاد نسبت به اعداد بررسی شده در الگوریتم های قبلی نرم هستند. این کلید کارایی غربال میدان عددی است. برای دستیابی به این افزایش سرعت، غربال میدان عددی باید محاسبات و فاکتورسازی را در میدانهای جبری اعداد انجام دهد. این منجر به بسیاری از جنبه های پیچیده الگوریتم در مقایسه با غربال ساده تر منطقی می شود.

اندازه ورودی الگوریتم الگو:ریاضی است یا به عبارت دیگر تعداد بیت ها در نمایش دودویی (باینری) الگو:Mvar است. هر عنصری از الگو:ریاضی برای ثابت الگو:Mvar در الگو:ریاضی نمایی است. زمان اجرای غربال میدان عددی فوق چند جمله ای است اما در اندازه ورودی زیر نمایی است .

میدان های اعداد

فرض کنید الگو:Mvar یک چند جمله‌ای از درجه الگو:Mvar روی $\mathbb{Q}$ (اعداد گویا) است، و الگو:Mvar یک ریشه مختلط از الگو:Mvar باشد. سپس، الگو:ریاضی است که می‌توان آن را به گونه‌ای مرتب کرد که الگو:ریاضی را به عنوان ترکیبی خطی از توان‌های r کمتر از k بیان کند. این معادله می‌تواند برای حذف هر توان r با توان e ≥ k استفاده شود. به عنوان مثال، اگر الگو:ریاضی و الگو:Mvar واحد موهومی الگو:Mvar باشد، آنگاه الگو:ریاضی است یا الگو:ریاضی . این به ما امکان می‌دهد ضرب مختلط را به صورت زیر تعریف کنیم:

$\begin{array}{cc}(a+bi)(c+di)& =ac+(ad+bc)i+(bd)i^2\\ & =(ac-bd)+(ad+bc)i.\end{array}$

به طور کلی، این به طور مستقیم به میدان جبری اعداد $\mathbb{Q}[r]$ منتهی می شود، که می‌توان آن را به عنوان مجموعه‌ای از اعداد مختلط به صورت زیر تعریف کرد:

$a_{k-1}{r}^{k-1}+\cdots +a_1{r}^1+a_0{r}^0,\text{ where }{a}_0,\dots ,a_{k-1}\in \mathbb{Q}.$

حاصلضرب هر دو مقدار از این نوع را می‌توان با گرفتن حاصلضرب چندجمله‌ای‌ها محاسبه کرد، سپس هر توان r با توان e ≥ k را همانطور که در بالا توضیح داده شد، کاهش داد و مقداری به همان شکل به دست آورد. برای اطمینان از اینکه این میدان در واقع الگو:Mvar بعدی است و به یک میدان کوچکتر تبدیل نمی‌شود، کافی است که الگو:Mvar یک چند جمله‌ای تجزیه‌ناپذیر روی اعداد گویا باشد. به طور مشابه، می توان حلقه اعداد صحیح ${𝕆}_{\mathbb{Q}[r]}$ را به عنوان زیر مجموعه از $\mathbb{Q}[r]$ تعریف کرد که ریشه های چندجمله ای مونیک (یکسان) با ضرایب صحیح هستند. در برخی موارد، این حلقه اعداد صحیح معادل حلقه $\mathbb{Z}[r]$ است. با این حال، موارد خاص زیادی وجود دارد.

روش

دو چند جمله‌ای f(x) و g(x) با درجات کوچک d و e انتخاب می‌شوند که ضرایب صحیح دارند و روی اعداد گویا تجزیه‌ناپذیر هستند و وقتی به پیمانه n تفسیر می‌شوند، یک ریشه صحیح مشترک m دارند. یک استراتژی بهینه برای انتخاب این چند جمله ای ها وجود ندارد. یک روش ساده این است که درجه d را برای یک چند جمله ای انتخاب کنیم، بسط n را در مبنای m (اعداد مجاز مابین -m و m) برای تعدادی از m مختلف از مرتبه n ^{1/ d} در نظر بگیریم و f(x) را به عنوان چندجمله‌ای با کوچکترین ضرایب و g(x) را به عنوان x - m انتخاب کنیم.

حلقه‌های میدان اعداد Z[r₁] و Z[r₂] را در نظر بگیرید، جایی که r₁ و r₂ ریشه‌های چندجمله‌ای‌های f و g هستند. از آنجا که f از درجه d با ضرایب صحیح است، اگر a و b اعداد صحیح باشند، b^d · f(a/b) نیز چنین خواهد بود که آن را r می‌نامیم. به طور مشابه، s = b^e · g(a/b) یک عدد صحیح است. هدف یافتن مقادیر صحیح a و b است که به طور همزمان r و s را نسبت به پایه انتخابی اعداد اول، نرم کنند. اگر a و b کوچک باشند، r و s نیز کوچک خواهند بود، تقریباً به اندازه m، و ما شانس بیشتری برای نرم بودن آنها به طور همزمان داریم. بهترین روش شناخته شده فعلی برای این جستجو، غربالگری شبکه است. برای به دست آوردن بازده قابل قبول، لازم است که از یک پایه عامل بزرگ استفاده شود.

با داشتن چنین جفت‌های به تعداد کافی، با استفاده از حذف گاوسی، می‌توانیم حاصلضرب‌های r و s مربوطه را به طور همزمان مربع کنیم. یک شرط کمی قوی‌تر لازم است - که آنها اعداد نرم مربع‌ در میدان‌های اعداد ما باشند، اما این شرط را نیز می‌توان با این روش به دست آورد. هر عدد r نرم به نوعی a − r₁b است و از این رو حاصلضرب عوامل مربوطه a − r₁b یک مربع در Z[r₁] است، با یک "ریشه مربع" که می‌توان آن را تعیین کرد (به عنوان حاصلضرب عوامل شناخته شده در [r₁]Z) - معمولاً به عنوان یک عدد جبری غیرمنطقی نشان داده می‌شود. به طور مشابه، حاصلضرب عوامل a − r₂b یک مربع در Z[r₂] است، با یک "ریشه مربع" که آن نیز قابل محاسبه است. لازم به ذکر است که استفاده از حذف گاوسی زمان اجرای بهینه الگوریتم را بدست نمی‌دهد. در عوض، الگوریتم‌های حل ماتریس پراکنده مانند Block Lanczos یا Block Wiedemann استفاده می‌شوند.

از آنجا که m ریشه هر دو f و g به پیمانه n است، هم‌ریختی‌هایی از حلقه‌های ℤ[r₁] و ℤ[r₂] به حلقه ℤ/nℤ (اعداد صحیح به پیمانه n) وجود دارد که r₁ و r₂ را به m نگاشت می‌کنند، و این هم‌ریختی‌ها هر "ریشه مربع" (که معمولاً به عنوان یک عدد گویا نشان داده نمی‌شود) را به نماینده صحیح آن نگاشت می‌کنند. اکنون حاصلضرب عوامل a − mb به پیمانه n را می‌توان به دو روش - یکی برای هر حلقه همریخت و یکی به عنوان یک مربع به دست آورد. بنابراین، می‌توان دو عدد x و y را یافت، به طوری که x² − y² بر n بخش‌پذیر باشد و دوباره با احتمال حداقل نصف، با یافتن بزرگترین مقسوم علیه مشترک n و x − y، یک عامل از n را به دست می‌آوریم.

بهبود انتخاب چندجمله‌ای

انتخاب چندجمله‌ای می‌تواند به طور چشمگیری بر زمان تکمیل بقیه الگوریتم تأثیر بگذارد. روش انتخاب چندجمله‌ای‌ها بر اساس بسط n در مبنای m که در بالا نشان داده شد، در بسیاری از موقعیت‌های عملی بهینه نیست و منجر به توسعه روش‌های بهتر شده است.

یکی از این روش‌ها توسط مورفی و برنت پیشنهاد شد. آنها یک امتیاز دو بخشی برای چندجمله‌ای‌ها معرفی می‌کنند که بر اساس وجود ریشه‌ها به پیمانه اعداد اول کوچک و همینطور این پیمانه ها میانگین مقداری که چندجمله‌ای روی ناحیه غربالگری قرار می‌گیرد، است.

بهترین نتایج گزارش شده با روش Thorsten Kleinjung به دست آمد، که اجازه می‌دهد g(x) = ax + b باشد و روی a متشکل از عوامل اول کوچک همنهشت با ۱ به پیمانه 2d و روی ضرایب پیشرو f که بر ۶۰ بخش‌پذیرند، جستجو می‌کند.

پیاده‌سازی‌ها

برخی از پیاده‌سازی‌ها بر روی یک کلاس کوچکتر معین از اعداد تمرکز می‌کنند. اینها به عنوان تکنیک‌های غربال خاص میدان اعداد شناخته می‌شوند، مانند آنچه در پروژه Cunningham استفاده می‌شود. پروژه‌ای به نام NFSNET از سال ۲۰۰۲ تا حداقل سال ۲۰۰۷ اجرا می‌شد. این پروژه از محاسبات توزیع‌شده داوطلبانه در اینترنت استفاده می‌کرد. پل لیلاند از بریتانیا و ریچارد واکربارث از تگزاس در آن دخیل بودند.

تا سال ۲۰۰۷، پیاده‌سازی استاندارد طلایی مجموعه‌ای از نرم‌افزار بود که توسط CWI در هلند توسعه و توزیع شده بود و فقط تحت یک مجوز نسبتاً محدود در دسترس بود. در سال ۲۰۰۷، Jason Papadopoulos یک پیاده‌سازی سریعتر از پردازش نهایی را به عنوان بخشی از msieve توسعه داد که در مالکیت عمومی است. هر دو پیاده‌سازی قابلیت توزیع بین چندین گره در یک خوشه با یک اتصال سریع کافی را دارند.

انتخاب چندجمله‌ای معمولاً توسط نرم‌افزار GPL نوشته شده توسط Kleinjung یا توسط msieve انجام می‌شود، و غربالگری شبکه توسط نرم‌افزار GPL نوشته شده توسط Franke و Kleinjung. این موارد در GGNFS توزیع می‌شوند.

• NFS@Home
• GGNFS
• فاکتور توسط gnfs
• CADO-NFS
• msieve (که شامل کد پردازش نهایی، انتخاب چند جمله ای بهینه سازی شده برای اعداد کوچکتر و اجرای خط غربال)
• kmGNFS

همچنین ببینید

• غربال خاص میدان اعداد

منابع

• متیو ای. بریگز: مقدمه ای بر غربال اعداد عمومی، 1998