[SCHNORR BREAK] Use quadratic-residue-y as symmetry breaker #359

1. 
   sipa commented at 6:00 pm on November 25, 2015: contributor

   (Builds on top of #322)

   This changes the implied y coordinate in Schnorr signatures to be the one which is a quadratic residue (the older logic required it to be even). This should be faster, as it doesn’t need a modular inverse.

2. sipa force-pushed on Nov 25, 2015
3. sipa force-pushed on Nov 25, 2015
4. sipa force-pushed on Nov 25, 2015
5. sipa force-pushed on Nov 25, 2015
6. 
   peterdettman commented at 4:01 am on November 26, 2015: contributor

   I guess it’s worth reminding that our sqrt returns the particular root (if any exist) that is a quadratic residue already, which seems relevant to “Verification (method 2)”.
7. 
   sipa commented at 10:00 am on November 26, 2015: contributor

   @peterdettman Yes, I implemented it that way. It could use some explanation indeed.
8. 
   sipa commented at 11:49 am on November 26, 2015: contributor

   @peterdettman By the way, do you have any intuition for a fast (and hopefully not too complex) algorithm for computing a Jacobi symbol (a|p) (where p is the size of our field)?
9. [Schnorr API change] Schnorr multisigning API overhaul 2f8a7c5ae1
10. Move schnorr documentation to markdown document f2514204a8
11. Add Jacobi symbol test via GMP

    Also add native Jacobi symbol test (Andrew)
    
    Rebased-by: Andrew Poelstra
    Rebased-by: Pieter Wuille

    7e5332e95b
12. Add function for testing quadratic residue field/group elements. d2dd320f9a
13. [SCHNORR BREAK] Use y being a quadratic residue as symmetry breaker 5ce3353ef2
14. sipa force-pushed on Dec 14, 2015
15. 
    sipa commented at 1:56 pm on June 29, 2016: contributor

    Going to do this differently.
16. sipa closed this on Jun 29, 2016

    ---

Contributors
sipa peterdettman