عددی ۱۵۵ رقمی که روی کارت‌های گرافیک تجزیه شد

شکستن یک عدد بزرگ به عامل‌های اولش دشوار است و این دشواری برای رمزنگاری اهمیت دارد — به همین دلیل مقاله با دقت توضیح می‌دهد که نتیجه‌اش چه چیزی را تهدید نمی‌کند. اعداد عمومی «چالش RSA» به عنوان محک برای روش‌های تجزیه به کار می‌روند. RSA-155 یکی از آن‌هاست: ۱۵۵ رقم، یا ۵۱۲ بیت.

دو غربال، هر کدام یک رکورد

دو خانواده از الگوریتم‌ها چیره‌اند. غربال میدان اعداد قهرمان اعداد بسیار بزرگ است: RSA-155 را در همان ۱۹۹۹ شکست، و به گفتهٔ مقاله، رکورد کلی اکنون عددی ۲۷۰ رقمی، RSA-896، در سال ۲۰۲۶ است. غربال درجهٔ دوم قدیمی‌تر از نظر مجانبی کندتر است و به تعبیر خود نویسندگان برای رکوردهای کلی «ابزار نادرستی» است. با این حال فهرست رکوردهای خودش را دارد: بزرگ‌ترین عددی که با آن شکسته شد RSA-150 بود، در ژوئن ۲۰۲۵، با صرف ۱۱٬۶۶۴ ساعت-هستهٔ CPU.

غربال درجهٔ دوم به دنبال شمار زیادی عدد کوچک است که روی مجموعه‌ای از اعداد اول کوچک کاملاً تجزیه می‌شوند، سپس با جبر خطی آن‌ها را ترکیب می‌کند تا دو مربع x² و y² به دست آید که به پیمانهٔ N برابرند. آنگاه یک بزرگ‌ترین مقسوم‌علیه مشترک یکی از عامل‌ها را آشکار می‌کند. روی رایانه، این برای پردازنده‌های گرافیکی (GPU) کابوس است: دسترسی‌های حافظه بسیار فراتر از هر حافظهٔ نهانی (cache) پراکنده می‌شوند، آزمون‌ها پر از انشعاب‌اند، و جبر پایانی در حسابی دودویی انجام می‌شود که هیچ کتابخانهٔ سازنده‌ای از آن پشتیبانی نمی‌کند. تلاش‌های پیشین با GPU فقط گام‌های جداگانه را شتاب داده بودند.

همه‌چیز روی کارت گرافیک

فابیان یانوشفسکی و کریستوف هاینریش، از مؤسسهٔ ریاضی دانشگاه پادربورن در آلمان، CUDA-MPQS را ساختند؛ یک غربال درجهٔ دوم متن‌باز که در آن همهٔ مراحل — آماده‌سازی چندجمله‌ای‌ها، غربال کردن، وارسی نامزدها، جفت کردن نتایج جزئی، ساختن ماتریس، حل آن و گرفتن جذر پایانی — روی GPU اجرا می‌شود. پردازندهٔ معمولی فقط هماهنگی، راه‌اندازی و ورودی و خروجی را بر عهده دارد؛ نویسندگان چند گام باقی‌مانده در سمت میزبان (host) را صریحاً فهرست می‌کنند. در آزمونی روی عددی ۱۰۰ رقمی، GPU در ۹۹٫۹٪ زمان غربال مشغول بود و هیچ مکثی برای انتظار پردازنده نداشت.

بزرگ کردن مقیاس خطایی ظریف را آشکار کرد. در اندازهٔ RSA-155، یک شمارندهٔ ۸ بیتی که در غربال به کار می‌رفت درست روی باارزش‌ترین نامزدها سرریز می‌کرد و بی‌صدا ۹۸ تا ۹۹٫۵٪ آن‌ها را دور می‌ریخت. گروه آن را با یک شمارندهٔ اشباع‌شونده جایگزین کرد که اثبات می‌کنند نتایج یکسانی می‌دهد.

RSA-155 در حدود یک روز

در ۱۴ ژوئیهٔ ۲۰۲۶، این زنجیرهٔ پردازش RSA-155 را به دو عدد اول هر کدام ۷۸ رقمی شکست که هم روی GPU و هم روی میزبان وارسی شدند:

• غربال: ۶۴ GPU از نوع NVIDIA H100 در ۱۶ گره، ۱۰٫۸ ساعت، با گردآوری حدود ۱۷٫۳ میلیون رابطه.
• جبر خطی: یک H100 به مدت ۱۰٫۹ ساعت، روی ماتریسی با ۱۶٫۷ میلیون سطر و ۶۸۴ میلیون درایهٔ ناصفر.
• کل: ۷۰۰٫۶ ساعت-GPU و ۲۴۲ کیلووات‌ساعت، تقریباً ۲۴ ساعت از آغاز تا یافتن عامل‌ها. غربال ۹۸٫۴٪ هزینه بود.

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

سریع‌تر از بهترین پردازنده‌ها

روی عددی ۱۰۰ رقمی، یک H100 به‌تنهایی در ۲۹٫۲ ثانیه کار را تمام می‌کند و یک RTX 5070 Ti خانگی در ۵۱ ثانیه. در مقایسه‌ای کنترل‌شده روی همان عدد، با اندازه‌گیری انرژی در هر دو سو، یک H100 ۳٫۶ تا ۴٫۲ برابر سریع‌تر از سریع‌ترین غربال درجهٔ دوم مبتنی بر CPU بود که روی ۹۶ هستهٔ یک پردازندهٔ AMD EPYC اجرا می‌شد، و حدود نُه تا ده برابر سریع‌تر از یک بستهٔ استاندارد دیگر. آن‌ها RSA-150 را نیز در ۳۰۲٫۹ ساعت-GPU دوباره تجزیه کردند، در برابر ۱۱٬۶۶۴ ساعت-هستهٔ رکورد پیشین — نسبتی که نویسندگان تأکید می‌کنند شتابی هم‌سنج نیست.

هیچ تهدیدی برای رمزنگاری

نویسندگان صریح‌اند: RSA-155 پیش‌تر تجزیه شده بود، این یک رکورد کلی تجزیه نیست، و «هیچ‌چیز در اینجا حاشیهٔ امنیتی را تنگ نمی‌کند». کد نیز عمداً به حدود ۱۵۵ رقم محدود شده است. علاقهٔ آن‌ها جای دیگری است: نشان دادن اینکه یک الگوریتم نامنظم و پرانشعاب می‌تواند به‌تمامی روی یک GPU زندگی کند. آن‌ها غربال‌گر مشبکهٔ (lattice siever) GPU را در قلب غربال میدان اعداد هدف طبیعی بعدی می‌دانند — کاری که به گفتهٔ آن‌ها دیگران از آن پس آغاز کرده‌اند و با نسخه‌های GPU یک بستهٔ موجود RSA-260 و RSA-896 را تجزیه کرده‌اند؛ دومی با Claude انجام شد.

تعارض منافع. نویسندگان اعلام می‌کنند که از هوش مصنوعی مولد و ابزارهای کدنویسی عامل‌محور استفاده شده است: مدل‌های Claude از Anthropic (از راه Claude Code) در کنار مدل‌های GPT از OpenAI و Gemini از Google برای توسعهٔ نرم‌افزار، و مدل‌های Claude برای آماده‌سازی داده‌ها و دست‌نوشته. آن‌ها می‌گویند همهٔ خروجی‌های هوش مصنوعی به‌صورت دستی بازبینی و راستی‌آزمایی شده‌اند. این نوشته را نیز Claude نوشته است.