پرش به محتویات

ریشه اولیه

تعریف

در حساب پیمانه‌ای، یک عدد $g$ را «ریشه اولیه به پیمانه n» می‌نامند اگر هر عدد متباین (نسبت به هم اول) با $n$ با توانی از $g$ به پیمانه $n$ همنهشت باشد. به زبان ریاضی، $g$ یک «ریشه اولیه به پیمانه n» است اگر و تنها اگر برای هر عدد صحیح $a$ که $\gcd(a, n) = 1$ باشد، یک عدد صحیح $k$ وجود داشته باشد به طوری که:

$g^k \equiv a \pmod n$.

در این صورت، $k$ «اندیس» یا «لگاریتم گسسته» $a$ در پایه $g$ به پیمانه $n$ نامیده می‌شود. $g$ همچنین «مولد» گروه ضربی اعداد صحیح به پیمانه $n$ نامیده می‌شود.

به طور خاص، در حالتی که $n$ یک عدد اول باشد، توان‌های ریشه اولیه تمام اعداد از $1$ تا $n-1$ را تولید می‌کنند.

وجود

ریشه اولیه به پیمانه $n$ وجود دارد اگر و تنها اگر:

  • $n$ برابر با ۱، ۲، ۴ باشد، یا
  • $n$ توانی از یک عدد اول فرد باشد $(n = p^k)$، یا
  • $n$ دو برابر توانی از یک عدد اول فرد باشد $(n = 2 \cdot p^k)$.

این قضیه توسط گاوس در سال ۱۸۰۱ اثبات شد.

ارتباط با تابع فی اویلر

فرض کنید $g$ یک ریشه اولیه به پیمانه $n$ باشد. آنگاه می‌توان نشان داد که کوچکترین عدد $k$ که در رابطه $g^k \equiv 1 \pmod n$ صدق می‌کند، برابر با $\phi (n)$ است. علاوه بر این، عکس این قضیه نیز درست است، و از این واقعیت در این مقاله برای یافتن ریشه اولیه استفاده خواهیم کرد.

همچنین، تعداد ریشه‌های اولیه به پیمانه $n$، در صورت وجود، برابر با $\phi (\phi (n) )$ است.

الگوریتم یافتن ریشه اولیه

یک الگوریتم ساده این است که تمام اعداد در بازه $[1, n-1]$ را در نظر بگیریم. سپس برای هر کدام بررسی کنیم که آیا ریشه اولیه است یا نه، این کار با محاسبه تمام توان‌های آن و بررسی اینکه آیا همگی متفاوت هستند، انجام می‌شود. این الگوریتم پیچیدگی زمانی $O(g \cdot n)$ دارد که بسیار کند خواهد بود. در این بخش، یک الگوریتم سریع‌تر با استفاده از چند قضیه شناخته‌شده پیشنهاد می‌کنیم.

از بخش قبل می‌دانیم که اگر کوچکترین عدد $k$ که در رابطه $g^k \equiv 1 \pmod n$ صدق می‌کند برابر با $\phi (n)$ باشد، آنگاه $g$ یک ریشه اولیه است. از آنجایی که برای هر عدد $a$ متباین با $n$ از قضیه اویلر می‌دانیم که $a ^ { \phi (n) } \equiv 1 \pmod n$ است، برای بررسی اینکه آیا $g$ ریشه اولیه است یا نه، کافی است بررسی کنیم که برای تمام $d$ های کوچکتر از $\phi (n)$، رابطه $g^d \not \equiv 1 \pmod n$ برقرار باشد. با این حال، این الگوریتم هنوز هم بسیار کند است.

بر اساس قضیه لاگرانژ، می‌دانیم که مرتبه هر عدد به پیمانه $n$ باید مقسوم‌علیهی از $\phi (n)$ باشد. بنابراین، کافی است بررسی کنیم که برای تمام مقسوم‌علیه‌های سره $d \mid \phi (n)$، رابطه $g^d \not \equiv 1 \pmod n$ برقرار باشد. این الگوریتم به مراتب سریع‌تر است، اما هنوز هم می‌توانیم آن را بهبود ببخشیم.

مقدار $\phi (n)$ را به عوامل اول تجزیه می‌کنیم: $\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$. اثبات می‌کنیم که در الگوریتم قبلی، کافی است فقط مقادیر $d$ را در نظر بگیریم که به شکل $\frac { \phi (n) } {p_j}$ هستند. در واقع، فرض کنید $d$ یک مقسوم‌علیه سره دلخواه از $\phi (n)$ باشد. آنگاه، بدیهی است که یک $j$ وجود دارد به طوری که $d \mid \frac { \phi (n) } {p_j}$، یعنی $d \cdot k = \frac { \phi (n) } {p_j}$. با این حال، اگر $g^d \equiv 1 \pmod n$ باشد، خواهیم داشت:

$g ^ { \frac { \phi (n)} {p_j} } \equiv g ^ {d \cdot k} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.

یعنی در میان اعداد به شکل $\frac {\phi (n)} {p_i}$، حداقل یکی وجود خواهد داشت که شرایط را برآورده نمی‌کند.

اکنون یک الگوریتم کامل برای یافتن ریشه اولیه داریم:

  • ابتدا $\phi (n)$ را پیدا کرده و آن را تجزیه می‌کنیم.

  • سپس روی تمام اعداد $g \in [1, n]$ پیمایش می‌کنیم و برای هر عدد، جهت بررسی اینکه آیا ریشه اولیه است یا نه، کارهای زیر را انجام می‌دهیم:

    • تمام مقادیر $g ^ { \frac {\phi (n)} {p_i}} \pmod n$ را محاسبه می‌کنیم.
    • اگر تمام مقادیر محاسبه‌شده مخالف $1$ باشند، آنگاه $g$ یک ریشه اولیه است.

    زمان اجرای این الگوریتم $O(Ans \cdot \log \phi (n) \cdot \log n)$ است (با فرض اینکه $\phi (n)$ دارای $\log \phi (n)$ مقسوم‌علیه است).

شوپ (Shoup) (۱۹۹۰، ۱۹۹۲) با فرض فرضیه ریمان تعمیم‌یافته، ثابت کرد که $g$ از مرتبه $O(\log^6 p)$ است.

پیاده‌سازی

کد زیر فرض می‌کند که پیمانه p یک عدد اول است. برای اینکه کد برای هر مقدار p کار کند، باید محاسبه $\phi (p)$ را به آن اضافه کنیم.

int powmod (int a, int b, int p) {
    int res = 1;
    while (b)
        if (b & 1)
            res = int (res * 1ll * a % p),  --b;
        else
            a = int (a * 1ll * a % p),  b >>= 1;
    return res;
}

int generator (int p) {
    vector<int> fact;
    int phi = p-1,  n = phi;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            fact.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        fact.push_back (n);

    for (int res=2; res<=p; ++res) {
        bool ok = true;
        for (size_t i=0; i<fact.size() && ok; ++i)
            ok &= powmod (res, phi / fact[i], p) != 1;
        if (ok)  return res;
    }
    return -1;
}