Answer the question
In order to leave comments, you need to log in
How does the secp256k1_fe_sqr_inner function work?
Good afternoon.
I want to understand thoroughly how the libsecp256k1 library works.
I can't figure out how this feature works. Can you explain mathematically to me?
Full code: https://github.com/bitcoin-core/secp256k1/blob/mas...
static void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a) {
uint64_t c, d;
uint64_t u0, u1, u2, u3, u4, u5, u6, u7, u8;
uint32_t t9, t0, t1, t2, t3, t4, t5, t6, t7;
const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
VERIFY_BITS(a[0], 30);
VERIFY_BITS(a[1], 30);
VERIFY_BITS(a[2], 30);
VERIFY_BITS(a[3], 30);
VERIFY_BITS(a[4], 30);
VERIFY_BITS(a[5], 30);
VERIFY_BITS(a[6], 30);
VERIFY_BITS(a[7], 30);
VERIFY_BITS(a[8], 30);
VERIFY_BITS(a[9], 26);
/** [... a b c] is a shorthand for ... + a<<52 + b<<26 + c<<0 mod n.
* px is a shorthand for sum(a[i]*a[x-i], i=0..x).
* Note that [x 0 0 0 0 0 0 0 0 0 0] = [x*R1 x*R0].
*/
d = (uint64_t)(a[0]*2) * a[9]
+ (uint64_t)(a[1]*2) * a[8]
+ (uint64_t)(a[2]*2) * a[7]
+ (uint64_t)(a[3]*2) * a[6]
+ (uint64_t)(a[4]*2) * a[5];
/* VERIFY_BITS(d, 64); */
/* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
t9 = d & M; d >>= 26;
VERIFY_BITS(t9, 26);
VERIFY_BITS(d, 38);
/* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
c = (uint64_t)a[0] * a[0];
VERIFY_BITS(c, 60);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
d += (uint64_t)(a[1]*2) * a[9]
+ (uint64_t)(a[2]*2) * a[8]
+ (uint64_t)(a[3]*2) * a[7]
+ (uint64_t)(a[4]*2) * a[6]
+ (uint64_t)a[5] * a[5];
VERIFY_BITS(d, 63);
/* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
u0 = d & M; d >>= 26; c += u0 * R0;
VERIFY_BITS(u0, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 61);
/* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
t0 = c & M; c >>= 26; c += u0 * R1;
VERIFY_BITS(t0, 26);
VERIFY_BITS(c, 37);
/* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
c += (uint64_t)(a[0]*2) * a[1];
VERIFY_BITS(c, 62);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
d += (uint64_t)(a[2]*2) * a[9]
+ (uint64_t)(a[3]*2) * a[8]
+ (uint64_t)(a[4]*2) * a[7]
+ (uint64_t)(a[5]*2) * a[6];
VERIFY_BITS(d, 63);
/* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
u1 = d & M; d >>= 26; c += u1 * R0;
VERIFY_BITS(u1, 26);
VERIFY_BITS(d, 37);
VERIFY_BITS(c, 63);
/* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
t1 = c & M; c >>= 26; c += u1 * R1;
VERIFY_BITS(t1, 26);
VERIFY_BITS(c, 38);
/* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
c += (uint64_t)(a[0]*2) * a[2]
+ (uint64_t)a[1] * a[1];
VERIFY_BITS(c, 62);
/* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
...............
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question