group: Save a normalize_to_zero in gej_add_ge #1078

1. 
   real-or-random commented at 10:05 am on February 21, 2022: contributor

   As discovered by sipa in #1033.

   See commit message for reasoning but note that the infinity handling will be replaced in the second commit again.

2. real-or-random force-pushed on Feb 21, 2022
3. group: Save a normalize_to_zero in gej_add_ge

   The code currently switches to the alternative formula for lambda only if (R,M)
   = (0,0) but the alternative formula works whenever M = 0: Specifically, M = 0
   implies y1 = -y2. If x1 = x2, then a = -b this is the r = infinity case that we
   handle separately. If x1 != x2, then the denominator in the alternative formula
   is non-zero, so this formula is well-defined.
   
   One needs to carefully check that the infinity assignment is still correct
   because now the definition of m_alt at this point in the code has changed. But
   this is true:
   
   Case y1 = -y2:
     Then degenerate = true and infinity = ((x1 - x2)Z == 0) & ~a->infinity .
     a->infinity is handled separately.
     And if ~a->infinity, then Z = Z1 != 0,
     so infinity = (x1 - x2 == 0) = (a == -b) by case condition.
   
   Case y1 != -y2:
     Then degenerate = false and infinity = ((y1 + y2)Z == 0) & ~a->infinity .
     a->infinity is handled separately.
     And if ~a->infinity, then Z = Z1 != 0,
     so infinity = (y1 + y2 == 0) = false by case condition.
   
   Co-Authored-By: Pieter Wuille <pieter@wuille.net>

   ac71020ebe
4. real-or-random force-pushed on Feb 21, 2022
5. 
   real-or-random commented at 12:20 pm on February 26, 2022: contributor

   I think the comment I wrote is wrong, I’ll have a look at this.
6. group: Further simply gej_add_ge e089eecc1e
7. real-or-random force-pushed on Feb 26, 2022
8. 
   real-or-random commented at 12:23 pm on February 26, 2022: contributor

   Fixed… (ok that was quick).
9. 
   sipa commented at 8:32 pm on November 18, 2022: contributor

   ACK e089eecc1e54551287b12539d2211da631a6ec5c
10. 
    apoelstra commented at 0:12 am on February 14, 2023: contributor

    utACK but I think this could be rebased on master so I can run the ctime tests on it. (This predates the existence of the ctime tests.)
11. 
    apoelstra commented at 0:18 am on February 14, 2023: contributor

    Never mind me :) the ctime tests just used to have a different name.
12. apoelstra approved
13. 
    apoelstra commented at 0:42 am on February 14, 2023: contributor

    ACK e089eecc1e54551287b12539d2211da631a6ec5c
14. 
    sipa commented at 7:49 pm on February 14, 2023: contributor

    Benchmarks on Ryzen 5950X, locked at 2.2 GHz, GCC 12.2.0, running with SECP256K1_BENCH_ITERS=1000000 ./bench_internal add:

    Master:

    0Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)    
    1group_add_affine              ,     0.444     ,     0.444     ,     0.444  
    

    Master + #1078

    0Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)    
    1group_add_affine              ,     0.432     ,     0.433     ,     0.433  
    

15. sipa merged this on Feb 14, 2023
16. sipa closed this on Feb 14, 2023

    ---

17. hebasto referenced this in commit 7c0cc5d976 on Mar 7, 2023
18. dhruv referenced this in commit a5df79db12 on Mar 7, 2023
19. dhruv referenced this in commit 77b510d84c on Mar 7, 2023
20. sipa referenced this in commit 763079a3f1 on Mar 8, 2023
21. div72 referenced this in commit 945b094575 on Mar 14, 2023
22. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
23. vmta referenced this in commit 8f03457eed on Jul 1, 2023
24. jonasnick cross-referenced this on Jul 20, 2023 from issue Upstream PRs 1160, 1193, 1169, 1190, 1192, 1194, 1196, 1195, 1170, 1172, 1200, 1199, 1203, 1201, 1206, 1078, 1209, 979, 1212, 1218, 1217, 1221, 1222 by jonasnick

Contributors
real-or-random sipa apoelstra