素数定理对不超过 $x$ 的素数个数给出了怎样的渐近估计？
What asymptotic estimate does the prime number theorem give for the count of primes not exceeding $x$?
记 $\pi(x)$ 为不超过 $x$ 的素数个数，素数定理断言 $\pi(x)\sim x/\ln x$，即 $\lim_{x\to\infty}\pi(x)\ln x/x=1$。等价于第 $n$ 个素数渐近为 $n\ln n$。该结果由 Hadamard 与 de la Vallee Poussin 于 1896 年独立证明。
Let $\pi(x)$ be the number of primes not exceeding $x$; the prime number theorem states $\pi(x)\sim x/\ln x$, i.e. $\lim_{x\to\infty}\pi(x)\ln x/x=1$. Equivalently the $n$-th prime is asymptotic to $n\ln n$. It was proved independently by Hadamard and de la Vallee Poussin in 1896.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Apostol《Introduction to Analytic Number Theory》（Springer，UTM 丛书）素数定理章
Apostol, Introduction to Analytic Number Theory, Springer (UTM), chapter on the prime number theorem
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780387901633 (1998)
#素数定理 #素数计数函数 #渐近
RSA 加密的安全性建立在哪个数论难题之上？
On which number-theoretic hardness problem does RSA encryption base its security?
RSA 依赖大整数分解的困难性：公钥含模数 $N=pq$（$p,q$ 为大素数）与公钥指数 $e$，私钥含 $d$ 使 $ed\equiv 1\pmod{\varphi(N)}$。由 $N$ 恢复 $\varphi(N)$ 等价于分解 $N$，而目前尚无多项式时间算法，故体系安全。
RSA relies on the hardness of factoring large integers: the public key has modulus $N=pq$ (with large primes $p,q$) and exponent $e$, while the private key has $d$ with $ed\equiv 1\pmod{\varphi(N)}$. Recovering $\varphi(N)$ from $N$ is equivalent to factoring $N$, for which no polynomial-time algorithm is known.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Menezes、van Oorschot、Vanstone《Handbook of Applied Cryptography》（CRC Press）
Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-1-4398-2191-6 (CRC Press)
#RSA #大整数分解 #模幂
为何模幂运算常被视为密码学中的单向函数？
Why is modular exponentiation often regarded as a one-way function in cryptography?
计算 $b=a^x\bmod N$ 可借快速幂在多项式时间内完成，但由 $b$ 反求指数 $x$（离散对数问题）在适当选择的群中被认为是困难的。这种易正向、难逆向的非对称性正是 Diffie-Hellman 与 DSA 等协议的根基。
Computing $b=a^x\bmod N$ is feasible in polynomial time via fast exponentiation, but recovering the exponent $x$ from $b$ (the discrete logarithm problem) is believed hard in suitably chosen groups. This easy-forward, hard-inverse asymmetry underlies Diffie-Hellman and DSA.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Menezes、van Oorschot、Vanstone《Handbook of Applied Cryptography》（CRC Press）
Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-1-4398-2191-6 (CRC Press)
#单向函数 #离散对数 #模幂
费马小定理对素数模下的幂运算给出了什么结论？
What does Fermat's little theorem say about exponentiation modulo a prime?
若 $p$ 为素数且整数 $a$ 不被 $p$ 整除，则 $a^{p-1}\equiv 1\pmod p$。等价地，对任意 $a$ 有 $a^p\equiv a\pmod p$。它是 RSA 等公钥算法的数论基础之一。
If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv 1\pmod p$. Equivalently, $a^p\equiv a\pmod p$ for all integers $a$. It is one of the number-theoretic foundations of public-key schemes such as RSA.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《初等数论》
American Mathematical Society (AMS), Elementary Number Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787301216125（豆瓣书目条目: 初等数论）
#费马小定理 #模运算 #同余
欧拉定理如何把费马小定理推广到合数模数？
How does Euler's theorem generalize Fermat's little theorem to composite moduli?
对任意与 $n$ 互素的 $a$，欧拉定理给出 $a^{\varphi(n)}\equiv 1\pmod n$，其中 $\varphi(n)$ 为欧拉函数（不超过 $n$ 且与 $n$ 互素的正整数个数）。当 $n$ 为素数时 $\varphi(n)=n-1$，即退化为费马小定理。
For any $a$ coprime to $n$, Euler's theorem gives $a^{\varphi(n)}\equiv 1\pmod n$, where $\varphi(n)$ counts integers up to $n$ coprime to $n$. When $n$ is prime, $\varphi(n)=n-1$, recovering Fermat's little theorem.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《初等数论》
American Mathematical Society (AMS), Elementary Number Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787301216125（豆瓣书目条目: 初等数论）
#欧拉定理 #欧拉函数 #互素
如何用扩展欧几里得算法求模 $m$ 下 $a$ 的乘法逆元？
How does the extended Euclidean algorithm find the modular multiplicative inverse of $a$ modulo $m$?
当 $\gcd(a,m)=1$ 时，扩展欧几里得算法给出整数 $x,y$ 使 $ax+my=\gcd(a,m)=1$，于是 $ax\equiv 1\pmod m$，故 $x\bmod m$ 即为 $a$ 在模 $m$ 下的逆元。若 $\gcd(a,m)\neq1$ 则逆元不存在。
When $\gcd(a,m)=1$, the extended Euclidean algorithm produces integers $x,y$ with $ax+my=\gcd(a,m)=1$, so $ax\equiv 1\pmod m$ and $x\bmod m$ is the inverse of $a$ modulo $m$. If $\gcd(a,m)\neq1$ no inverse exists.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《初等数论》
American Mathematical Society (AMS), Elementary Number Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787301216125（豆瓣书目条目: 初等数论）
#模逆元 #扩展欧几里得 #最大公约数
欧几里得是如何证明素数有无穷多个的？
How did Euclid prove that there are infinitely many prime numbers?
假设素数只有有限个 $p_1,\dots,p_n$，考虑 $N=p_1p_2\cdots p_n+1$。$N$ 不被任一 $p_i$ 整除，故 $N$ 有新的素因子或自身为素数，与假设矛盾，因此素数无穷多。
Suppose primes are finitely many $p_1,\dots,p_n$, and form $N=p_1p_2\cdots p_n+1$. None of the $p_i$ divides $N$, so $N$ has a new prime factor or is itself prime, contradicting finiteness; hence there are infinitely many primes.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《初等数论》
American Mathematical Society (AMS), Elementary Number Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787301216125（豆瓣书目条目: 初等数论）
#素数 #欧几里得 #反证法
中国剩余定理解决了怎样的同余方程组问题？
What kind of simultaneous congruences does the Chinese remainder theorem solve?
若模数 $m_1,\dots,m_k$ 两两互素，则对任意余数 $a_i$，方程组 $x\equiv a_i\pmod{m_i}$ 在模 $M=m_1\cdots m_k$ 下有唯一解。它把大模数运算拆解为若干小模数，广泛用于 CRT 加速与秘密分享。
If the moduli $m_1,\dots,m_k$ are pairwise coprime, the system $x\equiv a_i\pmod{m_i}$ has a unique solution modulo $M=m_1\cdots m_k$ for any remainders $a_i$. It splits computations into smaller moduli, used in CRT speedups and secret sharing.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《初等数论》
American Mathematical Society (AMS), Elementary Number Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787301216125（豆瓣书目条目: 初等数论）
#中国剩余定理 #同余 #互素