某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有 n 口油井的油田。從每口油井都要有一條輸油管道沿最短路經(或南或北)與主管道相連。如果給定 n口油井的位置,即它們的 x 坐標（東西向）和 y 坐標（南北向）,應如何確定主管道的最優位置,即使各油井到主管道之間的輸油管道長度總和最小的位置?證明可在線性時間內確定主管道的最優位置,使得給定n口油井的位置,編程計算各油井到主管道之間的輸油管道最小長度總和。
ElGamal算法既能用于數據加密也能用于數字簽名，其安全性依賴于計算有限域上離散對數這一難題。
密鑰對產生辦法。首先選擇一個素數p，兩個隨機數, g 和x，g, x < p, 計算 y = g^x ( mod p )，則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶共享。
ElGamal用于數字簽名。被簽信息為M，首先選擇一個
