Why does "epoint_set()" with point compression take longer time for secp224 than secp256?

[k3coby]

I’m trying to do a lot of point calculations on secp192, 224, 256, 384 and 521 using this library. However, when I tried to measure running times, I noticed that “epoint_set ()” with point compression enabled took much longer in secp224 than in secp256. It's weird because the implementation remained unchanged for different curves and other curves (160, 192, 384, 521) worked fine. Can anyone help me figure out why? Is it possible that there's some special optimizations for secp256 in this library? Thank you so much!

[mcarrickscott]

Sure. It actually depends on what the remainder is when the prime p is divided by 8. Obviously (since the prime is odd), the remainder will be 1, 3, 5 or 7 Now to set a point on the curve y*2=x^3+Ax+B, we generate x, and then calculate y=sqrt(x^3+Ax+B), where sqrt() is the square root modulo p. Its the calculation of this square root modulo p which takes time. If the remainder is 3 or 7, its fast. If its 5 its a bit slower. Unfortunately if its 1, its very much slower. And for secp224 the prime p=2^224-2^96+1, which leaves a remainder of 1 when divided by 8. In this case the best modular square rooting algorithm is very slow. Which explains what you have observed.! Mike

…

On Tue, Oct 3, 2017 at 8:23 PM, k3coby ***@***.***> wrote: I’m trying to do a lot of point calculations on secp192, 224, 256, 384 and 521 using this library. However, when I tried to measure running times, I noticed that “epoint_set ()” with point compression enabled took much longer in secp224 than in secp256. It's weird because the implementation remained unchanged for different curves and other curves (160, 192, 384, 521) worked fine. Can anyone help me figure out why? Is it possible that there's some special optimizations for secp256 in this library? Thank you so much! [image: screen shot 2017-10-03 at 15 19 35] <https://user-images.githubusercontent.com/8734578/31144305-577c8c92-a84e-11e7-9835-fc4b810ae123.png> — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#53>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACm8jj-w0sFq1FItI8gJWIcAnpoH2Nq5ks5soomlgaJpZM4Pso64> .

[k3coby]

I see what you mean. When p is an odd prime and p = -1 mod 4, there's a direct way to calculate the square root modulo p, based on "quadratic reciprocity". However, if p = 1 mod 4, we have to use other algorithms to find that square root, which is much slower. It does make sense.

Thanks, Mike. I really appreciate your help!

Coby