āĻāύā§āĻāĻŋāĻāĻžāϰ āĻĢā§āϝāĻžāĻā§āĻā§āϰāĻžāĻāĻā§āĻļāύ āĻĒāϰā§āĻŦ ā§Ļ
āĻāϤ āĻĒāϰā§āĻŦā§ āĻāĻŽāϰāĻž āĻāĻžā§ā§āϰ āĻā§āϰ⧠āĻāĻŋāĻā§ āϏāĻāĻā§āϝāĻžāϰ āĻā§āĻĒāĻžāĻĻāĻ āĻŦā§āϰ āĻāϰāĻžāϰ āĻā§āώā§āĻāĻž āĻāϰā§āĻāĻŋāϞāĻžāĻŽāĨ¤ āĻĻā§āĻāĻāĻāύāĻāĻāĻžāĻŦā§ āĻāĻŽāĻžāĻĻā§āϰ āĻŦāĻžāĻā§āĻāĻž āĻĒā§āϰā§āĻā§āϰāĻžāĻŽāĻāĻŋ \(20\) āĻĄāĻŋāĻāĻŋāĻā§āϰ āĻāĻāĻāĻŋ āϏāĻāĻā§āϝāĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āϞā§āώāĻŖ āĻāϰāϤ⧠āĻāĻŋā§ā§ āĻā§āϞāĻžāύā§āϤ āĻšā§ā§ āĻāĻŋā§ā§āĻāĻŋāϞāĨ¤ \(50\) āĻŦāĻž \(100\) āĻĄāĻŋāĻāĻŋāĻā§āϰ āĻā§āύ āϏāĻāĻā§āϝāĻžāĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āϞā§āώāĻŖ āĻāϰāϤ⧠āĻšāϞ⧠āϏā§āĻ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽā§āϰ āĻā§ āĻ
āĻŦāϏā§āĻĨāĻž āĻšāĻŦā§ āĻāĻžāĻŦ āĻāĻāĻŦāĻžāϰ!
āĻŽāĻžāύā§āώ āϝāĻāύ āĻĻā§āĻāϞ āĻŦā§ āĻŦā§ āϏāĻāĻā§āϝāĻžāϰ āĻāύā§āϝ \(2\) āĻĨā§āĻā§ \(N-1\) [āĻāĻŋāĻāĻŦāĻž \(\sqrt N\)] āĻĒāϰā§āϝāύā§āϤ āϏāĻŦ āϏāĻāĻā§āϝāĻž āĻĻāĻŋā§ā§ \(N\)-āĻā§ āĻāĻŽāύ āĻāĻžāĻ āĻāϰāĻž āĻ
āύā§āĻ āϏāĻŽā§āϏāĻžāĻĒā§āĻā§āώ, āϤāĻāύ āϤāĻžāϰāĻž āĻā§āϰāĻŋāĻ āĻā§āĻāĻāϤ⧠āϞāĻžāĻāϞ āĻā§ āĻāϰ⧠āĻāϰāĻ āĻāĻŽ āϏāĻāĻā§āϝāĻ āϏāĻāĻā§āϝāĻž āĻĻāĻŋā§ā§ āĻāĻžāĻ āĻāϰ⧠\(N\)-āĻāϰ āĻā§āĻĒāĻžāĻĻāĻ āĻŦā§āϰ āĻāϰāĻž āϝāĻžā§āĨ¤ āĻāĻŽāύ āĻ
āύā§āĻāĻā§āϞ⧠āĻā§āϰāĻŋāĻ āϰā§ā§āĻā§, āϝāĻžāϰ āĻŽāĻžāĻā§ āĻāĻāĻāĻŋ āĻšāϞ āĻāύā§āĻŽāĻĻāĻŋāύ āϏāĻŽāϏā§āϝāĻž(āĻĒāϰāĻŋāĻļāĻŋāώā§āĻā§ āĻĻā§āĻ)āĨ¤ āĻāĻā§ āĻāĻžāĻā§ āϞāĻžāĻāĻŋā§ā§ āĻāύā§āĻŽ āĻšā§ā§āĻā§ āĻāĻāĻāĻŋ āĻāĻžāϞāĻžāĻāĻāϤā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§āϰāĨ¤
āĻŽāύ⧠āĻāϰ, āĻāĻŽāĻžāĻĻā§āϰāĻā§ \(N=55\)-āĻā§ āĻā§āĻĒāĻžāĻĻāĻā§ āĻŦāĻŋāĻļā§āϞā§āώāĻŖ āĻāϰāϤ⧠āĻšāĻŦā§āĨ¤ (āĻāĻŽāϰāĻž āϝāĻĻāĻŋāĻ āĻāĻžāύāĻŋ āϝ⧠\(55\) āĻāϰ āĻāĻāĻāĻŋ āĻā§āĻĒāĻžāĻĻāĻ \(p=5\), āϤāĻŦā§āĻ āĻāĻŽāϰāĻž āϏā§āĻāĻŋ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻŦā§āϰ āĻāϰāĻŦāĨ¤)
āĻāĻŽāϰāĻž āĻāϰāĻŦ āĻāĻŋ, āϰâā§āϝāĻžāύā§āĻĄāĻŽ āĻĒā§āϰā§āĻŖāϏāĻāĻā§āϝāĻžāϰ āĻāĻāĻāĻŋ āĻ
āϏā§āĻŽ āϧāĻžāϰāĻž (infinite sequence) \(a_0, a_1, a_2, a_3, a_4,\ldots\) [āϏāĻāĻā§āώā§āĻĒā§ \(\{a_i\}_{i = 0}^{\infty}\)] āĻĨā§āĻā§ āĻā§ā§āĻžāϞ āĻā§āĻļāĻŋāĻŽāϤ āĻāĻŋāĻā§ āĻĒāĻĻ, āϝā§āĻŽāύ: \(a_0, a_3, a_7, a_{100}\), āϤā§āϞ⧠āύā§āĻŦāĨ¤ āĻāύā§āĻŽāĻĻāĻŋāύ āϏāĻŽāϏā§āϝāĻž āĻ
āύā§āϝāĻžā§ā§, āĻāĻ āĻāĻžāϰāĻāĻŋ āĻĒāĻĻā§āϰ āĻŽāĻžāĻā§ \(\pmod {5}\)-āĻ āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻ
āύā§āϤāϤ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž\[1-e^{-\frac{4^2}{2\times 5}}\approx 80\%\]āĻāĻŽāύ āĻĻā§āĻāĻŋ āĻĒāĻĻ \(a_m\) āĻāĻŦāĻ \(a_n\) āϝāĻĻāĻŋ āϏāϤā§āϝāĻŋ āϏāϤā§āϝāĻŋ āĻĨāĻžāĻā§, āϤāĻžāĻšāϞ⧠\[a_m\equiv a_n\pmod{5}\]\[\implies a_m-a_n\equiv 0\pmod{5}\]\[\implies d = \gcd(55, a_m-a_n)\ge 5\] āĻ
āϰā§āĻĨāĻžā§, āĻāĻŽāϰāĻž \(55\)-āĻāϰ āĻāĻāĻāĻŋ āĻā§āĻĒāĻžāĻĻāĻ \(d\) āύāĻŋāϰā§āĻŖā§ āĻāϰ⧠āĻĢā§āϞāĻŦāĨ¤ āĻ
āĻŦāĻļā§āϝ āĻā§āĻ āĻĒā§āϰāĻļā§āύ āĻāϰāϤā§āĻ āĻĒāĻžāϰ⧠\(d = 55\) āĻšāϞā§? āĻšā§āϝāĻžāĻ, āϏā§āĻāĻž āĻšāϤ⧠āĻĒāĻžāϰā§āĨ¤ āĻāĻŋāύā§āϤ⧠āĻāĻžāϰāĻāĻŋ āϏāĻāĻā§āϝāĻžāϰ āĻŽāĻžāĻā§ \(\pmod{55}\)-āĻ āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻĻā§āĻāĻŋ āϏāĻāĻā§āϝāĻž āĻĒāĻžāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž āĻŽāĻžāϤā§āϰ\[1-e^{-\frac{4^2}{2\times 55}}\approx 13.5\%\]
āĻ
āϤāĻāĻŦ, āĻāĻŽāϰāĻž āϝāĻĻāĻŋ \(\{a_i\}_{i = 0}^{\infty}\) āĻĨā§āĻā§ āĻĒā§āϰāϤāĻŋāĻŦāĻžāϰ āϝā§āĻā§āύ āĻĻā§āĻāĻāĻŋ āĻĒāĻĻ \(a_i\) āĻāĻŦāĻ \(a_j\) āύāĻŋā§ā§ \(\gcd(N, a_i-a_j)\) āύāĻŋāϰā§āĻŖā§ āĻāϰ⧠āϝā§āϤ⧠āĻĨāĻžāĻāĻŋ, āϤāĻžāĻšāϞ⧠āĻā§āĻŦāĻ āĻāĻžāϞ āϏāĻŽā§āĻāĻžāĻŦāύāĻž āĻāĻā§ āϝ⧠āĻāĻŽāϰāĻž \(a_m-a_n\) āĻĒā§ā§ā§ āϝāĻžāĻŦ āĻāĻŦāĻ \(55\)-āĻāϰ āĻāĻāĻāĻŋ āĻĒā§āϰāĻā§āϤ āĻā§āĻĒāĻžāĻĻāĻ \(d\) āύāĻŋāϰā§āĻŖā§ āĻāϰ⧠āĻĢā§āϞāĻŦāĨ¤
āϤāĻŦā§ āĻāĻžāĻŽā§āϞāĻž āĻšāĻā§āĻā§ āĻāĻžāĻāĻāĻŋ āϰâā§āϝāĻžāύā§āĻĄāĻŽ āϏāĻāĻā§āϝāĻžāϰ āĻ
āϏā§āĻŽ āϧāĻžāϰāĻž āĻŦā§āϝāĻŦāĻšāĻžāϰ āĻāϰāϞ⧠āϏā§āĻāĻŋāϰ āĻ
āύā§āĻāĻā§āϞ⧠āĻĒāĻĻ āĻāĻŽāĻžāĻĻā§āϰāĻā§ āĻŽā§āĻŽāϰāĻŋāϤ⧠āϰāĻžāĻāϤ⧠āĻšāĻŦā§, āĻĢāϞ⧠\(50\) āĻŦāĻž \(100\) āĻĄāĻŋāĻāĻŋāĻā§āϰ āĻā§āύ āϏāĻāĻā§āϝāĻžāϰ āĻāύā§āϝ āĻā§āĻāĻŋ āĻā§āĻāĻŋ āĻĒā§āĻāĻžāĻŦāĻžāĻāĻ āĻŽā§āĻŽāϰāĻŋāϰ āĻĒā§āϰā§ā§āĻāύ āĻšāĻŦā§āĨ¤ āϤāĻžāĻ āĻāĻŽāϰāĻž āĻāĻŽāύ āĻā§āύ āϏāĻāĻā§āϝāĻžāϰ āϧāĻžāϰāĻž āύā§āĻŦ āϝāĻžāϰ āĻŽāĻžāύ āĻĒā§āϰāĻā§āϤāĻĒāĻā§āώ⧠āĻĄāĻŋāĻāĻžāϰāĻŽāĻŋāύāĻŋāϏā§āĻāĻŋāĻ, āĻ
āϰā§āĻĨāĻžā§ āϏā§āϤā§āϰ āĻŽā§āύ⧠āĻāϞā§, āĻāĻŋāύā§āϤ⧠\(\pmod p\)-āϤ⧠āĻŽā§āĻāĻžāĻŽā§āĻāĻŋ āϰâā§āϝāĻžāύā§āĻĄāĻŽāϞāĻŋ āĻāϏā§āĨ¤ (āĻāĻŽāύ āϏāĻāĻā§āϝāĻžāĻā§ āĻŦāϞ⧠āϏā§āĻĄā§āϰâā§āϝāĻžāύā§āĻĄāĻŽ āϏāĻāĻā§āϝāĻž)
āĻāĻĻāĻžāĻšāϰāĻŖāϏā§āĻŦāϰā§āĻĒ, āĻ
āϏā§āĻŽ āϧāĻžāϰāĻž āĻšāĻŋāϏā§āĻŦā§ \(a_0=1\), āĻāĻŦāĻ \(a_i=a_{i-1}^2+1\), āĻ
āϰā§āĻĨāĻžā§ \(1, 2, 5, 26, 677,\ldots\) āϧāĻžāϰāĻžāĻāĻŋ āύā§āĻā§āĻž āύā§āĻŦ āĻāĻŦāĻ āĻĒā§āϰāϤāĻŋāĻāĻŋ āĻĒāĻĻā§āϰ āĻāύā§āϝ \(\gcd(N, a_i-a_0)\) āύāĻŋāϰā§āĻŖā§ āĻāϰāĻŦāĨ¤ āϞāĻā§āώā§āϝ āĻāϰ āϝā§, āĻāĻŽāĻžāĻĻā§āϰ \(a_i\)-āĻāϰ āĻĒā§āϰāĻā§āϤ āĻŽāĻžāύā§āϰ āĻĒāϰāĻŋāĻŦāϰā§āϤ⧠\(a_i\pmod N\) āĻāĻžāύāϞā§āĻ āĻāϞā§āĨ¤
def rhonaive(N):
a_0 = d = 1
a_i = a_0
while d == 1:
a_i = (a_i * a_i + 1) % N
d = gcd(a_i - a_0, N)
return d
āĻ
āύā§āĻāϏāĻŽā§ āĻĻā§āĻāĻž āϝā§āϤ⧠āĻĒāĻžāϰ⧠āĻāĻŽāĻžāĻĻā§āϰ āύā§āĻā§āĻž āϏā§āĻĄā§āϰâā§āϝāĻžāύā§āĻĄāĻŽ āϏāĻāĻā§āϝāĻžāϰ āϧāĻžāϰāĻžāĻāĻŋ “āϝāĻĨā§āώā§āĻ āϰâā§āϝāĻžāύā§āĻĄāĻŽ” āύā§āĨ¤ āϤā§āĻŽāύ āĻā§āώā§āϤā§āϰ⧠āĻāĻŽāĻžāĻĻā§āϰ \(a_i = a_{i-1}^2+1\) āĻāϰ āĻĒāϰāĻŋāĻŦāϰā§āϤ⧠āĻāϰā§āĻāĻā§ āĻāĻāĻŋāϞ āĻā§āύ āϏāĻŽā§āĻĒāϰā§āĻ āĻŦā§āϝāĻŦāĻšāĻžāϰ āĻāϰāϤ⧠āĻšāĻŦā§āĨ¤ āϤāĻžāĻ, āϏāĻžāϧāĻžāϰāĻŖāĻāĻžāĻŦā§(generally) āĻāĻŽāϰāĻž \(a_i=f(a_{i-1})\) āϧāϰāϤ⧠āĻĒāĻžāϰāĻŋ āϝā§āĻāĻžāύ⧠\(f(x)\) āĻšāĻā§āĻā§ āĻāĻāĻāĻŋ āϏā§āĻŦāĻŋāϧāĻžāĻāύāĻ āĻŦāĻšā§āĻĒāĻĻā§āĨ¤ āϝā§āĻŽāύ- āĻāĻĒāϰā§āϰ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽā§ \(f(x)=x^2+1\).
āϞāĻā§āώā§āϝ āĻāϰ āϝā§, \(\{a_i\}_{i = 0}^{\infty}\) āϧāĻžāϰāĻžāϰ āĻĒā§āϰāϤāĻŋāĻāĻŋ āĻĒāĻĻ āĻļā§āϧā§āĻŽāĻžāϤā§āϰ āĻāĻā§āϰ āĻĒāĻĻā§āϰ āĻāĻĒāϰ āύāĻŋāϰā§āĻāϰāĻļā§āϞāĨ¤ āϤāĻžāĻ \(a_m \equiv a_n\pmod p\) āĻāĻāĻŦāĻžāϰ āĻĒāĻžāĻā§āĻž āĻā§āϞ⧠āϧāĻžāϰāĻžāϤ⧠āĻĒā§āϰā§āĻŦāĻŦāϰā§āϤ⧠āĻĒāĻĻāĻā§āϞ⧠āϏāĻžāĻāĻā§āϞāĻŋāĻāĻāĻžāĻŦā§ āĻā§āϰ⧠āĻĢāĻŋāϰ⧠āĻāϏāϤ⧠āĻĨāĻžāĻāĻŦā§āĨ¤ āĻ
āϰā§āĻĨāĻžā§,\(a_{m+i}\equiv a_{n+i}\pmod p\).
āϤāĻŦā§ āĻāĻ āϏāĻžāĻāĻā§āϞ \(a_0\) āĻĨā§āĻā§ āĻļā§āϰ⧠āĻšāϤ⧠āĻšāĻŦā§ āĻāĻŽāύ āĻā§āύ āĻāĻĨāĻž āύā§āĻāĨ¤ āϝā§āĻŽāύ- \(p=29\) āĻāĻŦāĻ \(f(x)=x^2+1\) āĻšāϞā§, \(\pmod p\)-āϤ⧠\(\{a_i\}_{i = 0}^{\infty}\) āϧāĻžāϰāĻžāĻāĻŋ āĻšā§
\(i\) |
\(0\) |
\(1\) |
\(2\) |
\(3\) |
\(4\) |
\(5\) |
\(6\) |
\(7\) |
\(8\) |
\(9\) |
\(10\) |
\(11\) |
\(a_i\) |
\(1\) |
\(2\) |
\(5\) |
\(26\) |
\(10\) |
\(14\) |
\(23\) |
\(8\) |
\(7\) |
\(21\) |
\(\color{red}7\) |
\(\color{red}{21}\) |
āĻĻā§āĻāϤā§āĻ āĻĒāĻžāĻā§āĻ, \(a_0\)-āϰ āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻā§āύ āĻĒāĻĻ āĻĻā§āĻŦāĻŋāϤā§ā§āĻŦāĻžāϰ āĻĒāĻžāĻā§āĻž āϝāĻžā§āύāĻŋāĨ¤ āϤāĻžāĻ, āĻĒā§āϰā§āĻā§āϰāĻžāĻŽ ā§§-āĻ āϏāĻŦāϏāĻŽā§ \(a_0\) āĻĨā§āĻā§ āϏāĻžāĻāĻā§āϞ āĻļā§āϰ⧠āĻšāĻŦā§ āϧāϰ⧠āύā§āĻā§āĻžāĻāĻž āĻā§āϞ āĻāĻŋāϞāĨ¤
āĻāĻŽāύ āϧāĻžāϰāĻžāϤ⧠āϏāĻžāĻāĻā§āϞ (āĻ
āϰā§āĻĨāĻžā§ \(\pmod p\)-āϤ⧠āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ) āύāĻŋāϰā§āĻŖā§ āĻāϰāϤ⧠āĻāϰā§āĻāĻā§ āĻŦā§āĻĻā§āϧāĻŋ āĻāĻžāĻāĻžāϤ⧠āĻšā§āĨ¤ āĻāĻŽāĻŋ āĻāĻāĻžāύ⧠āĻĻā§āĻāĻŋ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§āϰ āĻāĻĨāĻž āĻŦāϞ⧠āĻĻāĻŋāĻā§āĻāĻŋāĨ¤ āĻĒā§āϰāĻĨāĻŽāĻāĻŋ āĻĢā§āϞā§ā§āĻĄā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ, āĻĻā§āĻŦāĻŋāϤā§ā§āĻāĻŋ āĻŦā§āϰā§āύā§āĻā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽāĨ¤
āĻĢā§āϞā§ā§āĻĄā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ
āĻŽāύ⧠āĻāϰ \(a_i\) āϧāĻžāϰāĻžāϰ āϏāĻžāĻāĻā§āϞā§āϰ āĻĻā§āϰā§āĻā§āϝ \(l\). \(n\) āϝāĻĻāĻŋ āϝāĻĨā§āώā§āĻ āĻŦā§ āĻšā§, āϤāĻŦā§,\[a_n\equiv a_{n+l}\equiv a_{n+2l}\equiv\cdots\equiv a_{n+kl}\pmod p\]
āĻāĻŽāϰāĻž āϝāĻĻāĻŋ āϝāĻĨā§āώā§āĻ āĻŦā§ āĻā§āύ \(k\)-āϰ āĻāύā§āϝ \(n=kl\) āύā§āĻ, āϤāĻŦā§,\[a_n \equiv a_{n+kl}=a_{2kl}=a_{2n}\pmod p\]
āĻ
āϰā§āĻĨāĻžā§, \(a_i\) āϧāĻžāϰāĻžā§ āĻāĻŽāύ āĻ
āϏā§āĻŽ āϏāĻāĻā§āϝāĻ āĻĒāĻĻ \(a_n\) āĻāĻā§ āϝāĻžāĻĻā§āϰ āĻāύā§āϝ \(a_n\equiv a_{2n}\pmod p\). āϏā§āϤāϰāĻžāĻ \(\gcd(N, a_{2i}-a_i)\) āύāĻŋāϰā§āĻŖā§ āĻāϰ⧠āϝā§āϤ⧠āĻĨāĻžāĻāϞā§āĻ āĻāĻāĻāĻž āϏāĻŽā§ \(\pmod p\)-āϤ⧠āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻž āϝāĻžāĻŦā§āĨ¤ āĻĢā§āϞā§ā§āĻĄā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻāĻ āϧāĻžāϰāĻŖāĻžāĻāĻŋ āĻŦā§āϝāĻŦāĻšāĻžāϰ āĻāϰā§āĨ¤
āĻĢā§āϞā§ā§āĻĄā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§ āĻāĻāĻāĻŋ āĻāϰāĻā§āĻļ āĻāϰ āĻāĻāĻāĻŋ āĻāĻā§āĻāĻĒā§āϰ āĻŽāĻžāĻā§ āĻĻā§ā§ āĻĒā§āϰāϤāĻŋāϝā§āĻāĻŋāϤāĻžāϰ āĻāϞā§āĨ¤ āĻāĻā§āĻāĻĒāĻāĻŋ āϧāĻžāϰāĻžāϰ āĻāĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒāĻĻā§ \(a_0, a_1, a_2,a_3,\ldots\) āĻĒāϰā§āϝāĻžā§āĻā§āϰāĻŽā§ āϝā§āϤ⧠āĻĨāĻžāĻā§āĨ¤ āĻāĻāĻāϏāĻŽā§ā§, āĻāϰāĻā§āĻļāĻāĻŋ āϧāĻžāϰāĻžāϰ \(a_0, a_2, a_4, a_6,\ldots\) āĻĒāĻĻāĻā§āϞā§āϤ⧠āϞāĻžāĻĢāĻŋā§ā§ āϞāĻžāĻĢāĻŋā§ā§ āϝā§āϤ⧠āĻĨāĻžāĻā§āĨ¤ āĻāĻŽāϰāĻž āĻāϰāĻā§āĻļā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύ āĻāĻŦāĻ āĻāĻā§āĻāĻĒā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύā§āϰ āĻĒāĻžāϰā§āĻĨāĻā§āϝā§āϰ āϏāĻžāĻĨā§ \(N\)-āĻāϰ āĻāϏāĻžāĻā§ āύāĻŋāϰā§āĻŖā§ āĻāϰāϤ⧠āĻĨāĻžāĻāĻŋāĨ¤ āϝāĻāύāĻ āĻāϏāĻžāĻā§ \(1\) āĻāϰ āĻā§ā§ā§ āĻŦā§ āĻšā§ā§ āϝāĻžā§, āĻāϞāĻā§āϰāĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāϰā§āĻŽāĻŋāύā§āĻ āĻāϰā§āĨ¤
def rhofloyd(N):
#both hare and tortoise at a_0
tortoise = hare = d = 1
while d == 1:
tortoise = f(tortoise) % N #tortoise steps once
hare = f(f(hare)) % N #hare steps twice
d = gcd(hare - tortoise, N)
return d
āĻŦā§āϰā§āύā§āĻā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ
āĻŦā§āϰā§āύā§āĻā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§ āĻ
āύā§āĻāĻā§āϞ⧠āϰāĻžāĻāύā§āĻĄā§ āĻāϰāĻā§āĻļ āĻāϰ āĻāĻā§āĻāĻĒā§āϰ āĻĻā§ā§ āĻĒā§āϰāϤāĻŋāϝā§āĻāĻŋāϤāĻž āĻāϞā§āĨ¤ āĻĒā§āϰāϤāĻŋāϝā§āĻāĻŋāϤāĻžāϰ \(i\)-āϤāĻŽ āϰāĻžāĻāύā§āĻĄā§ āĻāϰāĻā§āĻļ āĻāϰ āĻāĻā§āĻāĻĒ āĻāĻā§ā§āĻ \(a_{2^i}\)-āϤāĻŽ āĻĒāĻĻā§ āĻ
āĻŦāϏā§āĻĨāĻžāύ āĻāϰā§āĨ¤ āĻĒā§āϰāϤāĻŋāϝā§āĻāĻŋāϤāĻž āĻļā§āϰā§āϰ āĻĒāϰ āĻāϰāĻā§āĻļ āϤāĻžāϰ āĻāĻžā§āĻāĻžā§ āĻāϰāĻžāĻŽ āĻāϰ⧠āĻā§āĻŽ āĻĻā§ā§, āĻāϰ āĻāĻā§āĻāĻĒāĻāĻŋ āĻā§āĻ āĻā§āĻ āĻāϰ⧠āĻāĻāĻāĻŋ āĻāĻāĻāĻŋ āĻĒāĻĻ āϏāĻžāĻŽāύ⧠āĻāĻā§āϤ⧠āĻĨāĻžāĻā§āĨ¤ āĻāĻŽāϰāĻž āĻĒā§āϰāϤāĻŋāĻŦāĻžāϰāĻ āĻāϰāĻā§āĻļā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύ āĻāĻŦāĻ āĻāĻā§āĻāĻĒā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύā§āϰ āĻĒāĻžāϰā§āĻĨāĻā§āϝā§āϰ āϏāĻžāĻĨā§ \(N\)-āĻāϰ āĻāϏāĻžāĻā§ \(d\) āύāĻŋāϰā§āĻŖā§ āĻāϰāĻŋāĨ¤ āϝāĻāύ āĻāĻā§āĻāĻĒ āĻāϰāĻā§āĻļā§āϰ āĻā§ā§ā§ \(2^i\) āĻĒāĻĻ āϏāĻžāĻŽāύ⧠āĻāĻāĻŋā§ā§ āϝāĻžā§, āĻāϰāĻā§āĻļā§āϰ āϤā§āĻžāĻ āĻāϰ⧠āĻā§āĻā§ āĻāĻ ā§ āĻāĻŦāĻ āϏ⧠āĻāĻ āϞāĻžāĻĢā§ āĻāĻā§āĻāĻĒā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύ⧠āĻāϞ⧠āĻāϏā§āĨ¤ āĻāϰāĻĒāϰ āĻĒā§āϰāϤāĻŋāϝā§āĻāĻŋāϤāĻžāϰ \(i+1\)-āϤāĻŽ āϰāĻžāĻāύā§āĻĄ āĻļā§āϰ⧠āĻšā§āĨ¤
āĻāĻā§āϰ āĻŽāϤāĻ, \(d> 1\) āĻšā§ā§ āĻā§āϞ⧠āĻāϞāĻā§āϰāĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāϰā§āĻŽāĻŋāύā§āĻ āĻāϰāĻŦā§āĨ¤
āϞāĻā§āώā§āϝ āĻāϰ āϝā§, \(i\) āĻāϰ āĻŽāĻžāύ āĻŦāĻžā§āĻžāϰ āϏāĻžāĻĨā§ āϏāĻžāĻĨā§ \(2^{i}\) āĻāĻŦāĻ \(2^{i+1}\)-āĻāϰ āĻŽāϧā§āϝāĻŦāϰā§āϤ⧠āĻĒāĻžāϰā§āĻĨāĻā§āϝāĻ āĻŦāĻžā§āϤ⧠āĻĨāĻžāĻā§āĨ¤ āĻāĻāĻāĻž āϏāĻŽā§ āĻāĻ āĻĒāĻžāϰā§āĻĨāĻā§āϝ \(\{a_i\}_{i = 0}^\infty\) āϧāĻžāϰāĻžāϰ āϏāĻžāĻāĻā§āϞā§āϰ āĻĻā§āϰā§āĻā§āϝ \(l\) āĻĨā§āĻā§ āĻŦā§ āĻšā§ā§ āϝāĻžā§āĨ¤ āϤāĻāύ āĻāĻā§āĻāĻĒā§āϰ āĻā§āύ āĻāĻ āĻ
āĻŦāϏā§āĻĨāĻžāύā§āϰ āĻāύā§āϝ āĻāϰāĻā§āĻļ āĻ āĻāĻā§āĻāĻĒā§āϰ āĻ
āĻŦāϏā§āĻĨāĻžāύā§āϰ āĻĒāĻžāϰā§āĻĨāĻā§āϝ āĻšāĻŦā§ āĻ āĻŋāĻ \(l\)āĻāĻŋ āĻĒāĻĻāĨ¤ āĻāĻ āĻ
āĻŦāϏā§āĻĨāĻžāϤā§āĻ āĻāϏāϞ⧠āĻāϞāĻā§āϰāĻŋāĻĻāĻŽāĻāĻŋ āĻāĻžāϰā§āĻŽāĻŋāύā§āĻ āĻāϰāĻŦā§āĨ¤
def rhobrent(N):
#both hare and tortoise are at a_(2^0)
#power is the nearest 2^i behind tortoise
tortoise = hare = f(1)
power, lead, d = 1, 0, 1
while d == 1:
if lead == power: #tortoise reaches 2^(i+1)-th term
hare = tortoise #hare jumps to tortoise's position
power *= 2 #update power
lead = 0 #reset lead, since both hare and tortoise
#are in the same position now
tortoise = f(tortoise) % N #tortoise steps once
lead += 1 #tortoise leads the race by one more step
d = gcd(hare - tortoise, N)
return d
āĻŦā§āϰā§āύā§āĻā§āϰ āĻāύāĻžāϞāĻžāĻāϏāĻŋāϏ āĻ
āύā§āϏāĻžāϰā§, āĻŦā§āϰā§āύā§āĻā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻĢā§āϞā§ā§āĻĄā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻĨā§āĻā§ \(24\%\) āĻĻā§āϰā§āϤāϤāϰāĨ¤
āĻĒā§āϰā§āĻŖāĻžāĻā§āĻ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽ
āĻŦā§āϰā§āύā§āĻā§āϰ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻĻāĻŋā§ā§ āϝā§āĻšā§āϤ⧠āϏāĻžāĻāĻā§āϞ āĻļāύāĻžāĻā§āϤāĻāϰāĻŖ āϏāĻŦāĻā§ā§ā§ āĻĻā§āϰā§āϤ āĻāϰāĻž āϝāĻžā§, āϤāĻžāĻ āϏā§āĻāĻŋ āĻĻāĻŋā§ā§āĻ āύāĻŋāĻā§ āĻāĻāĻāĻŋ āĻĒā§āϰā§āĻŖāĻžāĻā§āĻ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽ āĻĻā§āĻā§āĻž āĻšāϞāĨ¤
from fractions import gcd
from time import time
def f(x):
return (x**2 + x + 1) % N
def rhobrent(N):
tortoise = hare = f(1)
power, lead, d = 1, 0, 1
while abs(d) == 1:
if lead == power:
hare, lead = tortoise, 0
power *= 2
tortoise = f(tortoise)
lead += 1
d = gcd(tortoise - hare, N)
return d
N = int(raw_input())
exec_time = time()
d = 1 if(-2 < N < 2) else rhobrent(N)
exec_time = time() - exec_time
print d, '*', N / d
print "Execution time: %.3f s" % exec_time
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iso646.h> //and
#define MAX 2147483647
long long f(long long x);
long long gcd(long long a, long long b);
long long rhobrent(long long N);
long long N;
int main(void){
long long d;
scanf("%lld", &N);
clock_t exec_time = clock();
d = (N < 2 and N > -2) ? 1 : rhobrent(N);
exec_time = clock() - exec_time;
double t = (double) exec_time / CLOCKS_PER_SEC;
printf("%lld * %lld\n", d, N/d);
printf("Execution time: %.3lf s\n", t);
return 0;
}
long long f(long long x){
if(x < MAX)
return (x * x + x + 1) % N;
long long y = x, output = x + 1;
while(y > 0){
if(y % 2 == 1)
output += x;
x *= 2;
y /= 2;
output %= N;
x %= N;
}
return output;
}
long long gcd(long long a, long long b){
long long r;
while(b != 0){
r = a % b;
a = b;
b = r;
}
return (a > 0) ? a : -a;
}
long long rhobrent(long long N){
long long tortoise = f(1), hare = f(1), power = 1, lead = 0, d = 1;
while(d == 1){
if(lead == power){
hare = tortoise;
power *= 2;
lead = 0;
}
tortoise = f(tortoise);
lead++;
d = gcd(N, tortoise - hare);
}
return d;
}
āύā§āĻ:
- āĻāĻĒāϰā§āϰ āĻā§āĻĄā§ \(f(x)=x^2+x+1\) āĻāĻŦāĻ āĻĢāĻžāĻāĻļāĻžāύā§āϰ āĻā§āϤāϰā§āĻ \(N\) āĻĻāĻŋā§ā§ āĻŽāĻĄā§āϞāĻžāϏā§āϰ āĻāĻžāĻ āĻļā§āώ āĻāϰāĻž āĻšā§ā§āĻā§āĨ¤
- āĻĒā§āϰāĻžā§ āϏāĻāϞ āĻāϧā§āύāĻŋāĻ āĻāĻŽā§āĻĒāĻžāĻāϞāĻžāϰ⧠long long int-āĻāϰ āĻŦā§āϝāĻžāĻŦāϧ⧠\([-2^{63}, 2^{63})\). āϤāĻžāĻ āϏāĻŋ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽā§ \(f(x)\) āĻĢāĻžāĻāĻļāύāĻāĻŋ āĻ āĻŋāĻāĻ āĻžāĻāĻŽāϤ āĻāĻžāĻ āĻāϰāĻžāϰ āĻāύā§āϝ \[x^2+x+1\leq 2^{63}-1\Longrightarrow x<2^{31.5}-1\] āĻšāϤ⧠āĻšāĻŦā§āĨ¤ āĻāĻāύā§āϝ \(x \ge 2^{31}\) -āĻāϰ āĻāύā§āϝ \(y = x\) āύāĻžāĻŽā§āϰ āĻāĻāĻāĻŋ āύāϤā§āύ āĻā§āϰāĻŋā§ā§āĻŦāϞ āύāĻŋā§ā§ āĻāϰ āĻĒā§āϰāϤāĻŋāĻāĻŋ āĻŦāĻŋāĻā§āϰ āϏāĻžāĻĨā§ āĻāϞāĻžāĻĻāĻžāĻāĻžāĻŦā§ \(x\)-āĻāϰ āĻā§āĻŖāĻĢāϞ āĻŦā§āϰ āĻāϰ⧠āϏā§āĻ āϏāĻŽāώā§āĻāĻŋāϰ āĻŽāĻĄā§āϞāĻžāϏ āύā§āĻā§āĻž āĻšā§ā§āĻā§āĨ¤
- \(\pmod N\) āĻāĻŦāĻ \(\pmod p\)-āϤ⧠\(N\)-āĻāϰ āϏāĻžāĻāĻā§āϞ āĻāĻāĻ āĻšāϞ⧠āĻāĻĒāϰā§āϰ āĻĒā§āϰā§āĻā§āϰāĻžāĻŽ \(N\) āĻā§āϤā§āϰāĻŋāĻŽ āĻšāĻā§āĻž āϏāϤā§āĻŦā§āĻ āĻāϰ āĻā§āĻĒāĻžāĻĻāĻ āĻā§āĻāĻā§ āĻĒāĻžāĻŦā§ āύāĻžāĨ¤ āĻāϰāĻāĻŽ āĻšāϞ⧠\(f(x)\) āĻĒāϞāĻŋāύā§āĻŽāĻŋā§āĻžāϞāĻāĻŋ āĻĒāϰāĻŋāĻŦāϰā§āϤāύ āĻāϰ⧠āĻāĻŦāĻžāϰ āĻā§āώā§āĻāĻž āĻāϰāϤ⧠āĻĒāĻžāϰāĨ¤
āĻāĻŽāĻĒā§āϞā§āĻā§āϏāĻŋāĻāĻŋ
āĻŽāύ⧠āĻāϰ, \(\{a_i\}_{i=0}^{\infty}\) āĻāĻāĻāĻŋ āϏāϤā§āϝāĻŋāĻāĻžāϰ⧠āϰâā§āϝāĻžāύā§āĻĄāĻŽ āϧāĻžāϰāĻžāĨ¤ āĻāύā§āĻŽāĻĻāĻŋāύā§āϰ āϏāĻŽāϏā§āϝāĻž āĻ
āύā§āϝāĻžā§ā§, \(\pmod p\)-āϤ⧠āĻāύāĻā§āϰā§ā§ā§āύā§āĻ āĻĻā§āĻāĻŋ āĻĒāĻĻ āĻĒāĻžāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \(99\%\) āĻšāϤ⧠āĻšāϞ⧠\(\sqrt{-2\times\ln(1-0.99)}\sqrt{p}\)-āĻāĻŋ āĻĒāĻĻ āύāĻŋāϤ⧠āĻšāĻŦā§āĨ¤ āĻ
āϤāĻāĻŦ, āϰ⧠āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§āϰ āĻāĻŽāĻĒā§āϞā§āĻā§āϏāĻŋāĻāĻŋ \(O(\sqrt p)\leq O\left(N^{\frac 1 4}\right)\). [āĻ
āϰā§āĻĨāĻžā§ \(N\) āϏāĻāĻā§āϝāĻžāĻāĻŋāϤ⧠\(k\)āĻāĻŋ āĻĄāĻŋāĻāĻŋāĻ āĻĨāĻžāĻāϞ⧠āϰ⧠āĻāϞāĻā§āϰāĻŋāĻĻāĻŽā§āϰ āϰāĻžāύāĻāĻžāĻāĻŽ \(O\left(10^{\frac k 4}\right)\)]
āĻāϤāĻĒāϰā§āĻŦā§āϰ āĻā§ā§ā§ āĻāϰā§āĻāĻā§ āĻāĻžāϞ⧠āĻŦāĻžāĻāύā§āĻĄ, āϤāĻžāĻ āύāĻž? āĻĒāϰāĻŦāϰā§āϤ⧠āĻĒāϰā§āĻŦā§ āĻāĻŽāϰāĻž āĻāύ āĻĒā§āϞāĻžāϰā§āĻĄā§āϰāĻ āĻāϰā§āĻāĻāĻŋ āĻāϞāĻā§āϰāĻŋāĻĻāĻŽ āĻĻā§āĻāĻŦ, āϝā§āĻāĻŋāϰ āύāĻžāĻŽ \(p-1\) āĻāϞāĻā§āϰāĻŋāĻĻāĻŽāĨ¤
āĻĒāϰāĻŋāĻļāĻŋāώā§āĻ
āĻāύā§āĻŽāĻĻāĻŋāύ āϏāĻŽāϏā§āϝāĻž
āϤā§āĻŽāĻžāϰ āĻĢā§āϏāĻŦā§āĻ āĻĢā§āϰā§āύā§āĻĄāϞāĻŋāϏā§āĻā§ āύā§āύā§āϝāϤāĻŽ āĻāϤāĻāύ āĻĨāĻžāĻāϞ⧠āĻāĻāĻĨāĻž āύāĻŋāĻļā§āĻāĻŋāϤ āĻāϰ⧠āĻŦāϞāĻž āϝāĻžāĻŦā§ āϝ⧠āĻ
āύā§āϤāϤ āĻĻā§āĻāĻāύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ āĻāĻāĻ āϤāĻžāϰāĻŋāĻā§ āĻšāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \(99\%\)?
āĻŽāύ⧠āĻāϰ, āϤā§āĻŽāĻžāϰ āĻĢā§āϰā§āύā§āĻĄāϞāĻŋāϏā§āĻā§ \(m\) āĻāύ āĻĢā§āϰā§āύā§āĻĄ āĻāĻā§, āĻāĻŦāĻ āĻā§āύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ ⧍⧝ āĻĢā§āĻŦā§āϰā§ā§āĻžāϰāĻŋ āύā§āĨ¤ āĻā§āύ āĻāĻāĻāύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ ā§Ŧ āĻ
āĻā§āĻā§āĻŦāϰ āĻšāϞ⧠āĻāϰ āĻā§āύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ ā§Ŧ āĻ
āĻā§āĻā§āĻŦāϰ āύāĻž āĻšāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \(1-\frac {1}{365}\). āĻāϰā§āĻ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ āĻŽāύ⧠āĻāϰ ā§Ē āĻāĻāϏā§āĻāĨ¤ āϏā§āϤāϰāĻžāĻ, āϤā§āϤā§ā§ āĻā§āύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ ā§Ŧ āĻ
āĻā§āĻā§āĻŦāϰ āĻŦāĻž ā§Ē āĻāĻāϏā§āĻ āύāĻž āĻšāĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \(1-\frac {2}{365}\). āĻ
āϤāĻāĻŦ, \(m\) āĻāύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāĻŋāύā§āύ āĻāĻŋāύā§āύ āĻĻāĻŋāύ⧠āĻāύā§āĻŽāĻĻāĻŋāύ āĻĒā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \[\left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)\]
āϤāĻžāĻšāϞā§, āĻ
āύā§āϤāϤ āĻĻā§āĻāύ āĻĢā§āϰā§āύā§āĻĄā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ āĻāĻāĻ āĻĻāĻŋāύ⧠āĻĒā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \[1 – \left(1-\frac {1}{365}\right)\cdots\left(1-\frac {m-1}{365}\right)\]
\(x\)-āĻāϰ āĻŽāĻžāύ \(0\)-āĻāϰ āĻāĻžāĻāĻžāĻāĻžāĻāĻŋ āĻšāϞ⧠āĻāĻŽāϰāĻž āĻā§āĻāϞāϰā§āϰ āϏāĻŋāϰāĻŋāĻ āĻĨā§āĻā§ \(1-x\approx e^{-x}\) āϞāĻŋāĻāϤ⧠āĻĒāĻžāϰāĻŋāĨ¤ āĻāĻāĻžāĻŦā§ āĻāĻĒāϰā§āϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻžāĻāĻŋāĻā§ āϏāϰāϞ āĻāϰ⧠āϞāĻŋāĻāĻž āϝāĻžā§ \[1-e^{-\frac {1}{365}}\cdot e^{-\frac {2}{365}}\cdots e^{-\frac {m-1}{365}}\]\[\approx 1-e^{-\frac{m^2}{2\times 365}}\]āĻāĻāύ \(1-e^{-\frac{m^2}{2\times 365}}\ge 0.99\) āĻšāϤ⧠āĻšāϞ⧠\[m\ge \sqrt{-2\times 365\ln(1-0.99)}\approx 58\] āĻšāϤ⧠āĻšāĻŦā§āĨ¤
āϤā§āĻŽāĻžāϰ āĻĢā§āϰā§āύā§āĻĄāϞāĻŋāϏā§āĻā§ āĻŽāĻžāϤā§āϰ \(58\) āĻāύ āĻŽāĻžāύā§āώ āĻĨāĻžāĻāϞā§āĻ āϤā§āĻŽāĻŋ \(99\%\) āĻā§āϝāĻžāϰāĻžāύā§āĻāĻŋ āĻĻāĻŋā§ā§ āĻŦāϞāϤ⧠āĻĒāĻžāϰāĻŦā§ āϝ⧠āĻ
āύā§āϤāϤ āĻĻā§āĻāĻāύā§āϰ āĻāύā§āĻŽāĻĻāĻŋāύ āĻāĻāĻ āϤāĻžāϰāĻŋāĻā§! āĻāĻ āĻŦāĻŋāĻā§āϝāĻžāϤ āϏāĻŽāϏā§āϝāĻžāĻāĻŋāϰ āύāĻžāĻŽ āĻāύā§āĻŽāĻĻāĻŋāύ āϏāĻŽāϏā§āϝāĻžāĨ¤
āϞāĻā§āώā§āϝ āĻāϰ āĻāύā§āĻŽāĻĻāĻŋāύā§āϰ āϏāĻŽāϏā§āϝāĻžāϰ āϏāĻŽāĻžāϧāĻžāύ āĻĨā§āĻā§ āĻāĻāĻž āĻŦāϞāĻž āϝāĻžā§ āϝā§, \(0\) āĻĨā§āĻā§ \(N-1\) āĻāϰ āĻŽāĻžāĻā§ \(m\) āϏāĻāĻā§āϝāĻž āύāĻŋāϞ⧠āĻā§āύ āĻāĻāĻāĻŋ āϏāĻāĻā§āϝāĻž āĻ
āύā§āϤāϤ āĻĻā§āĻāĻŦāĻžāϰ āύā§āĻā§āĻžāϰ āϏāĻŽā§āĻāĻžāĻŦāύāĻž \(1-e^{-\frac{m^2}{2N}}\).