ed25519如何区分负数

1. ed25519 如何区分负数

在论文《High-speed high-security signatures》中有如下约定： 对应curve25519-dalek/src/field.rs中的代码实现为：

    /// Determine if this `FieldElement` is negative, in the sense
    /// used in the ed25519 paper: `x` is negative if the low bit is
    /// set.
    ///
    /// # Return
    ///
    /// If negative, return `Choice(1)`.  Otherwise, return `Choice(0)`.
    pub fn is_negative(&self) -> Choice {
        let bytes = self.to_bytes();
        (bytes[0] & 1).into()
    }

2. sqrt(-1) mod p 的非负数根

/// Precomputed value of one of the square roots of -1 (mod p)
pub(crate) const SQRT_M1: FieldElement51 = FieldElement51([1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133]);

以下为sage脚本，平方根，注意存在正数和负数两个根，取其中的正数根（根据ed25519中负数的约定，应取根的最后一个bit为0的解，即为相应的非负数根）。

sage: p=2^255-19
sage: K=GF(p)
sage: K
Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
sage: K(-1).nth_root(2)
38214883241950591754978413199355411911188925816896391856984770930832735035197
sage: 1718705420411056+234908883556509*(2^51)+2233514472574048*(2^102)+211720262
....: 7021982*(2^153)+765476049583133*(2^204)
19681161376707505956807079304988542015446066515923890162744021073123829784752
sage: 19681161376707505956807079304988542015446066515923890162744021073123829784
....: 752+3821488324195059175497841319935541191118892581689639185698477093083273
....: 5035197==p
True
sage: hex(3821488324195059175497841319935541191118892581689639185698477093083273
....: 5035197)
'547cdb7fb03e20f4d4b2ff66c2042858d0bce7f952d01b873b11e4d8b5f15f3d' //负数根
sage: hex(1968116137670750595680707930498854201544606651592389016274402107312382
....: 9784752)
'2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0' //非负数根
sage:

参考资料： [1] 论文《High-speed high-security signatures》