個人對RSA加密算法有效性的理解

之前我對RSA加密算法一直一知半解。從小到大斷斷續續看了不少科普文章，最近一次學的是在得到app上買的卓克的密碼學課程，仍然沒完全理解到位。科普文章爲了讓讀者容易理解，用語有時過於簡略，並可能會因此導致硬傷。卓克課程裏的“模運算不能逆運算”就是課程裏讓人誤解的一個硬傷。

模运算怎么就是单向函数了呢？
我们可以看看刚才的例子：11×9=8 (mod13) 这个算式，从左往右推可以推出来，而且结果是唯一的。但是从右往左呢，就相当于问你“在模等于13的体系中，什么数×9以后余数为8”。这个问题能不能逆运算呢？答案是不能。
当然，不一定模运算就一定没有乘法逆。当模比较小的时候，可以逆运算的数字比较多；但是当模大到一定程度时，就完全没有逆运算了。这是由数学决定的。

爲了完全搞清楚RSA的原理，我仔細讀了英文Wiki的條目。其實很多條目的中文版都不夠清楚，切換到英文版就清晰多了。

首先搞清楚的是對大數運算的算法時間複雜度的基礎值n的含義。如果以二進制表示的大數N有n位數，則N ~ 2^n。回想一下筆算的過程，就可以知道通常的時間複雜度是對長度n而言，而不是對大數N本身而言的。加減法的時間複雜度是O(n)，乘除法的時間複雜度是O(n^2)。相比大數N本身，只是其對數的多項式函數。換句話說對大數的這些運算需要的時間只是把大數寫下來和存儲的時間的多項式函數，而不是跟數出這個數的時間成正比。如無特別說明，下文的時間複雜度都是對長度n而言的。

由於加減乘除的時間複雜度都是長度n的多項式函數。可以想像很多比較基礎的函數也不會差太多，包括乘方和模逆。而所謂“非對稱加密”，就是加密過程能用多項式時間完成，而破解過程（比如根據加密密鑰推算解密密鑰）需要N的至少是開方的時間（從而還是長度n的指數時間）的加密解密算法。

以下是RSA的加密解密和破解每個步驟的時間複雜度：

密鑰產生

1. 隨意選擇兩個大的不相等的素數p和q，計算N = pq。素數的選取是隨機的。有高效的素性測試算法在多項式時間內檢驗素性。
2. 根據歐拉函數計算出r = φ(N) = (p-1)(q-1)。根據筆算法可得出多項式時間。（更安全起見應該用卡邁克爾函數，不過此處僅討論基本原理，略去這個細節。）
3. 選擇一個小於r的整數e，使e與r互質。並求得e關於r的模逆元，命名為d（求d令ed ≡ 1 (mod r)，注意不是mod N）。模逆元可以用擴展歐幾里德算法（輾轉相除發）求得，用多項式時間。

加密和解密

1. 信息m被加密爲c ≡ m^e (mod N)。雖然e很可能接近N的量級，這個模冪運算並不需要與e成正比的時間。把e用二進制表示出來後，可以用不斷平方保存結果的方式，在e的長度（也就是n）的多項式時間內完成。
2. 解密是m ≡ c^d (mod N)。同理。

破解

1. 由於p, q和r = φ(N)的記錄都已被銷毀，破解等同要從N = pq求出φ(N) = (p-1)(q-1)，這又等同於把大數N做質因數分解。目前的經典計算機下的算法都需要其長度n的指數時間才能做到。

從群論更高的觀點來看：

1. 模加法群都是N階循環群。雖然循環群根據其階的質因數分解有些不同性質，但都在相對好把握的範圍內。
2. 模乘法群φ(N)階，雖然也一定是Abel群（乘法可交換），但其構成就比較複雜。實際上，僅僅是算出這個群的階就足夠困難（從N = pq求出φ(N) = (p-1)(q-1)）。

