[GitHub] [incubator-milagro-crypto-rust] mratsim opened a new issue #46: Fused sqrt and invsqrt

[GitBox <gi...@apache.org>]

mratsim opened a new issue #46:
URL: https://github.com/apache/incubator-milagro-crypto-rust/issues/46


   In Fp2 sqrt implementation you compute separately square root and inverse square root see https://github.com/apache/incubator-milagro-crypto-rust/blob/7c65ce1f23b906c17e97c479bcf90122b2ed0b8a/src/fp2.rs#L333-L336
   
   Those operation can be fused saving a significant amount of time for hashing to G2 as sqrt/inverse are one of the most costly operations there.
   
   Rationale:
   1/√a * a = √a
   
   Hence when p = 3 mod 4
   
   we have √a = a^(p+1)/4 = a^(p-3)/4 * a = 1/√a * a 
   So you can just stop your exponentiation at a^(p-3)/4 to get 1/√a and multiply by a to get √a
   
   Similarly when p = 5 mod 8
   
   we have √a = a^(p+3)/8 = a^(p-5)/8 * a = 1/√a * a
   
   This should be straightforward to plug in https://github.com/apache/incubator-milagro-crypto-rust/blob/7c65ce1f23b906c17e97c479bcf90122b2ed0b8a/src/fp.rs#L688-L730
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@milagro.apache.org
For additional commands, e-mail: issues-help@milagro.apache.org