From 708aeadf85e983c85dac95ec4e0932cacac8a79d Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Fri, 29 Nov 2019 15:47:33 +0000 Subject: Replace references to Euler's criterion with Legendre symbol in bip-schnorr --- bip-schnorr.mediawiki | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki index 379bc94..ce5abde 100644 --- a/bip-schnorr.mediawiki +++ b/bip-schnorr.mediawiki @@ -109,9 +109,9 @@ The following conventions are used, with constants as defined for [https://www.s ** The function ''bytes(x)'', where ''x'' is an integer, returns the 32-byte encoding of ''x'', most significant byte first. ** 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 first encoding is ''x''. -** The function ''is_square(x)'', where ''x'' is an integer, returns whether or not ''x'' is a quadratic residue modulo ''p''. Since ''p'' is prime, it is equivalent to the Legendre symbol ''(x / p) = x(p-1)/2 mod p'' being equal to ''1'' (see [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion])For points ''P'' on the secp256k1 curve it holds that ''y(P)(p-1)/2 ≠ 0 mod p''.. +** The function ''is_square(x)'', where ''x'' is an integer, returns whether or not ''x'' is a quadratic residue modulo ''p''. Since ''p'' is prime, it is equivalent to the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(x / p) = x(p-1)/2 mod p'' being equal to ''1''For points ''P'' on the secp256k1 curve it holds that ''y(P)(p-1)/2 ≠ 0 mod p''.. ** The function ''has_square_y(P)'', where ''P'' is a point, is defined as ''not is_infinite(P) and is_square(y(P))''For points ''P'' on the secp256k1 curve it holds that ''has_square_y(P) = not has_square_y(-P)''.. -** 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 ''has_square_y(P)'', or fails if no such point existsGiven a 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 = x3 + 7 mod p'' and they can be computed as ''y = ±c(p+1)/4 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(p-1)/2 = 1 mod p''. The same criterion applied to ''y'' results in ''y(p-1)/2 mod p = ±c((p+1)/4)((p-1)/2) mod p = ±1 mod p''. Therefore ''y = +c(p+1)/4 mod p'' is a quadratic residue and ''-y mod p'' is not.. The function ''lift_x(x)'' is equivalent to the following pseudocode: +** 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 ''has_square_y(P)'', or fails if no such point existsGiven a 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 = x3 + 7 mod p'' and they can be computed as ''y = ±c(p+1)/4 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''. The [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''( c / p)'' is ''c(p-1)/2 = 1 mod p''. The Legendre symbol ''( y / p )'' is ''y(p-1)/2 mod p = ±c((p+1)/4)((p-1)/2) mod p = ±1 mod p''. Therefore ''y = +c(p+1)/4 mod p'' is a quadratic residue and ''-y mod p'' is not.. The function ''lift_x(x)'' is equivalent to the following pseudocode: *** Let ''c = x3 + 7 mod p''. *** Let ''y = c(p+1)/4 mod p''. *** Fail if ''c ≠ y2 mod p''. -- cgit v1.2.3