How to determine first byte (recovery ID) for signatures (message signing)?
FWIW this is what I have found regarding this question. Basically there are two ways of finding what libraries call &quot;recid&quot; or recovery ID. Most of them use the first method but there is another way:
Method 1:

Only requires r and s so it can be performed by anyone as long as you have the signature and the &quot;message&quot; that was signed.
It is so much slower because it has 3 scalar multiplication and based on cofactor of the elliptic curve used the whole operation may be repeated 2*(h+1) times, which is up to 4 times for bitcoin with secp256k1 curve (99% of the time it is 1 or 2 times).

The steps are explained in section 4.1.6 of SEC:1, I won't repeat them here.
To find recid you check the calculated public key with the given public key or hash of it and report number of rejected public keys as recid. For example if x=r+(0*order) and Q was used then recid=0 and if -Q was used then recid=1 and so on.
method 2:

It requires full r or R=(xR, yR) so it can only be done while signing (requires having the private key).
It is much faster because there is no additional calculations. It just needs value checks which are fast.
This is usually referred to as v in libraries

byte v = if(R.X &gt; curve.N) then 2 else 0) | (if R.Y.IsEven then 0 else 1);
Basically it is check to see if xR is bigger than curve order (N) and whether yR is even or odd. Something that should not be forgotten is a &quot;flip&quot; that is performed based on s and whether s was used in the signature or -s
if s &gt; curve.N/2 then v^=1 else do nothing
** Note that in the end you need to calculate the following:
recid = 27 + v + (if compressed 4 else 0)