Open mratsim opened 4 years ago
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 ones 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
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 ones 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