有限幾何

一個有限射影幾何包含著由點P、q、…組成的有限集以及由的子集L、M、……組成的子集簇，這些子集稱為 線，並且這些子集滿足公理(i)一(iv)(若，我們稱P在L上或L通過P)。

(i) 通過任意兩不同的點P和q存在唯一的一條線(用(Pq)表示)。

(ii) 每條線至少包含3點。

(iii) 若不同的線L，M有公共點P，且若q，r為L上不等於P的點，及s，t為M上不等於P的點，則線(qt)和(rs)也有一公共點(看圖1)。

(iv) 對任意點P至少存在兩條不含P的線，而對任意線L至少存在兩個不在L上的點。

(v) 若P，q是S的不同的點則S包含線(Pq)上所有的點。

子空間的實例就是內的點和線以及自身。超平面H是最大的正規子空間，所以是唯一的完全包含H的子空間。

定義 從一射影幾何的子空間中去掉一固定的超平面H(叫做在無窮遠處的超平面)的點就得到一仿射或歐幾里德幾何。所形成的那些集都叫做仿射幾何的子空間。

在一射影幾何或仿射幾何中的一點集t，若對一切，則X不屬於包含的最小子空間，T叫做獨立的。例如，任何不在一線上的三點啤做獨立的。如果 r 是在子空間S中獨立點的最大集的尺度，S的維數是。特別地，若 這就定義了射影幾何的維數。

射影幾何PG(m，q) 射影幾何和仿射幾何中最重要的是從有限域得到的那些情況。

設GF(q)為一有限域且假定.的點以非0的重

表示，並且規定

和

代表相同的點，這裡為GF(q)的任意非0元。這些叫做點的齊次坐標。存在個非0的重而每點出現次，所以在中點的數目為。

通過兩不同點和的線由點

構成，這裡均不為0。因為對於，存在種選擇而每點在上式中出現次，一線包含點。

明顯地滿足公理(i)，(ii)。

作為有限域的一個應用，下面介紹有限幾何的概念。

定義1 設F是有限域，仿射平面AP(F)由下列兩個集合組成：

① 點集，

② 直線集 。

不難證明仿射平面AP(F)具有普通歐幾里得平面的性質：

① 過兩個不同的點只能作一條直線；

② 過一直線外的點P只能作一條直線與不相交。

由於AP(F)是定義在有限域上，因而P與L都是有限集合，且有以下計數定理。

定理1 設F是有限域且，AP(F)是F上的仿射平面，則有

①

②

③ 每條直線恰通過n個點；

④ 每個點恰在條直線上。

有限域理論在組合設計中有很好的應用。

有一種密碼系統是利用離散橢圓曲線進行編碼的，那麼什麼是橢圓曲線呢？我們先從實平面上的橢圓曲線說起，設a，b為實數，實平面上的曲線方程的圖形是以x軸為對稱軸的曲線，稱為 橢圓曲線(elliptic curve)．根據判別式的三種情況：和，橢圓曲線有三種類型。例如，方程，曲線由兩部分組成，在左半平面是一個類似於橢圓的一條封閉曲線，而右半平面是一條不封閉的趨向無窮的曲線。

類似，我們可以在有限幾何中研究橢圓曲線，它的定義如下。

定義2 設為素數，有限域且，則滿足同餘式的點的集合E稱為F上的 離散橢圓曲線(discrete elliptic curve)．並假定E中有一個特殊點O。在E中定義加法如下：設，則

其中定義。

上面式子中的運算均為mod p的運算。

可以證明 是可換群．元素的逆元為。

各種形式的同餘方程在密碼學中有很多應用，對於指數是未知數的同餘方程，就是所謂離散對數(discrete logarithm)問題：

定義3 設為素數，是一個本原元，，求整數滿足

x存在且惟一的，稱x為的以為底的 離散對數，並記作。

首先我們看一下離散對數的存在惟一性．這是因為是一個本原元，它是的生成元，所以均有使.若有J，則由得，因而，在範圍內是惟一確定的。

我們更關心的是如何計算離散對數．由於是在有限域上計算離散對數，自然會想到把所有的冪 都計算出來，從而找出所對應的x。