1. 乘法是加法的疊加，作爲乘法逆運算的模逆，其複雜度與模加法群的複雜度相當。乘法逆運算的結果與加法循環次數相關，而模加法群的階就是N自己。
2. 乘方是乘法的疊加，作爲乘方逆運算的離散對數，其複雜度與模乘法群的複雜度相當。RSA的問題也可以看成是離散對數：問明文對密文的離散對數值是多少，想要的答案就是解密密鑰d。乘方逆運算的結果與乘法群循環次數相關，而模乘法群的階是φ(N)，最大循環次數是φ(N) / 2（卡邁克爾函數）。

我以前總把RSA錯記成乘法取模，有了群論觀點後就不會記錯了。

淺談槓桿投資

先學院派一下：有個問題雖然是簡單的數學題，但沒實際計算過的話不是很容易得到正確結論。用槓桿通常會有借貸成本。假設借貸成本是零，在不調倉的前提下，槓桿投資的收益等於槓桿倍數。但是這個收益率只能按相對於初始本金的比率累加，不能按複利累乘，因為槓桿率實際上是隨著資產價值變化而變化的。市面上有槓桿ETF，比如2倍或3倍，也有2倍或3倍做空。資產變化後，每個週期（一般是一天或一月）調倉(rebalance)使得槓桿倍數保持不變。在不考慮槓桿借貸成本的前提下，調倉的行為也會讓槓桿ETF產生損耗。標的先漲後跌回到原點，無論做多還是做空的槓桿ETF都是虧的。

網上的說明文大部分都不到位，這裡用理論計算一下。

假設標的的價值在一個週期從1變到a，下一個週期再回到1。追蹤標的的槓桿ETF倍率是x，那麼它的收益是

[1+x(a-1)][1+x(1/a-1)] – 1 = (a+1/a-2)x(1-x)

只要a不是1（對應標的有漲跌），第一個係數恆為正。有趣的是x(1-x)這部分，在x<0或x>1時為負，也就是說需要借貸的槓桿投資都會產生損耗。做多時超過1倍槓桿需要借貸，做空時無論多少倍都要借貸。在0和1之間時實際上它是正值。0.5倍槓桿是什麼意思呢？實際上是一種“反槓桿”，不僅不借貸，自己還留著一半現金池，按價值變化動態調倉。在忽略交易成本時居然可以做到標的波動回原點而自己賺錢！當然，標的上漲時賺的錢也只是一半多一點。

槓桿ETF會帶來損耗，而自用槓桿不調倉的話，在對數效用下，槓桿對損失的放大作用一定大於收益。最理想的槓桿投資是隨時rebalance保持槓桿倍數，這樣線性槓桿就變成幾何槓桿。3倍槓桿下漲20%對應槓桿投資賺72.8%（1.2^3-1），跌20%對應槓桿投資賠48.8%（1-0.8^3）。賺的時候比線性槓桿多，賠的時候比線性槓桿少。可能由於槓桿賠很多，但理論上永遠不會爆倉。只可惜這種操作會由於交易成本太高而無法實現。

回到實際投資可用的槓桿。槓桿可以理解成對利率市場的投資或套利，自然也有低買高賣一說。IB的港幣和美元融資利率非常低，同時有些股票常年穩定派發高股息，那麼投資它們收息就是可行的方案。還有一種情況是有資金在較高利息的固定收益類投資，比如保險或各類低風險人民幣投資，又想把更多資產分配到股票。贖回這些投資要很大代價，於是用低息的槓桿也可以做到不用贖回而達到投資重分配的效果。只不過最終平倉線還是完全看在經紀商的那部分資產。

雖然使用槓桿時會有追加保證金提醒，會有平倉線，但在股價變化過快或流動性缺失時仍然可能導致負資產。正規的經紀商是不會為客戶的債務兜底的。在流動性好的市場，這種情況不容易發生。而對A股來說，停牌幾個月後復牌連續一字跌停的情況不時出現。

其實保險市場也是有槓桿的。香港AIA有儲蓄型壽險允許槓桿。保險派息4-5%，銀行收的貸款利息2-3%。加槓桿後保險年化收益可以達到10%以上。但是起投門檻很高，而且要十年以上才能看出效果。主要的風險在於利率的變化。

