This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
本文讨论了SM2大素数蒙哥马利乘法优化的一些方法。
SM2 P256 P表示
SM2 256 的素数P=0xfffffffeffffffffffffffffffffffffffffffff00000000ffffffffffffffff，也可以表示为
p_0=0xFFFFFFFFFFFFFFFF
p_1=0xFFFFFFFF00000000
p_2=0xFFFFFFFFFFFFFFFF
p_3=0xFFFFFFFEFFFFFFFF
P = 2^{256} - 2^{224} - 2^{96} + 2^{64} - 1
P = p_3 \ast 2^{192} + p_2 \ast 2^{128} + p_1 \ast 2^{64} + p_0
P = 2^{256}-(2^{32} \ast 2^{192} + 0 \ast 2^{128} + (2^{32} - 1) \ast 2^{64} + 1)
P域平方的WWMM约减优化
假设 T=a^2 ：
T=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0
则共四次约减，第一次约减为：
T_1=t_0
方案一：(乘法、加法)
这个是最原始方法。
T_2=T_1 \ast P=t_0 \ast P= (t_0 \ast p_3) \ast 2^{192} + (t_0 \ast p_2) \ast 2^{128} + (t_0 \ast p_1) \ast 2^{64} + (t_0 \ast p_0)
T_3=T + T_2=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + (t_3+t_0 \ast p_3) \ast 2^{192} + (t_2+t_0 \ast p_2) \ast 2^{128} + (t_1+t_0 \ast p_1) \ast 2^{64} + t_0 \ast 2^{64}
t_1=t_1 + t_0 \ast 0xFFFFFFFF00000001
t_2=t_2 + t_0 \ast p_2
t_3=t_3 + t_0 \ast p_3
伪代码：
MOVQ $0xFFFFFFFF00000001, AX
MULQ t0
ADDQ AX, t1
ADCQ $0, DX
MOVQ DX, BX // carry
MOVQ p2, AX
MULQ t0
ADDQ BX, t2
ADCQ $0, DX
ADDQ AX, t2
ADCQ $0, DX
MOVQ DX, BX // carry
MOVQ p3, AX
MULQ t0
ADDQ BX, t3
ADCQ $0, DX
ADDQ AX, t3
ADCQ $0, DX
MOVQ DX, t0
乘法: 3
加法：10
使用MULXQ/ADCXQ/ADOXQ:
MOVQ t0, DX
XORQ SI, SI
MULXQ p1, AX, DI
ADOXQ AX, t1
MULXQ p2, AX, BX
ADCXQ DI, AX
ADOXQ AX, t2
MULXQ p3, AX, t0
ADCXQ BX, AX
ADOXQ AX, t3
ADCXQ SI, t0
ADOXQ SI, t0
乘法: 3
加法：7
方案二：(移位、加法、减法)
T_2=T_1 \ast P=t_0 \ast P= t_0 \ast (2^{256}-(2^{32} \ast 2^{192} + 0 \ast 2^{128} + (2^{32} - 1) \ast 2^{64} + 1))
T_2=t_0 \ast 2^{256} - t_0 \ast 2^{32} \ast 2^{192} - t_0 \ast (2^{32} - 1) \ast 2^{64} - t_0
T_3=T + T_2=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0 \ast 2^{256} - t_0 \ast 2^{32} \ast 2^{192} - t_0 \ast (2^{32} - 1) \ast 2^{64}
T_3=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + (t_4+t_0) \ast 2^{256}+(t_3 - t_0 \ast 2^{32}) \ast 2^{192} + t_2 \ast 2^{128} + (t_1 + t_0 - t_0 \ast 2^{32}) \ast 2^{64}
T_3=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + (t_4+t_0-t0>>32) \ast 2^{256}+(t_3 - t_0<<32) \ast 2^{192} + (t_2 - t0>>32) \ast 2^{128} + (t_1 + t_0 - t_0<<32) \ast 2^{64}
先处理加法，后处理减法，后三个加法是带进位加法
t_1=t_0 + t_1
t_2=t_2 + 0
t_3=t_3 + 0
t_0=t_0 + 0
t0，t2，t3会不会同时是0xffffffffffffffff呢？这里没法给出证明。
接着处理减法，假定a0是 t_0 \ast 2^{32} 的低64位，a1是 t_0 \ast 2^{32} 的高64位。后三个减法是带借位减法：
t_1=t_1 - a_0
t_2=t_2 - a_1
t_3=t_3 - a_0
t_0=t_0 - a_1
减法显然是安全的（因为第四步的结果显然是>=0的，而且为零的情况仅限于 t_0==0 的情况 ），所以调整为先做减法，再做加法，确保第四步加法不会产生进位。
伪代码：
\ // First reduction step, [p3, p2, p1, p0] = [1, -0x100000000, 0, (1 - 0x100000000), -1]
MOVQ acc0, AX \
MOVQ acc0, DX \
SHLQ $32, AX \ // AX = L(acc0 * 2^32), low part
SHRQ $32, DX \ // DX = H(acc0 * 2^32), high part
\// calculate the negative part:
\//[1, -0x100000000, 0, -0x100000000] * acc0 + [0, acc3, acc2, acc1]
\//[acc0, acc3, acc2, acc1] - [0, 0x100000000, 0, 0x100000000] * acc0
\//[acc0, acc3, acc2, acc1] - [acc0>>32, acc0<<32, acc0>>32, acc0<<32]
SUBQ AX, acc1 \
SBBQ DX, acc2 \
SBBQ AX, acc3 \
MOVQ acc0, AX \
SBBQ DX, acc0 \
\ // calculate the positive part: [0, 0, 0, 1] * AX + [acc0, acc3, acc2, acc1],
\ // due to (-1) * acc0 + acc0 == 0, so last lowest lamb 0 is dropped directly, no carry.
ADDQ AX, acc1 \ // acc1' = L (AX+ acc1)
ADCQ $0, acc2 \ // acc2' = acc2 + carry1
ADCQ $0, acc3 \ // acc3' = acc3 + carry2
ADCQ $0, acc0 \ // acc0' = acc0 + carry3
移位: 2
加法：4
减法：4
| 方案 | 乘法 | 移位 | 加法 | 减法 |
|---|---|---|---|---|
| 方案一 | 3 | 0 | 10 | 0 |
| 方案一（MULX/ADCX/ADOX） | 3 | 0 | 7 | 0 |
| 方案二 | 0 | 2 | 4 | 4 |
P域乘法的WWMM约减优化
乘法没有和平方一样，先把乘法做完再约减，而是乘法和约减混合在一起做的。
假设：
X = x_3 \ast 2^{192} + x_2 \ast 2^{128} + x_1 \ast 2^{64} + x_0
Y = y_3 \ast 2^{192} + y_2 \ast 2^{128} + y_1 \ast 2^{64} + y_0
则第一轮先处理 X \ast y_0
T=(y_0 \ast x_3 \ast 2^{192}) + (y_0 \ast x_2 \ast 2^{128}) + (y_0 \ast x_1 \ast 2^{64}) + y_0 \ast x_0
=t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0
方案一：(乘法、加法)
这个是最原始方法。
T_2=T_1 \ast P=t_0 \ast P= (t_0 \ast p_3) \ast 2^{192} + (t_0 \ast p_2) \ast 2^{128} + (t_0 \ast p_1) \ast 2^{64} + (t_0 \ast p_0)
T_3=T + T_2=t_4 \ast 2^{256} + (t_3+t_0 \ast p_3) \ast 2^{192} + (t_2+t_0 \ast p_2) \ast 2^{128} + (t_1+t_0 \ast p_1) \ast 2^{64} + t_0 \ast 2^{64}
t_1=t_1 + t_0 \ast 0xFFFFFFFF00000001
t_2=t_2 + t_0 \ast p_2
t_3=t_3 + t_0 \ast p_3
t_4=t_4 + 0
t_5=0 + 0
伪代码：
MOVQ $0xFFFFFFFF00000001, AX
MULQ t0
ADDQ AX, t1
ADCQ $0, DX
MOVQ DX, BX // carry
MOVQ p2, AX
MULQ t0
ADDQ BX, t2
ADCQ $0, DX
ADDQ AX, t2
ADCQ $0, DX
MOVQ DX, BX // carry
MOVQ p3, AX
MULQ t0
ADDQ BX, t3
ADCQ $0, DX
ADDQ AX, t3
ADCQ DX, t4
ADCQ $0, t5
乘法: 3
加法：11
使用MULXQ/ADCXQ/ADOXQ:
MOVQ t0, DX
XORQ SI, SI
MULXQ p1, AX, DI
ADOXQ AX, t1
MULXQ p2, AX, BX
ADCXQ DI, AX
ADOXQ AX, t2
MULXQ p3, AX, DI
ADCXQ BX, AX
ADOXQ AX, t3
ADCXQ SI, DI
ADOXQ DI, t4
ADOXQ SI, t5
乘法: 3
加法：8
方案二：(移位、加法、减法)
T_2=T_1 \ast P=t_0 \ast P= t_0 \ast (2^{256}-(2^{32} \ast 2^{192} + 0 \ast 2^{128} + (2^{32} - 1) \ast 2^{64} + 1))
T_2=t_0 \ast 2^{256} - t_0 \ast 2^{32} \ast 2^{192} - t_0 \ast (2^{32} - 1) \ast 2^{64} - t_0
T_3=T + T_2=t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0 \ast 2^{256} - t_0 \ast 2^{32} \ast 2^{192} - t_0 \ast (2^{32} - 1) \ast 2^{64}
T_3=(t_4+t_0) \ast 2^{256}+(t_3 - t_0 \ast 2^{32}) \ast 2^{192} + t_2 \ast 2^{128} + (t_1 + t_0 - t_0 \ast 2^{32}) \ast 2^{64}
T_3=(t_4+t_0-t_0>>32) \ast 2^{256}+(t_3 - t_0<<32) \ast 2^{192} + (t_2 - t_0>>32) \ast 2^{128} + (t_1 + t_0 - t_0<<32) \ast 2^{64}
先处理加法，后处理减法，后四个加法是带进位加法
t_1=t_1 + t_0
t_2=t_2 + 0
t_3=t_3 + 0
t_4=t_4 + t_0
t_5=0 + 0
显然，这里不像平方那样有溢出风险。
接着处理减法，假定a0是 t_0 \ast 2^{32} 的低64位，a1是 t_0 \ast 2^{32} 的高64位。后四个减法是带借位减法：
t_1=t_1 - a_0
t_2=t_2 - a_1
t_3=t_3 - a_0
t_4=t_4 - a_1
t_5=t_5 - 0
伪代码：
XORQ acc5, acc5
// First reduction step
MOVQ acc0, AX
MOVQ acc0, DX
SHLQ $32, AX
SHRQ $32, DX
ADDQ acc0, acc1
ADCQ $0, acc2
ADCQ $0, acc3
ADCQ acc0, acc4
ADCQ $0, acc5
SUBQ AX, acc1
SBBQ DX, acc2
SBBQ AX, acc3
SBBQ DX, acc4
SBBQ $0, acc5
移位: 2
加法：5
减法：5
如果先使用减法：
XORQ acc5, acc5
// First reduction step
MOVQ acc0, AX
MOVQ acc0, DX
SHLQ $32, AX
SHRQ $32, DX
SUBQ AX, acc1
SBBQ DX, acc2
SBBQ AX, acc3
MOVQ acc0, AX
SBBQ DX, acc0
ADDQ AX, acc1
ADCQ $0, acc2
ADCQ $0, acc3
ADCQ acc0, acc4
ADCQ $0, acc5
移位: 2
加法：5
减法：4
| 方案 | 乘法 | 移位 | 加法 | 减法 |
|---|---|---|---|---|
| 方案一 | 3 | 0 | 11 | 0 |
| 方案一（MULX/ADCX/ADOX） | 3 | 0 | 8 | 0 |
| 方案二 | 0 | 2 | 5 | 4 |
SM2 P256 Order表示
SM2的素数Order=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
O = O_3 \ast 2^{192} + O_2 \ast 2^{128} + O_1 \ast 2^{64} + O_0
O = 2^{256} - 2^{32} \ast 2^{192} - 2^{128} + O_1 \ast 2^{64} + O_0
O_3=0xFFFFFFFEFFFFFFFF
O_2=0xFFFFFFFFFFFFFFFF
O_1=0x7203DF6B21C6052B
O_0=0x53BBF40939D54123
Order域平方的WWMM约减优化
假设 T=a^2 ：
T=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0
则共四次约减，第一次约减为：
T_1=t_0
Y=T_1 \ast k_0
计算Y：
MOVQ acc0, AX
MULQ p256ordK0<>(SB)
MOVQ AX, t0 // Y = t0 = (k0 * acc0) mod 2^64
使用MULX:
MOVQ acc0, DX
MULXQ p256ordK0<>(SB), t0, AX
方案一：(乘法、加法)
这个方案和P域的方案类似。
T_2=T_1 \ast O=Y \ast O= (Y \ast O_3) \ast 2^{192} + (Y \ast O_2) \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=T + T_2=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + (t_3+Y \ast O_3) \ast 2^{192} + (t_2+Y \ast O_2) \ast 2^{128} + (t_1+Y \ast O_1) \ast 2^{64} + t_0 + Y \ast O_0
共四次约减，结果表示为 [t_3,t_2,t_1,t_0]
（下面没有表示出高64位和进位处理）
t_0=t_0 + Y \ast O_0
t_1=t_1 + Y \ast O_1
t_2=t_2 + Y \ast O_2
t_3=t_3 + Y \ast O_3
t_0=0+0
伪代码(第一轮)：
// T = [acc0, acc1, acc2, acc3, acc4, acc5, y_ptr, x_ptr]
// First reduction step
MOVQ acc0, AX
MULQ ·np+0x00(SB)
MOVQ AX, t0 // Y
// Calculate next T = T+Y*P
MOVQ ·p2+0x00(SB), AX
MULQ t0
ADDQ AX, acc0 // acc0 is free now
ADCQ $0, DX
MOVQ DX, t1 // carry
XORQ acc0, acc0
MOVQ ·p2+0x08(SB), AX
MULQ t0
ADDQ t1, acc1
ADCQ $0, DX
ADDQ AX, acc1
ADCQ $0, DX
MOVQ DX, t1 // carry
MOVQ ·p2+0x10(SB), AX
MULQ t0
ADDQ t1, acc2
ADCQ $0, DX
ADDQ AX, acc2
ADCQ $0, DX
MOVQ DX, t1 // carry
MOVQ ·p2+0x18(SB), AX
MULQ t0
ADDQ t1, acc3
ADCQ $0, DX
ADDQ AX, acc3
ADCQ DX, acc0
乘法: 5
加法：14
使用MULXQ/ADCXQ/ADOXQ:
// First reduction step
MOVQ acc0, DX
MULXQ ·np+0x00(SB), DX, AX
MULXQ ·p2+0x00(SB), AX, t0
ADOXQ AX, acc0 // (carry1, acc0) = acc0 + t0 * ord0
MULXQ ·p2+0x08(SB), AX, BX
ADCXQ t0, AX
ADOXQ AX, acc1
MULXQ ·p2+0x10(SB), AX, t0
ADCXQ BX, AX
ADOXQ AX, acc2
MULXQ ·p2+0x18(SB), AX, acc0
ADCXQ t0, AX
ADOXQ AX, acc3
MOVQ $0, t0
ADCXQ t0, acc0
ADOXQ t0, acc0
乘法: 5
加法：9
方案二：(移位、加法、减法)
因为Order素数不是MFMM，所以这个方案其实优势不大、甚至没有优势，尤其是在使用使用MULXQ/ADCXQ/ADOXQ的情况下。
移位针对 O_3 O_2 乘法
T_2=T_1 \ast O=Y \ast O= Y \ast 2^{256}-(Y \ast 2^{32}) \ast 2^{192} - Y \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=T + T_2=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0 + Y \ast 2^{256}-(Y \ast 2^{32}) \ast 2^{192} - Y \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + (t_4+Y) \ast 2^{256}+(t_3 - Y \ast 2^{32}) \ast 2^{192} + (t_2 - Y) \ast 2^{128} + (t_1 + Y \ast O_1) \ast 2^{64} + (t_0 + Y \ast O_0)
T_3=t_7 \ast 2^{448} + t_6 \ast 2^{384} + t_5 \ast 2^{320} + (t_4+Y-Y>>32) \ast 2^{256}+(t_3 - Y<<32) \ast 2^{192} + (t_2 - Y) \ast 2^{128} + (t_1 + Y \ast O_1) \ast 2^{64} + (t_0 + Y \ast O_0)
依然采用先减后加！
// First reduction step
MOVQ acc0, AX
MULQ p256ordK0<>(SB)
MOVQ AX, t0 // Y = t0 = (k0 * acc0) mod 2^64
// 处理第一个加法，以便释放acc0
MOVQ p256ord<>+0x00(SB), AX
MULQ t0
ADDQ AX, acc0 // (carry1, acc0) = acc0 + L(t0 * ord0)，acc0 可以被释放了。
ADCQ $0, DX // DX = carry1 + H(t0 * ord0)
MOVQ DX, t1 // t1 = carry1 + H(t0 * ord0)
// calculate the negative part: [acc0, acc3, acc2, acc1] - [0, 0x100000000, 1, 0] * t0
// 处理减法
MOVQ t0, acc0 // acc0 = t0
MOVQ t0, AX
MOVQ t0, DX
SHLQ $32, AX
SHRQ $32, DX
SUBQ t0, acc2
SBBQ AX, acc3
SBBQ DX, acc0
// 处理加法
MOVQ p256ord<>+0x08(SB), AX
MULQ t0
ADDQ t1, acc1 // (carry2, acc1) = acc1 + t1
ADCQ $0, DX // DX = carry2 + H(t0*ord1)
ADDQ AX, acc1 // (carry3, acc1) = acc1 + t1 + L(t0*ord1)
ADCQ DX, acc2
ADCQ $0, acc3
ADCQ $0, acc0
乘法: 3
移位：2
加法：8
减法：3
| 方案 | 乘法 | 移位 | 加法 | 减法 |
|---|---|---|---|---|
| 方案一 | 5 | 0 | 14 | 0 |
| 方案一（MULX/ADCX/ADOX） | 5 | 0 | 9 | 0 |
| 方案二 | 3 | 2 | 8 | 3 |
看来在支持MULXQ/ADCXQ/ADOXQ的情况下，使用方案一（MULX/ADCX/ADOX）更好！
Order域乘法的WWMM约减优化
乘法没有和平方一样，先把乘法做完再约减，而是乘法和约减混合在一起做的。
假设：
X = x_3 \ast 2^{192} + x_2 \ast 2^{128} + x_1 \ast 2^{64} + x_0
Y = y_3 \ast 2^{192} + y_2 \ast 2^{128} + y_1 \ast 2^{64} + y_0
则第一轮先处理 X \ast y_0
T=(y_0 \ast x_3 \ast 2^{192}) + (y_0 \ast x_2 \ast 2^{128}) + (y_0 \ast x_1 \ast 2^{64}) + y_0 \ast x_0
=t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0
方案一：(乘法、加法)
T_2=T_1 \ast O=Y \ast O= (Y \ast O_3) \ast 2^{192} + (Y \ast O_2) \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=T + T_2=t_4 \ast 2^{256} + (t_3+Y \ast O_3) \ast 2^{192} + (t_2+Y \ast O_2) \ast 2^{128} + (t_1+Y \ast O_1) \ast 2^{64} + t_0 + Y \ast O_0
（下面没有表示出高64位和进位处理）
t_0=t_0 + Y \ast O_0
t_1=t_1 + Y \ast O_1
t_2=t_2 + Y \ast O_2
t_3=t_3 + Y \ast O_3
t_4=t_4 + 0
t_5=0 + 0
// First reduction step
MOVQ acc0, AX
MULQ ·np+0x00(SB)
MOVQ AX, t0
MOVQ ·p2+0x00(SB), AX
MULQ t0
ADDQ AX, acc0
ADCQ $0, DX
MOVQ DX, BX
MOVQ ·p2+0x08(SB), AX
MULQ t0
ADDQ BX, acc1
ADCQ $0, DX
ADDQ AX, acc1
ADCQ $0, DX
MOVQ DX, BX
MOVQ ·p2+0x10(SB), AX
MULQ t0
ADDQ BX, acc2
ADCQ $0, DX
ADDQ AX, acc2
ADCQ $0, DX
MOVQ DX, BX
MOVQ ·p2+0x18(SB), AX
MULQ t0
ADDQ BX, acc3
ADCQ $0, DX
ADDQ AX, acc3
ADCQ DX, acc4
ADCQ $0, acc5
乘法: 5
加法：15
使用MULXQ/ADCXQ/ADOXQ:
// First reduction step
MOVQ acc0, DX
MULXQ ·np+0x00(SB), DX, AX
MULXQ ·p2+0x00(SB), AX, t0
ADOXQ AX, acc0
MULXQ ·p2+0x08(SB), AX, BX
ADCXQ t0, AX
ADOXQ AX, acc1
MULXQ ·p2+0x10(SB), AX, t0
ADCXQ BX, AX
ADOXQ AX, acc2
MULXQ ·p2+0x18(SB), AX, BX
ADCXQ t0, AX
ADOXQ AX, acc3
ADCXQ res_ptr, BX
ADOXQ BX, acc4
ADOXQ res_ptr, acc5
乘法: 5
加法：10
方案二：(移位、加法、减法)
T_2=T_1 \ast O=Y \ast O= Y \ast 2^{256}-(Y \ast 2^{32}) \ast 2^{192} - Y \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=T + T_2=t_4 \ast 2^{256} + t_3 \ast 2^{192} + t_2 \ast 2^{128} + t_1 \ast 2^{64} + t_0 + Y \ast 2^{256}-(Y \ast 2^{32}) \ast 2^{192} - Y \ast 2^{128} + (Y \ast O_1) \ast 2^{64} + (Y \ast O_0)
T_3=(t_4+Y) \ast 2^{256}+(t_3 - Y \ast 2^{32}) \ast 2^{192} + (t_2 - Y) \ast 2^{128} + (t_1 + Y \ast O_1) \ast 2^{64} + (t_0 + Y \ast O_0)
T_3=(t_4+Y-Y>>32) \ast 2^{256}+(t_3 - Y<<32) \ast 2^{192} + (t_2 - Y) \ast 2^{128} + (t_1 + Y \ast O_1) \ast 2^{64} + (t_0 + Y \ast O_0)
依然采用先减后加！
伪代码：
// First reduction step
MOVQ acc0, AX
MULQ p256ordK0<>(SB)
MOVQ AX, t0
// 处理第一个加法，以便释放acc0
MOVQ p256ord<>+0x00(SB), AX
MULQ t0
ADDQ AX, acc0 // acc0 可以被释放了
ADCQ $0, DX
MOVQ DX, BX
// 开始处理减法
MOVQ t0, acc0
MOVQ t0, AX
MOVQ t0, DX
SHLQ $32, AX
SHRQ $32, DX
SUBQ t0, acc2
SBBQ AX, acc3
SBBQ DX, acc0
// 处理加法
MOVQ p256ord<>+0x08(SB), AX
MULQ t0
ADDQ BX, acc1
ADCQ $0, DX
ADDQ AX, acc1
ADCQ DX, acc2
ADCQ $0, acc3
ADCQ acc0, acc4
ADCQ $0, acc5
乘法: 3
移位：2
加法：9
减法：3
| 方案 | 乘法 | 移位 | 加法 | 减法 |
|---|---|---|---|---|
| 方案一 | 5 | 0 | 15 | 0 |
| 方案一（MULX/ADCX/ADOX） | 5 | 0 | 10 | 0 |
| 方案二 | 3 | 2 | 9 | 3 |
看来在支持MULXQ/ADCXQ/ADOXQ的情况下，使用方案一（MULX/ADCX/ADOX）更好！
两个移位vs.一个乘法
两个移位操作和一个乘法操作的性能哪个好？
MOVQ t0, AX
MOVQ t0, DX
SHLQ $32, AX
SHRQ $32, DX
vs.
MOVQ $0x100000000, AX
MULQ t0
MULX版本：
MOVQ $0x100000000, DX
MULXQ t0, AX, DX