ECDH Public Key Recovery - Determine if valid key exists from just signature and message If I have just the (r,s,v) values of the signature and the message hash, what is the most efficient way to determine if a valid public key exists?

I do not need to know the public key, just that the signature and message hash recover to a public key.

Lets say with the notation:


, are the values from the signature. 
ℎ is the hash of the message being verified
 is the public key
 is the group generator
|| is the x-coordinate of the point 
{,′} are the two curve points with x-coordinate 


The recovery would be:

$$P \ \overset{?}{=} r^{-1}s\{R, R'\} - r^{-1}hG$$

My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P.
"My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P."

I believe that you could check whether $r$ is a valid nonzero $x$ coordinate; that is, whether it is a part of a solution to curve equation (e.g. if your curve is in Weierstrass form with characteristic > 3, you'd check whether $x^3 + ax + b$ is a Quadratic Residue).

If it is (and if it is nonzero), then yes, you could perform the operations to recover $P$, and it would come up with two valid points, and so that's your answer.