Regular and Efficient doubling in $GF(2^n)$ A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe against timing attack.

Does there exist optimization techniques to implement $2 \cdot a$ for $a \in GF(2^n)$  in a regular way ?

If we consider $GF(2^4)$ defined by the polynomial $X^4 + X + 1$ (represented by 0x13 in hexadecimal), the most efficient solution I found is to compute $2 \cdot a$ as described below (in C code)

 (a&lt;&lt;1) ^ (0x20 - ((a &amp; 0x8) &gt;&gt; 3)) &amp; 0x13


Can we do better in terms of efficiency without precomputations?
TL;DR; The general formula is; 

$x := deg(primitive \;\; polynomial) -1 $

$$(a \ll 1) \oplus ((1 \ll (x +3)) - [(a \wedge (1 \ll x)) \gg x]) \wedge \{p.p\}$$

A simplification by Dave's comment;

$((a\gg deg) \wedge 1) = ((a\wedge (1 \ll deg)) \gg deg)$

$$\{2\}* a = (a \ll 1) \oplus ((1 \ll (x +3)) - [(a\gg (x-1)) \wedge 1) ] \wedge \{p.p\}$$



In the comment, I said that "for the general case, there is no generic algorithm". I was completely wrong. This algorithm indeed generic.


  
  case: Why works in $GF(2^4)$ with the primitive polynomial (p.p.) $x^4+x+1 = \{0x13\}$
  


(a&lt;&lt;1) ^ (0x20 - ((a &amp; 0x8) &gt;&gt; 3)) &amp; 0x13


represent the $a$ as letters in binary $a=\{x_3,x_2,x_1,x_0\}$ let see how the calculation really works.


$b = a \ll 1 = \{x_3,x_2,x_1,x_0,0\}$
$c = a \;\&amp;\; 0x8= \{x_3,0,0,0\}$
$d = c \gg 3 = \{x_3\}$
$e = 0x20 - \{x_3\}$ this is the tricky part.


if $\{x_3\} = 0$ than $e = \{1,0,0,0,0,0\} = 0x20$


$b = \{y,z,t,0\}$ //since $x_3=0$
$f = e \;\&amp;\; 0x13 = \{1,0,0,0,0,0\} \;\&amp;\; \{1,0,0,1,1\} = \{0,0,0,0\}$
$2\cdot A= b \oplus e = \{x_2,x_1,x_0,0\} \oplus \{0,0,0,0\} = \{x_2,x_1,x_0,0\} $  

if $\{x_3\} = 1$ than $e = \{x_3,x_3,x_3,x_3,x_3\}$


$f = e \;\&amp;\; 0x13 = \{x_3,x_3,x_3,x_3,x_3\} \;\&amp;\; \{1,0,0,1,1\} = \{x_3,0,0,x_3,x_3\}$
$2 \cdot A= b \oplus e = \{x_3,x_2,x_1,x_0,0\} \oplus \{x_3,0,0,x_3,x_3\} = \{x_2,x_1,x_0 \oplus x_3, x_3\} $ 





  
  case: AES $GF(2^8)$ with the primitive polynomial  $x^8 + x^4 + x^3 + x + 1 = \{0x11b\}$
  


(a&lt;&lt;1) ^ (0x200 - ((a &amp; 0x80) &gt;&gt; 7)) &amp; 0x11b


This is exactly same steps only with different size and primitive polynomial; 

represent the $a$ as letters in binary $a=\{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0\}$ 


$b = a \ll 1 = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$
$c = a \;\&amp;\; 0x8= \{x_7,0,0,0,0,0,0,0\}$
$d = c \gg 7 = \{x_7\}$
$e = 0x200 - \{x_7\}$ 


if $\{x_7\} = 0$ than $e = \{1,0,0,0,0,0,0,0,0,0\} = 0x200$


$b = \{x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$ //since $x_7=0$
$f = e \;\&amp;\; 0x11b = \{1,0,0,0,0,0,0,0,0,0\} \;\&amp;\; \{1,0,0,0,1,1,0,1,1\} = \{0,0,0,0,0,0,0,0\}$
$\{2\}\cdot A= b \oplus f = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\} \oplus  \{0,0,0,0,0,0,0,0\} = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\} $  

if $\{x_7\} = 1$ than $e = \{x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7\}$


$f = e \;\&amp;\; 0x11b = \{x,x,x,x,x\} \;\&amp;\; \{1,0,0,0,1,1,0,1,1\} = \{x_7,0,0,0,x_7,x_7,0,x_7,x_7\}$
$\{2\} \cdot A= b \oplus f = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}  \oplus \{x_7,0,0,0,x_7,x_7,0,x_7,x_7\} = \\ \{x_6,x_5,x_4,x_3 \oplus x_7,x_2 \oplus x_7,x_1 ,x_0 \oplus x_7,x_7\} $ 





  
  General formula
  


$x := deg(primitive \;\; polynomial) -1 $

$$(a \ll 1) \oplus ((1 \ll (x +3)) - [(a \wedge (1 \ll x)) \gg x]) \wedge \{p.p\}$$

sketch of proof;

Normally we use primitive polynomial $p = \{x_n,\ldots,x_0\}$ of degree $n$ to represent $x^n = p -x_n$ to replace the $x^n$ as;

let $a=\{a_n,\ldots,a_0\}$ than $\{2\}a=\{a_n,\ldots,a_0,0\}$

if $a_n = 0$ there is nothing to do, $\{2\}a=\{a_{n-1},\ldots,a_0,0\}$ 

if $a_n = 1$, we add the $x^n = p -x_n$ to the polynomial 

$$\{2\}a=\{a_{n-1},\ldots,a_0,0\} + p$$ 

The algorithm cleverly combines the two cases $a_n =0$ and $a_n=1$. if $a_n =0$ the $\oplus$ part is just $\{0,\ldots,0\}$ with masked the p.p. If not; then it is exactly $x_n-p$.