總的來說，“不是完全不能用，而是算清楚再用也不遲”。

Calculating Dates Difference by yyyymmdd

It is an interesting question to calculate the day of the week by yyyymmdd. A straight forward method is calculating the cumulative days (mod 7). The yyyy part is simple. But the mmdd part needs counting cumulative days from January to the month before the current month. One may use a table to do this. Truly there is a better formula called Zeller’s congruence. This article is to explain it and promote it to a formula calculating dates difference.

The key of Zeller’s congruence is viewing January and February as the 13th and 14th months of the last year. One may say, there is either 28 or 29 days in February, so putting it in the last of a year will remove the difficulty of counting days. But there another important reason. Let’s list the number of days from March to February:

 

Number of days in each month

Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec	Jan	Feb
31	30	31	30	31	31	30	31	30	31	31	28 or 29

Do you find anything interesting? Yes, it is periodic! The pattern “31, 30, 31, 30, 31” repeats for first and second 5 values, and also for the 11th one.

So we may think of some floored linear function to calculate the cumulative days. Like

where mm is the month and for March, .

In a period, there is 30.6 days in a month on average, so . And we want . So . Actually b can be any value in the range of . The formula now becomes:

You may verify this formula month by month.

The cumulative days by yyyy and dd are simple. So the final formula, number of days from 00010101 to yyyymmdd (including the first and last days), for Gregorian calendar is:

One can easily calculate the dates difference between two given yyyymmdd’s. And of course Zeller’s Congruence is based on this formula.

[学术文备份]多少次才能刷出零失误？

原文于2008年9月15日发表于www.doujinstg.cn。

如何高效地练成表演效果呢？从视觉效果和实际难度的角度我们会想到选择一个前者与后者比值尽可能大的项目来表演。这点此处并不打算作过多讨论，而是单从练习和表演本身符合的概率统计规律来进行分析。

问题：多少次才能刷出零失误？

通常的计算方法是把流程分成若干小块，分别统计成功率后相乘，再用1去减。这里介绍的方法让整个模型的参数少至１个：
我们把流程中的每一个细节都分割开来，分得越细越好。譬如原来统计“完美擦完正直者之死”，在这里变成“正直者之死擦弹每一步移动成功率”；原来统计“前半某个段消弹不失误的成功率”，在这里变成“每一步走位都恰到好处和每一次攻击分别的成功率”。这样统计的特点是，每一个细节的成功率无限趋近于1（或者说失误率无限趋近于0），而细节数趋近于无穷大，但全程的平均失误次数是一个有限值。而我们关心的是，刷出零失误的成功率是多少？

用了这种统计方法后，其概率分布符合“泊松分布”的模型：

P(k)=n^k*exp(-n)/k!

其中P(k)表示一次全流程挑战中发生k次失误的概率，n表示平均失误次数。

实际挑战中每个细节的难度和成功率总是各不相同的，有些区段失误密度大，有些区段失误密度小。但只要总数足够大，技术细节本身之间的差异在这里并不重要。成功率仅仅跟“全程平均失误次数”有联系。

在上面式子中，把0代入，可以得到零失误的概率：

P(0)=exp(-n)

一般来说，若平均失误次数是3，则零失误的成功率是1/20；若平均失误次数是5，则大约要150局才能刷出一局零失误。如果你时不时能打出有三两个失误的成绩，但零失误就是很难打出来，那你并不孤单。

由此可见，对于要用于表演的流程，从提高成功率来看，最关键的处理在于降低全程的平均失误次数。

在降低失误率的战斗中，会遇到两个界限，分别是对难度的生理极限挑战和对复杂度的大脑处理能力挑战（ref）。生理极限因人而异，但总体差别并不大（譬如对抢跑的硬性规定是起跑反应时间小于0.1秒），而且提高的过程非常漫长。而大脑处理能力的提高不仅要相对迅速，其极限亦非我们可以预料得到的。

