2019-03-15

AOJ 2720 Identity Function (JAG 夏合宿 2015 day4-D) (4D, 600 点)

AOJ JAG AOJ-ICPC450点数学(整数問題) 素因数分解位数の法則 Fermatの小定理けんちょん自作問題互いに素 AtCoder 離散対数 Giant-Step Baby-Step法競技数学色強め指数の指数 JAG夏合宿 AOJ-ICPC NoviSteps4D 原始根

この問題の原案やってました！高校の頃、時刻表同好会の友達から

「f(n) = n¹⁵ を 15 で割った余りとすると任意の整数 n に対して f(f(n)) = n になるんだけど、これって暗号の危機じゃない？」

というメールを受け取って、あれこれ考えたことがキッカケになって生えた。

問題へのリンク

問題概要

$1$ より大きな整数 $N$ が与えられる。これを用いて以下のような関数 $f, F_1, F_2, \dots$ を定義する:

$f(a) = a^{N} ({\rm mod}. N)$
$F_1(a) = f(a)$
$F_{k+1}(a) = F_{k}(f(a))$ ( $k=1,2,3,\dots$ )

$0$ 以上 $N$ 未満の任意の自然数 $a$ に対して $F_{k}(a) = a$ となるような最小の正の整数 $k$ を求めよ。そのようなものが存在しない場合には $-1$ を出力せよ。

制約

$2 \le N \le 10^{9}$

解法

とりあえず条件式は

$a^{N^{k}} ≡ a ({\rm mod}. N)$

と整理できる。 $k = 1$ のときは

$a^{N} ≡ a ({\rm mod}. N)$

となり、これは Fermat の小定理でもお馴染みの式になっている！！！
つまり、とりあえず $N$ が素数のときは $k = 1$ で成立することとなる。

そして少し有名なこととして、この式が逆に「素数判定に使えないか？」という問題意識がある。つまり Fermat の小定理の逆が成り立つのではないかと？？？ところがこれには反例があって、例えば任意の整数 $a$ に対して

$a^{1729} ≡ a ({\rm mod}. 1729)$

が成立している (余談だけど、 $1729$ と言えば有名なタクシー数でもある)。

さて、背景となる物語はそんな感じで色々あるのだけど、この問題自体はそういったことが知らなくても自然に解くことができる。まず ${\rm mod}. N$ についての式を見たときに直ちに考えたいこととして

$N$ を素因数分解して、各素因子ごとに考える

というのがある。

素因数分解してみる

$N = p_{1}^{e_1} p_2^{e_2} \dots p_m^{e_m}$ と素因数分解したとき、問題の条件は

$a^{N^{k}} ≡ a ({\rm mod}. p_1^{e_1})$ (が任意の $a$ で成立すること)
$a^{N^{k}} ≡ a ({\rm mod}. p_2^{e_2})$ (が任意の $a$ で成立すること)
...
$a^{N^{k}} ≡ a ({\rm mod}. p_m^{e_m})$ (が任意の $a$ で成立すること)

がすべて成り立つことと同値になる。mod のところが素数べきになって少し見やすくなる。さらに、少し考えてみると

$e_1 = e_2 = \dots = e_m = 1$

でなければならないことがわかる。例えば、 $N = 45 = 3^{2} × 5$ のとき、 $a = 3$ とすると

$3^{45^{k}}$ は $9$ の倍数
$3$ は $9$ で割り切れない

という風になっていてこれらを $9$ で割ったあまりは一致しない。 $3^{N^{k}}$ の方は $3$ で 2 回以上割れるのに、 $3$ は $3$ で一回しか割れない、という状態になっている。なので、 $3^{N^{k}}$ と $3$ を $9$ で割った余りは異なる。これは $3^{N^{k}}$ と $3$ を $N = 45$ で割った余りも異なることを意味する。

より一般に、 $N$ が $p^{2}$ の倍数であるとする。 $p^{N^{k}}$ は $p$ で 2 回以上割れるのに、 $p$ は $p$ で一回しか割れない。よって、 $p^{N^{k}}$ と $p$ を $p^{2}$ で割った余りは異なる。従って $N$ が $p^{2}$ の倍数であるとき、 $p^{N^{k}}$ と $p$ を $N$ で割った余りも異なる。

以上から、 $N = p_1 p_2 \dots p_m$ の形のみ考えれば良い (それ以外は -1) ことが示された。

よって問題の条件は

