Re: Square roots and cube roots in secp224k1

Quote from: stwenhao on Today at 12:46:57 AM

However, the same method won't work for p-value in secp224k1 for some reason:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
n=0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
p%4=1 (failed, expected 3)
p%9=1 (failed, expected 7)

If all of those curves were generated together, then why p-value for secp224k1 was picked differently, than for three other curves? And how to efficiently compute square roots and cube roots for this curve? Also, how to proceed with all n-values? I heard there are some algorithms, to compute those results for any values, but if those curves were selected specifically, to make operations like that "fast", then everything should be solvable by simple equations like "(p+x)/y", similar to "(p+1)/4" and "(p+2)/9", right?

There are "complex" algorithms: A remark on the computation of cube roots in finite fields

One could solve the square and cube root in this case by "simple equation" too. To my knowledge this is not published anywhere.

The smallest pair x & y for square root is (p+3)/8; and for cube root is (p+8)/27.

r4 and r9 are non-trivial primitive 4th and 9th roots 1 mod p more info

r4 = 11913830147633844989339888812832642491211314989669855304438134084459 r9 = 452128346974922831777605865588626403245808317223927710376180600773 b² = a (mod p) if a^(p-1)/2 = 1 ; if square root exists b = a^(p+3)/8 if b² != a b = b * r4 b³ = a (mod p) if a^(p-1)/3 = 1 ; if cube root exists b = a^(p+8)/27 if b³ != a b = b * r9 if b³ != a b = b * r9