拿道中前半消弹和正直者之死擦弹作比较：
前半消弹刚开始练时也常常20局连续推掉，但那是因为原本有能力固定下来的操作没固定好。通过反复比较自己和他人录像操作的差异，乃至用上截图和视频片段的手段，大部分人是可以练到很高的成功率的。因为，由生理极限带来的操作波动通常并不影响成败。
不过正直者之死擦弹就不一样了。表面上看它完全是很有节奏的模式化操作，然而事实上每一次移动时机和幅度的微小差异都会导致下一次必须作出相应的调整。因此它的成功率很大程度上受限于生理极限，并且在达到极限后不可能在短时间内通过反复单一的练习得到显著提高。

如果Extra全程是表演项目的话，正直者之死擦弹擦到结束一般来说不应列入其中，因为它大大提高了全程的平均失误次数。不仅如此，东方高难度中所有危险的擦弹动作都是需要慎重考虑的。假设投入同样的大脑处理练习，可以把一个通常人成功率为40%的项目A成功率提高到80%，或者把一个通常人成功率为75%的项目B成功率提高到95%。而以项目A的视觉效果并不值得为此冒如此大的风险时，可以优先考虑项目B。

表演并不是奇迹，而是计算和重现（ref已不可考）。因此自己对流程的控制力越大就越好。Boss的攻击分为很多轮，对观众来说是一波未平一波又起，对表演者来说却提供了很多次refresh的机会。当表演计划为每文明用语击尽快击破时，打法很快就能固定下来，实战时生理波动引起的效应还未累积到一定程度就随着Boss的一声爆炸而清零，表演者马上可以喘一口气进而准备下一回合战斗。鉴于此，擦弹擦到击破也是不错的选择，尤其像徐福时空这样的符，擦到击破并不难，而且能多几千万的分数，又有很好的视觉效果。不过若要擦到结束就要三思而后行了，生理波动80多秒的累积是很可怕的，它导致失误速率（失误率的时间密度）随着累积效应而逐渐变大。最后在什么时候打爆呢？1秒还是2秒？Oh no，这个未固定下来的战术又是一个增加失误率的因素。

据此按允许失误次数为1次估算一下，组别Extra全程稳定表演成绩22亿是个虽然困难但还有方法去做的目标，再往上就不现实了。

这些是关于“如何高效地练成表演效果”的小结。

一元代数方程可解性的导读（未完成）

在一元三次和四次方程的求根公式被找出来以后，很多人致力于寻求五次以上代数方程的解。该问题一度成为热门的题目，但寻找根式解的尝试无一例外以失败告终。事实上，五次以上代数方程不存在一般的根式解，而证明它所用到的工具当时尚未被开发出来。直到19世纪初，这个问题才由Abel作出了重要突破，并由Galios圆满地解决。现在回过头来看，寻求低次方程解的配方技巧与一般的可解性研究存在着本质的不同。后者需要从域(field)扩张及其自同构的角度去审视，并借助群(group)这个重要的工具方能解决。现在，在很多近世代数教科书中都把一元代数方程可解性作为经典题目来介绍。只要群环域等概念积累得足够多，问题的解就水到渠成了。

本文打算讲述的内容大都不是严格的证明。严格的证明可以在很多代数书中找到。只不过，基于一般代数教学的课本会介绍很多额外的概念。如果读者只希望了解方程的可解性这一个问题，为了把最后的证明看懂，可能需要啃前面的很多概念。平心而论，笔者自己也不敢说把证明链中的每一个细节都真正搞明白了。由于笔者自己没有找到以方程可解性为主线的书籍，特写此文以作导读，希望有兴趣的读者可以在本文的指引下对这道数学名题有更深刻的了解。当然，对近世代数中群、域等基本概念的了解还是必需的。

零、开始问题之前

熟悉代数学的读者对群的概念一定不会陌生，群的定义在很多教科书里也有介绍。笔者打算说的是，这个群的定义其实过强了。最初群的定义可能是以一种较弱的表述出现的，我们试着以这样的方式去定义群：

