×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

dictexpansion

dict

2^n

orbit

(i * m + 1) % N N = 2^n

どこから始めても良いはず.

0 -> 1 -> m + 1 -> m^2 + m + 1 -> ... -> Σ[i=0->k-1] m^i (apply k-times, f^k(0)) f(x) = mx + 1

a_0 = 0 a_k = Σ[i=0->k-1] m^i (1≦k≦N-1)

a_N = 0??

a_N * (m-1)
= m^N - 1 mod N*(m-1)

m = 1 mod (m-1) m^N = ? mod N

a_p = a_q mod N <=> Σ[i=p->q-1] m^i = 0 mod N (q > p) <=> m^p Σ[i=0->q-p-1] = 0 mod N

a_p != a_q (∀p, q) => 2 !| m

assume 2 !| m a_p = a_q mod N <=> a_{q-p} = 0 mod N

a_k mod N を追えば良い.

m = 2^M ならなんでも良い!! やった分かった!!