خانه ویکی

بررسی اول بودن یک عدد

می دانیم عدد اول عددی است که به جز خودش و یک مقسوم علیه دیگری ندارد و عدد مرکب عددی است که حداقل یک مقسوم علیه دیگر علاوه بر خودش و یک داشته باشد . فرض می کنیم این مقسوم علیه $d$ است . معمولا $n/d$ هم مقسوم علیه دیگری از $n$ است و این واضح است که یا $\frac{n}{d} \le \sqrt n$ است یا $d \le \sqrt n$ است و ما می توانیم از این نتیجه برای چک کردن اول بودن یک عدد استفاده کنیم.برای همین ما چک می کنیم که $x$ بر اعداد بین $2$ تا $ \sqrt n$ بخش پذیر است یا نه . اگر بخش پذیر بود پس $x$ اول نیست .

bool isPrime(int x) 
{
    for (int d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
            return false;
    }
    return true;
}

این یک راه ساده برای چک کردن اول بودن است و می توان آن را کمی بهینه تر کرد . مثلا فقط می توان اعداد فرد را چک کرد چون تنها عددد اول زوج ۲ است . می توانید بهینه سازی های دیگری را هم در [تجزیه اعداد] بخونید.

بررسی اول بودن یک عدد با استفاده از قضیه فرما

توجه داشته باشید که این راه یک راه احتمالی است طبق قضیه فرمای کوچک به ازای عدد اول $p$ و عدد $a$ که نسبت به هم اول هستند داریم : $a^{p-1} \equiv 1 \mod p$ و اغلب برای اعداد مرکب درست نیست و ما با استفاده از این می توانیم اول بودن $p$ را چک کنیم . برای همین یک عدد مانند $a$ از بازه $[2 , p - 2]$ انتخاب می کنیم و چک میکنیم که معادله بالا درست است یا نه . اگر درست نبود یعنی $a^{p-1} \not\equiv 1 \mod p$ متوجه می شویم که $p$ نمی تواند اول باشد. ولی ممکن است که این معادله برای یک عدد مرکب هم درست باشد . بنابراین اگر معادله برقرار بود نمی توانیم بگوییم که عدد اول است یا نه ولی احتمال می دهیم که باشد . توجه کنید که اگر تمام اعداد ممکن $a$ را در بازه بالا چک کنیم می تونیم ثابت کنیم که عدد اول هست یا نه ولی اینکه بخواهیم تمام $a$های ممکن رو چک کنیم برای $p$های بزرگ کار خوبی نیست و روش اول منطقی تر و بهتر است . بنابراین تعداد $a$ رندوم انتخاب می کنیم . اگر معادله به ازای تمام $a$های رندوم درست بود به احتمال خوبی عدد $p$ اول است.

bool probablyPrimeFermat(int n, int iter=5) 
{
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) 
    {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

برای اینکه سریعتر $a^{p-1}$ را محاسبه کنیم می توانیم از الگوریتم توان رسایی دودوییاستفاده کنیم که در $Order(log(p-1))$ اجرا می شود. اما با وجود چک کردن چند $a$ هم مشکلی وجود دارد:)) اعداد مرکبی هستند که $a^{n-1} \equiv 1 \mod n$ به ازای تمام $a$هایی که نسبت به $n$ اول هستند برفرار است . برای مثال عدد $561 = 3.11.17$ به چنین عددی کارمایکل می گویند و این روش درصورتی می تواند این عدد را تشخیص دهد که مرکب است که $a$ایی انتخاب شود که $gcd(a , n) != 1$ باشد . با این وجود این روش همچنان استفاده می شود چون سریع است و اعداد کارمایکل بسیار نادر هستند به طوری که تنها $646$ عدد کارمایکل تا $10^{9}$ داریم .

مسائل تمرینی