定义 设[tex]G[/tex]是一个非空集合，如果在[tex]G[/tex]上定义了一个代数运算，通常称为乘法，记作[tex]ab[/tex]，并且它适合下列条件：

1、对于[tex]G[/tex]中任意元素[tex]a[/tex]、[tex]b[/tex]、[tex]c[/tex]，有

[tex](ab)c=a(bc)[/tex]（结合律）；

2、[tex]G[/tex]中有一个左单位元[tex]e_1[/tex]，对任意[tex]a{\in}G[/tex]有

[tex]e_1a=a[/tex]，

又有一个右单位元[tex]e_2[/tex]，对任意[tex]a{\in}G[/tex]有

[tex]ae_2=a[/tex]。

到这里先暂停一下，我们立即可以看出左右单位元其实是同一个，因为：

[tex]e_1=e_1e_2=e_2[/tex]。

于是它们可以合称为单位元[tex]e[/tex]。

3、对于[tex]G[/tex]中任一元素[tex]a[/tex]，都有[tex]G[/tex]中一个左逆元[tex]a_1^{-1}[/tex]，使得

[tex]a_1^{-1}a=e[/tex]，

又有一个右逆元[tex]a_2^{-1}[/tex]，使得

[tex]aa_2^{-1}=e[/tex]。

我们马上可以看到，同一元素的左右逆元也必定是同一个：

[tex]a_1^{-1}=a_1^{-1}aa_2^{-1}=a_2^{-1}[/tex]。

于是它们可以统称为[tex]a[/tex]的逆元。

满足上述定义的群[tex]G[/tex]（及其运算）称为一个群(group)。我们知道，群的乘法不一定是可交换的。但从上面的过程可以知道，单位元的乘法一定可交换，任一元素及其逆元的乘法也必定可交换。这说明群具有非常良好的内禀属性，不仅群本身有很高的研究价值，它更可作为解决其它领域问题的有力工具。

一、代数方程求根问题的提法

在初等的书上这个问题一般有两种提法“一般五次以上代数方程无求根公式”和“一般五次以上代数方程无根式解”。前一个提法不严格，因为任何一个方程抽象的“求根公式”总是存在的。后一种提法特指形如[tex]\sqrt[n]{a}[/tex]的根式，或者说形如[tex]x^n-a=0[/tex]这种方程的解。二次方程求根公式的推导大家都会，可以再看看三次方程和四次方程的根式解是如何找出的。如果一个代数方程能通过一系列的变形，约化成各种中间阶段的方程，而这些方程全部具备[tex]x^n-a=0[/tex]的形式，那我们就说这个方程有根式解，反之亦然。从五次方程的约化中我们可以看到，借助四次以下方程能把五次方程化成的最简形式是[tex]x^5+ax+b=0[/tex]。把[tex]\sqrt[5]{a}[/tex]考虑进去，最后只能化成[tex]x^5+x+b’=0[/tex]。因而一般的五次方程没有根式解。

到这里，有两点可以探讨一下。第一点，根式到底意味着什么。譬如，给我们一个[tex]\sqrt{2}[/tex]，除了知道它的近似值是1.414以外，还能给我们什么信息，跟sin1又有什么本质区别？从代数的角度来说，根式的意义不在于我们一见到它就能扔给计算机求出近似值，而在于它所具备的代数性质。[tex](\sqrt{2})^2=2[/tex]便是[tex]\sqrt{2}[/tex]所具备的基本性质，从其定义而来的。除此之外我们还知道它是第一个被证明的无理数，其证明至今仍是经典。而对于sin1是超越数，要给出一个漂亮的spiecific证明并不容易。最后，代数学可以利用[tex]a+b\sqrt{2}[/tex]，其中[tex]a,b{\in}Q[/tex]（有理数域），来构造[tex]Q[/tex]的域扩张（看过代数书的同学会知道，这实际上是多项式[tex]x^2-2=0[/tex]在[tex]Q[/tex]上的分裂域）。在这里，[tex]\sqrt{2}[/tex]可以代表2的任何一个平方根。如果我们作[tex]\sqrt{2}\to-\sqrt{2}[/tex]，便是这个域扩张的一个[tex]Q-[/tex]自同构——限定在[tex]Q[/tex]上保持不变的自同构。而自同构群就是最简单的2阶循环群[tex]Z_2[/tex]。也许正是因为根式的代数性质最好把握，数学家们才如此热衷地追求根式解。如果我们可以定义[tex]x^5+x+t=0[/tex]的某个解作为[tex]t[/tex]的函数[tex]f(t)[/tex]，那么五次方程的解同样可以由[tex]f(t)[/tex]和五次以下的根式表出。只不过它在应用上给人的感觉可能跟一般的超越函数没有区别。

