--- Log opened Fri Sep 20 00:00:18 2019
01:06 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
01:08 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 260 seconds]
01:10 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
01:12 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
01:14 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1
01:21 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 260 seconds]
01:28 -!- quad123 [5f56495a@95.86.73.90] has joined #secp256k1
01:30 < quad123> Hi
01:30 < quad123> I'm reading bip-schnorr and trying to figure out the quadratic residue thing
01:31 < quad123> Saying that "y is quadratic residue mod n" means that "there exist some a such that a^2=y mod n". right? how is that always true for one y and not for the complement?
01:32 < quad123> (i.e. it means that `y=sqrt(x^3+7)` has one solution which is quad residue and another which is not. I don't get why would a result of a square root have one quad residue and the other not)
01:42 < nsh> that square root is not the square root of the square establishing the residue; it's the curve equations. a^2=y mod n does have two solutions, for a and -a
01:44 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
01:50 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1
01:55 < elichai2> quad123: this is because `-1 mod n` in the secp order is a quadratic residue. and "The product of two quadratic residues is a residue, the product of a residue and a non-residue is a non-residue, and the product of two non-residues is a residue."
01:57 < elichai2> * `-1 mod n` is not a Quadratic Residue
01:58 < elichai2> so `-1 = QNR`. so if `y'=QR` then -y is QNR*QR which according to the sentence above is QNR. and if `y'=QNR` then `-1*y'`=QNR*QNR=QR
01:59 < elichai2> so by the fact that -1 mod n is QNR(Quadratic non residue) then any number and it's negation mod n one will be QR and the other QNR
02:13 < elichai2> sipa: maybe adding it to the bip? I can try writing a PR. altough the BIP is already pretty big
02:20 -!- quad123 [5f56495a@95.86.73.90] has quit [Ping timeout: 260 seconds]
07:45 < elichai2> sipa: nickler, this may be a bit nitpicking, but the python example is using euler's criterion which is for calculating the legendre symbol, and not the jacobi symbol. now because `p` is odd prime then it's the same. but generally calling this function `jacobi` isn't really correct. (I tried copying it for some prototype when I got weird results and I realized this isn't actually jacobi but legendre :) )
09:04 < sipa> elichai2: actually what we need is legendre's symbol, because we care only about quadratic residuosity
09:04 < sipa> it's just more xommonly called jacobi symbol because in practice, the algorithm for computing legendre symbols is the same as jaxobi
09:05 < elichai2> Yes. I know. But the python code in the bip has a function Jacobi which doesn't do Jacobi, but legendre :/
09:05 < sipa> ha
09:06 < elichai2> It uses a^(p-1/2) that's euiler criterion which doesn't apply to non primes
09:07 < elichai2> AFAIK
09:10 < elichai2> I don't mind implementing a Jacobi symbol in python, but it's going to return the same thing as p is a prime anyway
09:11 < sipa> no
09:11 < sipa> maybe we should rename things to legendre symbol everywhere
09:12 < sipa> there is a jacobi symbol here: https://github.com/bitcoin/bitcoin/blob/master/test/functional/test_framework/key.py
09:13 < sipa> which is faster than the modexp based one
09:42 < elichai2> Yes it's probably faster heh. I prefer legendre because the proofs for the properties are easier to understand. But as you said in practice the Jacobi is faster so everyone uses that
09:43 < elichai2> Interestingly that one has xors and not an obvious law of repriocity (modulo 4)(it's probably the t^n^k^3 somehow heh) curious to check if it performs better hmm
09:52 < sipa> it's xoring bits instead of multiplying by -1
09:53 < sipa> it's just alternating between -1 and 1 anyway; easier to do with bit flipping
10:40 -!- reallll [~belcher@unaffiliated/belcher] has joined #secp256k1
10:43 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 265 seconds]
11:02 -!- reallll is now known as belcher
15:03 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Ping timeout: 260 seconds]
15:04 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-hvxettnarofpvnmf] has quit [Quit: Connection closed for inactivity]
15:04 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Ping timeout: 260 seconds]
15:14 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]
15:18 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1
15:19 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1
15:24 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
--- Log closed Sat Sep 21 00:00:17 2019