Skip to content

SM2 WWMM (2)

Jump to bottom
Sun Yimin edited this page Aug 1, 2024 · 27 revisions

本文讨论了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&gt;&gt;32) \ast 2^{256}+(t_3 - t_0&lt;&lt;32) \ast 2^{192} + (t_2 - t_0&gt;&gt;32) \ast 2^{128} + (t_1 + t_0 - t_0&lt;&lt;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&gt;&gt;32) \ast 2^{256}+(t_3 - Y&lt;&lt;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&gt;&gt;32) \ast 2^{256}+(t_3 - Y&lt;&lt;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
Clone this wiki locally