獲取在扭曲 Edwards 擴展座標上的有限域上定義的橢圓曲線的點

我正在開發一個加密庫，我需要執行一些測試以實現：

• 點加法。
• 點減法。
• 點加倍。
• 標量 Mul 點。

這些操作是在 Twisted Edwards 擴展座標 so (X, Y, Z, T) 上執行的。

問題是除了身份點之外，(0,1,1,0)我很難獲得其他點來測試操作。

所以是曲線的方程：-x²+y²=1-$\frac{86649}{86650}$x²y²在有限域模P = 2^252 + 27742317777372353535851937790883648493上。

（所以a = -1和d = 86649/86650 (mod P)。

我的想法是選擇隨機X值並獲得相應的Y值。然後查找T是微不足道的。但問題是我最終會得到以下結果：

For whatever X,

Y = +- (sqrt(-x^2 -1)) / (sqrt(d*x^2 -1))

我的問題是這種在曲線上獲取隨機點的方法是否正確。在這種情況下：由於我無法在有限欄位上獲得十進制值，我應該如何處理 sqrts？

通過除法我們知道a/b= a * inverse_mod(b, P)。

但是 SQRT 運算符呢？我該如何處理？

你將有一個如下形式的weistrass方程：

$ Y^2 = aX^3.. $

其中 x 是右側唯一的未知變數。在右側插入一個隨機 X 值。然後評估右手邊。無論您使用什麼素數，這都需要模數完成。

您最終將得到以下形式的等式：

$ Y^2 = K $ 其中 K 是您評估的右手邊。

這個數字 K 要麼是二次殘差，要麼不是。您可以使用勒讓德符號進行檢查。

如果是，那麼您可以對您的素數進行 K 的 sqrt 以獲取 $ +Y, -Y $

你如何做 sqrt 取決於你決定使用什麼算法，你可以使用 Tonelli-Shanks 這是一種更通用的平方根算法

引用自：https://crypto.stackexchange.com/questions/71697