fp.go

Documentation: github.com/cloudflare/circl/math/fp448

     1  // Package fp448 provides prime field arithmetic over GF(2^448-2^224-1).
     2  package fp448
     3  
     4  import (
     5  	"errors"
     6  
     7  	"github.com/cloudflare/circl/internal/conv"
     8  )
     9  
    10  // Size in bytes of an element.
    11  const Size = 56
    12  
    13  // Elt is a prime field element.
    14  type Elt [Size]byte
    15  
    16  func (e Elt) String() string { return conv.BytesLe2Hex(e[:]) }
    17  
    18  // p is the prime modulus 2^448-2^224-1.
    19  var p = Elt{
    20  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    21  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    22  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    23  	0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
    24  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    25  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    26  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    27  }
    28  
    29  // P returns the prime modulus 2^448-2^224-1.
    30  func P() Elt { return p }
    31  
    32  // ToBytes stores in b the little-endian byte representation of x.
    33  func ToBytes(b []byte, x *Elt) error {
    34  	if len(b) != Size {
    35  		return errors.New("wrong size")
    36  	}
    37  	Modp(x)
    38  	copy(b, x[:])
    39  	return nil
    40  }
    41  
    42  // IsZero returns true if x is equal to 0.
    43  func IsZero(x *Elt) bool { Modp(x); return *x == Elt{} }
    44  
    45  // IsOne returns true if x is equal to 1.
    46  func IsOne(x *Elt) bool { Modp(x); return *x == Elt{1} }
    47  
    48  // SetOne assigns x=1.
    49  func SetOne(x *Elt) { *x = Elt{1} }
    50  
    51  // One returns the 1 element.
    52  func One() (x Elt) { x = Elt{1}; return }
    53  
    54  // Neg calculates z = -x.
    55  func Neg(z, x *Elt) { Sub(z, &p, x) }
    56  
    57  // Modp ensures that z is between [0,p-1].
    58  func Modp(z *Elt) { Sub(z, z, &p) }
    59  
    60  // InvSqrt calculates z = sqrt(x/y) iff x/y is a quadratic-residue. If so,
    61  // isQR = true; otherwise, isQR = false, since x/y is a quadratic non-residue,
    62  // and z = sqrt(-x/y).
    63  func InvSqrt(z, x, y *Elt) (isQR bool) {
    64  	// First note that x^(2(k+1)) = x^(p-1)/2 * x = legendre(x) * x
    65  	// so that's x if x is a quadratic residue and -x otherwise.
    66  	// Next, y^(6k+3) = y^(4k+2) * y^(2k+1) = y^(p-1) * y^((p-1)/2) = legendre(y).
    67  	// So the z we compute satisfies z^2 y = x^(2(k+1)) y^(6k+3) = legendre(x)*legendre(y).
    68  	// Thus if x and y are quadratic residues, then z is indeed sqrt(x/y).
    69  	t0, t1 := &Elt{}, &Elt{}
    70  	Mul(t0, x, y)         // x*y
    71  	Sqr(t1, y)            // y^2
    72  	Mul(t1, t0, t1)       // x*y^3
    73  	powPminus3div4(z, t1) // (x*y^3)^k
    74  	Mul(z, z, t0)         // z = x*y*(x*y^3)^k = x^(k+1) * y^(3k+1)
    75  
    76  	// Check if x/y is a quadratic residue
    77  	Sqr(t0, z)     // z^2
    78  	Mul(t0, t0, y) // y*z^2
    79  	Sub(t0, t0, x) // y*z^2-x
    80  	return IsZero(t0)
    81  }
    82  
    83  // Inv calculates z = 1/x mod p.
    84  func Inv(z, x *Elt) {
    85  	// Calculates z = x^(4k+1) = x^(p-3+1) = x^(p-2) = x^-1, where k = (p-3)/4.
    86  	t := &Elt{}
    87  	powPminus3div4(t, x) // t = x^k
    88  	Sqr(t, t)            // t = x^2k
    89  	Sqr(t, t)            // t = x^4k
    90  	Mul(z, t, x)         // z = x^(4k+1)
    91  }
    92  
    93  // powPminus3div4 calculates z = x^k mod p, where k = (p-3)/4.
    94  func powPminus3div4(z, x *Elt) {
    95  	x0, x1 := &Elt{}, &Elt{}
    96  	Sqr(z, x)
    97  	Mul(z, z, x)
    98  	Sqr(x0, z)
    99  	Mul(x0, x0, x)
   100  	Sqr(z, x0)
   101  	Sqr(z, z)
   102  	Sqr(z, z)
   103  	Mul(z, z, x0)
   104  	Sqr(x1, z)
   105  	for i := 0; i < 5; i++ {
   106  		Sqr(x1, x1)
   107  	}
   108  	Mul(x1, x1, z)
   109  	Sqr(z, x1)
   110  	for i := 0; i < 11; i++ {
   111  		Sqr(z, z)
   112  	}
   113  	Mul(z, z, x1)
   114  	Sqr(z, z)
   115  	Sqr(z, z)
   116  	Sqr(z, z)
   117  	Mul(z, z, x0)
   118  	Sqr(x1, z)
   119  	for i := 0; i < 26; i++ {
   120  		Sqr(x1, x1)
   121  	}
   122  	Mul(x1, x1, z)
   123  	Sqr(z, x1)
   124  	for i := 0; i < 53; i++ {
   125  		Sqr(z, z)
   126  	}
   127  	Mul(z, z, x1)
   128  	Sqr(z, z)
   129  	Sqr(z, z)
   130  	Sqr(z, z)
   131  	Mul(z, z, x0)
   132  	Sqr(x1, z)
   133  	for i := 0; i < 110; i++ {
   134  		Sqr(x1, x1)
   135  	}
   136  	Mul(x1, x1, z)
   137  	Sqr(z, x1)
   138  	Mul(z, z, x)
   139  	for i := 0; i < 223; i++ {
   140  		Sqr(z, z)
   141  	}
   142  	Mul(z, z, x1)
   143  }
   144  
   145  // Cmov assigns y to x if n is 1.
   146  func Cmov(x, y *Elt, n uint) { cmov(x, y, n) }
   147  
   148  // Cswap interchanges x and y if n is 1.
   149  func Cswap(x, y *Elt, n uint) { cswap(x, y, n) }
   150  
   151  // Add calculates z = x+y mod p.
   152  func Add(z, x, y *Elt) { add(z, x, y) }
   153  
   154  // Sub calculates z = x-y mod p.
   155  func Sub(z, x, y *Elt) { sub(z, x, y) }
   156  
   157  // AddSub calculates (x,y) = (x+y mod p, x-y mod p).
   158  func AddSub(x, y *Elt) { addsub(x, y) }
   159  
   160  // Mul calculates z = x*y mod p.
   161  func Mul(z, x, y *Elt) { mul(z, x, y) }
   162  
   163  // Sqr calculates z = x^2 mod p.
   164  func Sqr(z, x *Elt) { sqr(z, x) }
   165
View as plain text