$a^{N^{k}} ≡ a ({\rm mod}. p_1)$ (が任意の $a$ で成立すること)
$a^{N^{k}} ≡ a ({\rm mod}. p_2)$ (が任意の $a$ で成立すること)
...
$a^{N^{k}} ≡ a ({\rm mod}. p_m)$ (が任意の $a$ で成立すること)

と同値になって大変見やすくなった！！！

次に素数 $p$ をとったとき、任意の整数 $a$ に対して

$a^{N^{k}} ≡ a ({\rm mod}. p)$

が成立する条件について考察する。

法が素数 p の場合の考察

ここで以下の「位数の法則」を使う (この問題でも出て来た)。証明はリンク先にて。

素数 $p$ とある整数 $a$ に対して

$a^{b} ≡ 1 ({\rm mod}. p)$

が成立する最小の整数 $b$ を $a$ の位数と呼ぶ。このとき、

$a^{c} ≡ 1 ({\rm mod}. p)$

が成立しているならば、 $c$ は $b$ の倍数である。

ここで特に、 $a$ として ${\rm mod}. p$ での原始根 $r$ をとると、原始根の位数は $p-1$ であるから、

$r^{N^{k}} ≡ r ({\rm mod}. p)$ $⇔ N^{k} - 1$ が $p-1$ の倍数である

となることがわかる。逆に $N^{k} - 1$ が $p-1$ の倍数であるならば、Fermat の小定理より、任意の整数 $a$ について

$a^{N^{k}} ≡ a ({\rm mod}. p)$

が成立する。以上より、

$p$ を素数として、任意の整数 $a$ に対して

$a^{N^{k}} ≡ a ({\rm mod}. p)$

が成立する必要十分条件は、 $N^{k} - 1$ が $p-1$ の倍数であること

が導かれた。

まとめ

以上の考察から、 $N = p_1 p_2 \dots p_m$ の場合も同様で、問題の条件は

$N^{k} - 1$ が $p_1 - 1$ の倍数
$N^{k} - 1$ が $p_2 - 1$ の倍数
...
$N^{k} - 1$ が $p_m - 1$ の倍数

がすべて成立することと同値であることがわかる。つまり、 $p_1-1, p_2-1, \dots, p_m-1$ の最小公倍数を $L$ として、

$N^{k} - 1$ が $L$ の倍数

であることと同値である。よって

$N^{k} ≡ 1 ({\rm mod}. L)$

を満たす最小の $k$ を求める問題に帰着された。これは離散対数を用いて求めることができる。

存在しない場合もあることに注意が必要である。これを満たす $k$ が存在する必要十分条件は $N$ と $L$ が互いに素であることである。

もうちょっと

離散対数でも通るのだが、離散対数を持っていなくても通すことができる。 $N^{k} ≡ 1 ({\rm mod}. L)$ を満たす最小の $k$ とはすなわち、 ${\rm mod}. L$ における $N$ の位数である。しかるに Euler の定理から、 $N$ と $L$ とが互いに素であるとき、

$N^{\phi(L)} ≡ 1 ({\rm mod}. L)$

が成立することに留意すると、位数の法則から

$k$ は $\phi(L)$ の約数

であることが従う。 $\phi(L)$ の約数をすべて試すことで答えが求められる。

そしてさらに、RUPC 2019 day2-L でやったような高速化を施すことで、高々 $O(\log(\phi(L))$ ) 個の候補を調べればよいこともわかる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

// 位数計算
int calc_order(long long N, long long L) {
    auto pf = prime_factorize(L);
    long long euler = L;
    for (auto pa : pf) {
        int p = pa.first;
        euler /= p, euler *= p-1;
    }
    
    long long res = euler;
    auto pfeuler = prime_factorize(euler);
    for (auto pa : pfeuler) {
        int p = pa.first;
        while (res % p == 0 && modpow(N, res/p, L) == 1) res /= p;
    }
    return res;
}

long long solve(long long N) {
    auto pf = prime_factorize(N);
    
    bool ok = true;
    long long L = 1;
    for (auto p : pf) {
        if (p.second > 1) ok = false;
        long long g = GCD(L, p.first - 1);
        L = L / g * (p.first - 1);
    }
    if (!ok) return -1;
    if (GCD(N, L) > 1) return -1;
    if (L == 1) return 1; // 例外処理

    // mod L での N の位数を求める
    return calc_order(N, L);
}

int main() {
    long long N; cin >> N;
    cout << solve(N) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2720 Identity Function (JAG 夏合宿 2015 day4-D) (4D, 600 点)

問題概要

制約

解法

素因数分解してみる

法が素数 p の場合の考察

まとめ

もうちょっと