第二点，既然这里我们讨论纯粹的代数，那还有一点可能是读者会感觉奇怪的。仅二次方程的根式解包含唯一一类根式。三、四次方程的求解都分别要借助二、三次方程来完成。解三次方程会出现二次根式并不奇怪，因为[tex]x^3-1=0[/tex]的一对共轭虚根，即三次单位根[tex]\omega,\bar{\omega}=(-1\pm\sqrt{3}i)/2[/tex]就含有二次根式。而[tex]x^4-1=0[/tex]的解是[tex]{\pm}1[/tex]和[tex]{\pm}i[/tex]，那么四次方程的求解能否只用平方根和四次方根（平方根可以看作特殊的四次方根）表出呢？答案是不能。
读者在高中学习立体几何时，一定对正方体内嵌正四面体的图像很熟悉。虽然正方体的每个角都是直角，每个面都是正方形，但它却不乏以3为因子性质：除了内嵌正四面体，它的最大俯视图和最大截面图都是正六边形。其中最有意思的是正方体的对称性群了。这个群里既有4阶元，表明正方体以对面面心连线为轴，旋转[tex]\pi/2[/tex]可以与自己重合，这样的轴在晶体学里称为四重对称轴。其实正方体还有三重对称轴，就是对角顶点的连线。熟悉内嵌正四面体图像的读者马上可以想到，绕这个轴旋转[tex]2\pi/3[/tex]也可以与自己重合。这个例子跟我们的主题并没有什么必然的逻辑关系，它只是用来说明以4为“特征值”的代数对象里也可以包含特征为3的子对象。事实上，一般四次方程的Galios群是4阶置换群[tex]S_4[/tex]，而3阶置换群[tex]S_3[/tex]是它的一个子群。

二、群的架构方式——单群与可解群之概念

有了集合，便有了子集概念。有了群，自然会有相应的子群概念。有限群的子群的阶一定能整除母群的阶，Sylow定理表明了某些特别阶子群的存在性。不过，对群结构的研究起更关键作用的是所谓的正规子群(normal subgroup)。为了说明这个概念，我们先看一种简单的例子：

Abel群是较为简单的一种群。4阶群有2种，都是Abel群，代表是[tex]Z_4[/tex]和[tex]Z_2{\times}Z_2[/tex]。6阶Abel群只有一种，因为[tex]Z_6=Z_2{\times}Z_3[/tex]。可以证明，所有Abel群都可以分解成素数幂阶循环群的直积。

但是对一般的群来说，乘法并不一定可交换。如果要求直积的形式，则分解形式十分有限。这时我们可以尝试用同态的方式去研究群结构，通俗地说就是投影。同态的核一定是一个子群，反之任给一个子群不一定能成为同态核。这种可以成为同态核的子群就是正规子群。同时，左右陪集合一，成为一个群，即商群。群同态基本定理表明，同态核唯一决定了同态像，它们共同给出了原来群的架构。

没有非平凡正规子群的群称为单群。单群之于群，正如素数之于整数，前者都是后者的基本架构。不过，单群本身也远没有这么简单。

