موضوع مقاله: غربال عمومی میدان اعداد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # غربال عمومی میدان اعداد | مقدمه: در نظریه اعداد ، غربال عمومی میدان اعداد (GNFS) کارآمدترین الگوریتم کلاسیک شناخته شده برای تجزیه اعداد صحیح بزرگتر از است. | ## بخش 1: غربال عمومی میدان اعداد | از نظر رهیافت آنی (اکتشافی) ، پیچیدگی آن برای تجزیه یک عدد صحیح (شامل بیت) به شکل زیر است در نمادهای O و L . این یک تعمیم از غربال خاص میدان اعداد است: در حالی که دومی فقط می تواند اعداد یک شکل از اعداد خاص را تجزیه کند، غربال عمومی میدان اعداد می تواند هر عددی را به غیر از نماهای اول (که با گرفتن ریشه به راحتی تجزیه می‌شوند) تجزیه کند. در اصل غربال میدان اعداد (شامل خاص و عمومی) را می توان به عنوان بهبودی برای غربال ساده تر منطقی یا غربال درجه دوم شناخت و درک کرد. هنگام استفاده از چنین الگوریتم‌هایی برای تجزیه کردن یک عدد بزرگ ، لازم است اعداد صاف (یعنی اعدادی با فاکتورهای اول کوچک) با مرتبه را پیدا کرد. از سوی دیگر، غربال عمومی میدان اعداد، موفق به جستجوی اعداد صافی می شود که به اندازه زیر نمایی هستند. از آنجایی که این اعداد کوچکتر هستند، به احتمال زیاد نسبت به اعداد بررسی شده در الگوریتم های قبلی صاف هستند. برای دستیابی به این افزایش سرعت، غربال میدان عددی باید محاسبات و فاکتورسازی را در میدانهای جبری اعداد انجام دهد. این منجر به بسیاری از جنبه های پیچیده الگوریتم در مقایسه با غربال ساده تر منطقی می شود. اندازه ورودی الگوریتم است یا به عبارت دیگر تعداد بیت ها در نمایش دودویی (باینری) است. زمان اجرای غربال میدان عددی فوق چند جمله ای است اما در اندازه ورودی زیر نمایی است . میدان های اعداد فرض کنید یک چند جمله‌ای از درجه روی (اعداد گویا) است، و یک ریشه مختلط از باشد. سپس، است که می‌توان آن را به گونه‌ای مرتب کرد که را به عنوان ترکیبی خطی از توان‌های r کمتر از k بیان کند. | ## بخش 2: غربال عمومی میدان اعداد | این به ما امکان می‌دهد ضرب مختلط را به صورت زیر تعریف کنیم: به طور کلی، این به طور مستقیم به میدان جبری اعداد منتهی می شود، که می‌توان آن را به عنوان مجموعه‌ای از اعداد مختلط به صورت زیر تعریف کرد: حاصلضرب هر دو مقدار از این نوع را می‌توان با گرفتن حاصلضرب چندجمله‌ای‌ها محاسبه کرد، سپس هر توان r با توان e ≥ k را همانطور که در بالا توضیح داده شد، کاهش داد و مقداری به همان شکل به دست آورد. برای اطمینان از اینکه این میدان در واقع بعدی است و به یک میدان کوچکتر تبدیل نمی‌شود، کافی است که یک چند جمله‌ای تجزیه‌ناپذیر روی اعداد گویا باشد. به طور مشابه، می توان حلقه اعداد صحیح را به عنوان زیر مجموعه از تعریف کرد که ریشه های چندجمله ای مونیک (یکسان) با ضرایب صحیح هستند. روش دو چند جمله‌ای 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 هستند. هدف یافتن مقادیر صحیح a و b است که به طور همزمان r و s را نسبت به پایه انتخابی اعداد اول، صاف کنند. اگر a و b کوچک باشند، r و s نیز کوچک خواهند بود، تقریباً به اندازه m، و ما شانس بیشتری برای صاف بودن آنها به طور همزمان داریم. برای به دست آوردن بازده قابل قبول، لازم است که از یک پایه عامل بزرگ استفاده شود. با داشتن چنین جفت‌های به تعداد کافی، با استفاده از حذف گاوسی، می‌توانیم حاصلضرب‌های r و s مربوطه را به طور همزمان مربع کنیم. یک شرط کمی قوی‌تر لازم است - که آنها اعداد صاف مربع‌ در میدان‌های اعداد ما باشند، اما این شرط را نیز می‌توان با این روش به دست آورد. هر عدد r صاف به نوعی a − r₁b است و از این رو حاصلضرب عوامل مربوطه a − r₁b یک مربع در Z[r₁] است، با یک "ریشه مربع" که می‌توان آن را تعیین کرد (به عنوان حاصلضرب عوامل شناخته شده در [r₁]Z) - معمولاً به عنوان یک عدد جبری غیرمنطقی نشان داده می‌شود. | ## بخش 3: غربال عمومی میدان اعداد | به طور مشابه، حاصلضرب عوامل a − r₂b یک مربع در Z[r₂] است، با یک "ریشه مربع" که آن نیز قابل محاسبه است. لازم به ذکر است که استفاده از حذف گاوسی زمان اجرای بهینه الگوریتم را بدست نمی‌دهد. از آنجا که 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 که در بالا نشان داده شد، در بسیاری از موقعیت‌های عملی بهینه نیست و منجر به توسعه روش‌های بهتر شده است. آنها یک امتیاز دو بخشی برای چندجمله‌ای‌ها معرفی می‌کنند که بر اساس وجود ریشه‌ها به پیمانه اعداد اول کوچک و همینطور این پیمانه ها میانگین مقداری که چندجمله‌ای روی ناحیه غربالگری قرار می‌گیرد، است. پیاده‌سازی‌ها برخی از پیاده‌سازی‌ها بر روی یک کلاس کوچکتر معین از اعداد تمرکز می‌کنند. تا سال ۲۰۰۷، پیاده‌سازی استاندارد طلایی مجموعه‌ای از نرم‌افزار بود که توسط CWI در هلند توسعه و توزیع شده بود و فقط تحت یک مجوز نسبتاً محدود در دسترس بود. | ## جمع‌بندی | هر دو پیاده‌سازی قابلیت توزیع بین چندین گره در یک خوشه با یک اتصال سریع کافی را دارند.