diff options
author | John Newbery <john@johnnewbery.com> | 2019-05-18 13:24:23 -0400 |
---|---|---|
committer | Pieter Wuille <pieter.wuille@gmail.com> | 2020-01-19 14:47:33 -0800 |
commit | bba0bad5e8001a7302557883d655ec5b583ac8a6 (patch) | |
tree | 67000b3b2db4659c1275bfa9e3fa0790628846d2 /bip-schnorr.mediawiki | |
parent | 1c6b104597d6a6f374e1ae22e748f78a5295c151 (diff) | |
download | bips-bba0bad5e8001a7302557883d655ec5b583ac8a6.tar.xz |
Define c in lift_x(x)
Diffstat (limited to 'bip-schnorr.mediawiki')
-rw-r--r-- | bip-schnorr.mediawiki | 1 |
1 files changed, 1 insertions, 0 deletions
diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki index 43ea9d7..c267640 100644 --- a/bip-schnorr.mediawiki +++ b/bip-schnorr.mediawiki @@ -104,6 +104,7 @@ The following convention is used, with constants as defined for secp256k1: ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))'. ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte encoding is ''x''. ** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' and ''y(P)'' is a quadratic residue modulo ''p'', or fails if no such point exists<ref>Given an candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. Given a candidate ''x'', the valid Y coordinates are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''. Due to [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion] it then holds that ''c<sup>(p-1)/2</sup> = 1 mod p''. The same criterion applied to ''y'' results in ''y<sup>(p-1)/2</sup> mod p = ±c<sup>((p+1)/4)((p-1)/2)</sup> mod p = ±1 mod p''. Therefore ''y = +c<sup>(p+1)/4</sup> mod p'' is a quadratic residue and ''-y mod p'' is not.</ref>. The function ''lift_x(x)'' is equivalent to the following pseudocode: +*** Let ''c = x<sup>3</sup> + 7 mod p''. *** Let ''y = c<sup>(p+1)/4</sup> mod p''. *** Fail if ''c ≠ y<sup>2</sup> mod p''. *** Return ''(r, y)''. |