对非单群[tex]G[/tex]来说，可以构造所谓的合成群列[tex]G{\triangleright}G_1{\triangleright}G_2{\triangleright}\cdots\{e\}[/tex]。其中群列每一个都是前一个的正规子群，而商因子[tex]G_i/G_{i+1}[/tex]皆为单群。并且可以证明，所有商因子在交换的意义下唯一。如果这些商因子都是Abel群（从而也必定是素数阶循环群），这样的群称为可解群，否则称之为不可解群。至于为什么叫这个名字，因为群论最早就是用来研究代数方程根式解的，而可解群与根式解的存在性有着直接的联系。后面我们会看到，Galois证明了一个数域的多项式存在根式解当且仅当其分裂域的自同构群（Galios群）为可解群。

十分简单明了的勾股定理证明

Polya的书就是不同凡响啊，在其《数学与猜想》第一卷《数学中的归纳和类比》中引用了Euclid对勾股定理的一个证明，其思路是这样的：

(1)我们来考察一个直角三角形，它的边分别是，其中是斜边。我们需要证明

(A)

(2)这个式子表明，我们可以以直角三角形三边为边作正方形，只要证明直角边上两个正方形的面积和等于斜边上的即可。

(3)其实这个式子也可以变形为

(B)

也就是说，对任何相似形这个结论都等价。只要证明了勾股定理，就表明对任何相似形都成立。逆转过来看，只要对任一相似形证明等式的成立，也就证明了勾股定理。

现在看上面这个图，图中隐藏了三个相似三角形，它们分别可以看做从直角三角形三边往里作出的相似形。又由于两个小三角形加起来等于那一个大三角形，因而勾股定理得证。

统领正逆概率的Bayes公式

最初接触Bayes公式时是在随手翻看数学手册时看到的，不过并未加以留意。正式的接触是在一次渔场的概率学术帖中的讨论（很遗憾该帖子已经浮云了），在那场讨论中闪闪现学现用该公式并得出最后完整正确的结论。再后来有幸读到几篇关于该公式的文章，才发现它的内涵实在很深刻。特此拿出来分享一下。

我们先从朴素的例子讲起，暂时抛开概率论中的那些复杂的定义。假设在某个群体中，一个人患某种绝症的概率是0.01%。现在有一种很先进的检测手段可以检查是否患该绝症，但很可惜检验正确率还不是绝对的100%。如果患病的人被检出的概率达到98%，即100个患者中有98个呈阳性反应，其余2个呈阴性；此外未患病的人被误检的概率为1%，即100个健康人中有1个呈假阳性，其余99个为正常的阴性。现在有一人检查结果为阳性，问这个人患病的概率是多少？

要回答这个问题，可以用非常直观的计算。假设这个群体共有1亿人，那么患病的有1万人，其余9999万是健康人。这10000患者中会有9800人检查呈阳性，200呈假阴性。而9999万健康人中会有99万9900的假阳性，其余的9899万0100人是正常的阴性。现在我们不知道这个人是否患病，但知道检查的结果为阳性。那么计算方法就是比较9800的真阳性和99万9900的假阳性的比例。结论是检查结果为阳性，而实际会患病的概率是9800/(9800+999900)=0.97%，连1%都不到。顺便我们也可以比较一下200的假阴性和9899万0100的真阴性，结果是检查结果为阴性的人，仍有百万分之二的概率是患者。

这个例子抽象出来的结论就是著名的Bayes定理：

[tex]P(A|B)=\frac{P(B|A)P(A)}{P(B)}[/tex]

式中[tex]P(A)[/tex]和[tex]P(B)[/tex]分别是事件A和事件B的先验概率（prior probability），[tex]P(A|B)[/tex]是事件A对事件B的条件概率（conditional probability），具体来说就是在给定事件B发生的前提下，事件A也发生的概率。在实际使用中有时也可以称为似然概率（likelihood probability）。这个公式在计算逆向概率时十分有用。比如前面检查患病的例子，不是从患病与否推断检查结果的概率分布，而是从检查结果反推被检查者的状况，就是一个逆向概率问题，具体写出来就是：

被检查出阳性时患病的概率
=若患病会显阳性反应的概率*患病的概率/显阳性反应的概率
=真阳性率/总阳性率
=（患病率*患病检出率)/(患病率*患病检出率+不患病率*不患病假阳性率)

