ماشین‌حساب تجزیه فرما

درباره این ابزار

روش تجزیهٔ فرما از این واقعیت بهره می‌برد که هر عدد صحیح فرد N را می‌توان به‌صورت تفاضل دو مربع نوشت، N = a² − b² = (a−b)(a+b). الگوریتم از a = ⌈√N⌉ شروع می‌کند و در هر گام a را ۱ واحد زیاد می‌کند و بررسی می‌کند که آیا a² − N خودش مربع کامل (b²) است یا نه؛ همین که چنین شد، N بی‌درنگ به (a−b)(a+b) تجزیه می‌شود. این ماشین‌حساب آن حلقه را اجرا می‌کند و هر گامی را که برای یافتن عوامل برداشته شده نشان می‌دهد.

وقتی دو عامل N به هم نزدیک باشند، این روش در گام‌های بسیار کمی همگرا می‌شود — و بزرگ‌ترین ضعفش مهم‌ترین کاربرد واقعی‌اش هم هست: دانشجویان رمزنگاری و پژوهشگران امنیت از تجزیهٔ فرما نشان می‌دهند که چرا پیمانه‌های RSA باید از اعداد اولی ساخته شوند که از هم دور باشند، چون اعداد اولی که بیش از حد نزدیک انتخاب شوند پیمانه را به‌سادگی قابل شکستن می‌کنند. این روش همچنین تمرینی استاندارد در درس‌های نظریهٔ اعداد برای نشان دادن استدلال تفاضل مربع‌هاست.