在这个例子中，虽然检测方法本身貌似很准确，真阳性率和真阴性率分别达到98%和99%，实际检测结果呈阳性的人患病概率还是很小。这是因为这里的逆向概率预测取决于假阳性的干扰，而假阳性不仅取决于方法本身的准确率，还取决于不患病的人群基数。虽然一个患病的人有很大概率被检出阳性，不患病的人以更大的概率不被误检，但被检出阳性的人实际患病的概率却很小。

如果我们把“患病”换成“有天赋”，把“检查结果呈阳性”换成“取得成功”，结论会如何？有天赋的人很大可能成功，没有天赋的人很难成功。但如果我们后验地观察到一位成功人士，他有天赋的可能性还是很小！

在文章[2]中，有这样一段话：

统计学家和贝叶斯学家有一个有趣的争论，统计学家说：我们让数据自己说话。言下之意就是要摒弃先验概率。而贝叶斯支持者则说：数据会有各种各样的偏差，而一个靠谱的先验概率则可以对这些随机噪音做到健壮。事实证明贝叶斯派胜利了，胜利的关键在于所谓先验概率其实也是经验统计的结果。

于是对“天赋”等概念也有类似结果。天赋即是一出生就有的，严格来说只有基于遗传和基因的分析才能给天赋的有无提供先验的支持。当然我们也常看到著名学者评论自己的同事时会用“天赋异禀”之类的词，这时候的意思是对这个人了解很透彻，从大量的事实细节归纳出这个结论。其实这时候他们想表达的意思是“这个人的能力信得过”，以后用人的时候可以作参考。至于其微观机制是否源于其生理基因，倒不是问题的重点。另一方面，如果基因工程发展下去，是不是可以逐渐揭开天赋之谜了？然而研究基因与表现联系的方法本身却正是大量的实验和数据统计。通过统计大量改变某个单独基因导致的后验结果，来反推其起作用的先验机制。研究中必然会遇到很多令人困惑的不一致，因而其结果只能表达为具有一定置信度的推测而不是确定的事实。就算生理基因的作用完全搞清楚了，那么背后更深刻的原理是什么？这又是一条无限的回溯链。读到这里应该不难明白了，先验和后验本身就是相对的概念，而Bayes公式的意义就在于给出了某一个环节中从先验过渡到后验的准确算法。只不过这个原本应该很清晰的逻辑，如果不去仔细考虑光靠直觉的话，得到的结果往往与事实相去甚远。

那么最后，闪闪本人属于什么类型呢？啊哈，这么重要的东西怎么可能公开谈论！

参考文献：

[1]. Bayes’ theorem – Wikipedia
[2]. 数学之美番外篇：平凡而又神奇的贝叶斯方法 作者：刘未鹏

《几何原本》中的几个经典数论问题

Euclid的《几何原本》中第七、八、九篇讲述的是数论，第十篇讨论不可公度量。其中的两数最大公因子求法、关于质数数量无限和[tex]\sqrt{2}[/tex]为无理数的证明在今天仍然是不朽的经典。

最大公因子的辗转相除法无疑是最具可操作性的的算法，而且如果要用计算机编程，这几乎是唯一的算法。证明质数数量无限所用的反证法同样包含了十分重要的思想。

比较有意思的是关于[tex]\sqrt{2}[/tex]为无理数的证明，它的成立实际上需要一个前提：每个自然数都能被唯一地分解成质因数的乘积，这个前提被称为“算术基本定理”。在自然数的结构下这是对的，但在另一些代数结构下却不一定对。譬如在加入了[tex]\sqrt{5}i[/tex]的环里，[tex]9[/tex]可以被分解成[tex]3\times3[/tex]或[tex](2+\sqrt{5}i)\times(2-\sqrt{5}i)[/tex]，而两者都不能再分下去了，因此分解方式不唯一。在这种代数结构里，“既约分数”的概念需要重新研究。而非整数方根是否仍为无理数？个人猜测是成立的，但证明会更加复杂。