1 Introduction

Threshold implementations (TI) are a kind of side-channel attack countermeasures, based on secret sharing schemes and techniques from multiparty computation. The idea is to split a variable x into s additive shares \(x_i\) with \(x =\sum _{i=1}^s x_i\). Let \(\textbf{x}=(x_1,x_2,\ldots ,x_s)\). To implement a function \(F(x,y,z,\ldots ,)=a\) from \({\mathbb F}_2^m\) to \({\mathbb F}_{2}^n\), the TI method requires sharing, that is, a set of s functions \(F_i\), which together can compute the output of F. Sharing needs to satisfy some properties, namely, correctness, non-completeness and uniformity [10]:

  • Correctness: \(a=F(x,y,z,\ldots )=\sum _{i=1}^sF_i(\textbf{x},\textbf{y},\textbf{z},\ldots )\), for all \(\textbf{x},\textbf{y},\textbf{z},\ldots ,\) with \(x=\sum _{i=1}^s x_i,y=\sum _{i=1}^s y_i,z=\sum _{i=1}^sz_i\).

  • Non-completeness: Every function is independent of at least one share of the input variables x, y, z (\(F_i\) should be independent of \(x_i,y_i,z_i\)).

  • Uniformity (balancedness): For all \((a_1,a_2,\ldots ,a_s)\) with \(\sum _{i=1}^s a_i=a\), the number of tuples \((\textbf{x},\textbf{y},\textbf{z},\ldots )\in {\mathbb F}_2^{ms}\) for which \(F_j(\textbf{x},\textbf{y},\textbf{z},\ldots )=a_j,1\le j\le s\), is equal to \(2^{(s-1)(m-n)}\) times the number of \((x,y,z,\ldots )\in {\mathbb F}_2^m\), for which \(a=F(x,y,z,\ldots )\). So, if F is a permutation on \({\mathbb F}_2^m\), then the \(F_i\)’s form together a permutation on \(F_2^{ms}\) (sharing preserves the output distribution).

We should mention earlier work on the Gold function, where TI was achieved for all \(3\times 3,4\times 4\) S-boxes [1], and the realization of the inversion in \(\mathbb {F}_{16}\) with 5 shares [10]. One notes that since each \(F_i\) is completely independent of the unmasked values, also the subcircuits implementing them are, even in the presence of glitches. Because of the linearity of the expectation operator, the same holds true for the average power consumption of the whole circuit, or any linear combination of the power consumptions of the subcircuits. This has, as a consequence, the implication that one has perfect resistance against all first-order side-channel attacks [10] (this approach was extended and applied to Noekeon, Keccak, Present, and AES).

Now, in order to share a nonlinear function (S-box) with algebraic degree d, at least \(d+1\) shares are needed. For example, (quadratic) Gold (APN or not) functions can be realized with 3 shares. Since the algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation, a natural question is whether we decompose every permutation using affine/quadratics/cubics (especially of those whose shares are investigated).

Prior to this, in [2], Carlitz showed that all permutation polynomials over \({\mathbb F}_q\), where \(q>2\) is a power of a prime, are generated by the special permutation polynomials \(x^{q-2}\) (the inversion) and \( ax+b\) (affine functions, where \(0\ne a, b\in {\mathbb F}_q\)). The smallest number of inversions in such a decomposition is called the Carlitz rank.

Here, we ask whether the inverse in \({\mathbb F}_{2^n}\) (the finite field of dimension n over the two-elements prime field \({\mathbb F}_2\)) can be written as a composition of quadratics, or quadratics and cubics. That is, we ask if there are integers \(r\ge 1\) and \(a_1\ge 0,\ldots ,a_r\ge 0\) such that

$$\begin{aligned} -1\equiv \prod _{i=1}^r (2^{a_i}+1)\pmod {2^n-1}. \end{aligned}$$

Nikova, Nikov and Rijmen [9] proposed an algorithm to find such a decomposition. Leveraging Carlitz’s work [2], they utilized the algorithm to demonstrate that for all \(n\le 16\), any permutation can be decomposed into quadratic permutations, when n is not a multiple of 4, and into cubic permutations, when n is a multiple of 4. In addition to a theoretical result, which we will discuss below, Petrides [11] improved the complexity of the algorithm and presented a computational table of shortest decompositions for \(n\le 32\), allowing also cubic permutations in addition to quadratics. Here, we find a new number theoretical approach that allows us to cover all (surely, odd) exponents up to 250, at least.

2 Heuristics and some conjectures

Let \(\nu _2\) be the 2-valuation, that is, the largest power of 2 dividing the argument. We start with a proposition, extending one of Petrides’ results [11], which states that if n is an odd integer and \(\frac{n-1}{2^{\nu _2(n-1)}}\equiv 2^k\pmod {2^n-1}\), for some k, then

$$\begin{aligned} 2^n-2&=2\left( 2^{\left( \frac{n-1}{2^{\nu _2(n-1)}}\right) 2^{\nu _2(n-1)}}-1\right) \\&=2\left( 2^{\frac{n-1}{2^{\nu _2(n-1)}}}-1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&\equiv 2\left( 2^{2^k}-1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&= 2\prod _{j=0}^{k-1}\left( 2^{2^j}+1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) . \end{aligned}$$

This implies, via Carlitz [2], that for all odd integers (coined good integers, with the counterparts named bad integers in [7]) satisfying the congruence \(\frac{n-1}{2^{\nu _2(n-1)}}\equiv 2^k\pmod {2^n-1}\), one can decompose any permutation polynomial in \({\mathbb F}_{2^n}\) into affine and quadratic power permutations.

The smallest odd positive integer that is not good is \(n=7\). We note however that in that case

$$\begin{aligned} 2^7-2=2(2^6-1)=2(2^2-1)(2^4+2^2+1)=2(2+1)(2^4+2^2+1), \end{aligned}$$

and so, any permutation in \({\mathbb F}_{2^7}\) can be decomposed into affine, quadratic and cubic permutations. We are ready to generalize this observation.

Theorem 1

Let n be an odd integer satisfying

$$\begin{aligned} \frac{n-1}{2^{\nu _2(n-1)}}\equiv 2^k3^s\pmod {2^n-1}, \end{aligned}$$

for some non-negative integers k, s. Then, the inverse power permutation in \({\mathbb F}_{2^n}\) has a decomposition into affine, quadratic and cubic power permutations of length \(k+s+\nu _2(n-1)\).

Proof

As we have already alluded to above, using the difference of cubes factorization, \(a^3-b^3=(a-b)(a^2+ab+b^2)\), we have

$$\begin{aligned} 2^n-2&=2\left( 2^{\frac{n-1}{2^{\nu _2(n-1)}}}-1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&\equiv 2 \left( 2^{2^k3^s}-1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&= 2\left( 2^{2^k 3^{s-1}}-1\right) \left( 2^{2^{k+1}3^{s-1}}+2^{2^k3^{s-1}}+1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&\cdots \cdots \cdots \cdots \\&=2 \left( 2^{2^k}-1\right) \prod _{j=0}^{s-1} \left( 2^{2^{k+1}3^j}+2^{2^k 3^j}+1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) \\&\equiv 2\prod _{j=0}^{k-1}\left( 2^{2^j}+1\right) \prod _{j=0}^{s-1} \left( 2^{2^{k+1}3^j}+2^{2^k 3^j}+1\right) \prod _{j=1}^{\nu _2(n-1)}\left( 2^{\frac{n-1}{2^j}}+1\right) . \end{aligned}$$

The claim is shown.

Example 1

It is natural to investigate the counting function \(\mathcal {B}(x)\) of superbad integers (that is, integers n such that \(\frac{n-1}{2^{\nu _2(n-1)}}\not \equiv 2^k3^s\pmod {2^n-1}\)), with \(\mathcal {B}(x)=\{n\le x\,:\, n\text { is superbad}\}\), or its complement

$$\begin{aligned} \mathcal {A}(x)=\{n\le x\,:\, \frac{n-1}{2^{\nu _2(n-1)}}\equiv 2^k3^s\pmod {2^n-1}\}. \end{aligned}$$

As an example, \(|\mathcal {B}(50)|=16\), more precisely,

$$\begin{aligned} \mathcal {B}(50)=\{1, 2, 3, 4, 5, 7, 9, 10, 13, 17, 19, 25, 28, 33, 37, 49\}. \end{aligned}$$

Petrides [11] noted that 25 integers up to 50 are bad, so our extension surely prunes the integers better. In a recent paper [5], two of us showed that

$$\begin{aligned} \mathcal {A}(x)\ll \frac{x}{(\log \log x)^{1+o(1)}}, \quad {\text {as}}\quad x\rightarrow \infty . \end{aligned}$$

In the first part of our paper, we restrict our attention to \(n=p\), a prime, and propose some conjectures that will help us in designing our algorithm. Surely, there is no reason why we should not expect the algorithm to work for odd integers, also.

Let \(p\ge 3\) be prime, \(N:=N_p=2^p-1\). It is known that if \(q\mid N_p\), then \(q\equiv 1\pmod {p}\). We ask if we can say anything about the number of distinct prime factors \(\omega (N_p)\) of \(N_p\). We propose the following conjecture.

Conjecture 1

There exists \(p_0\) such that for \(p>p_0\), \(\omega (N_p)<1.36\log p\).

Similar heuristics regarding lower bounds for \(\Omega (2^n-1)\) and \(\omega (2^n-1)\) can be found in [4] and [6].

Our Conjecture 1 is based on statistical arguments originating from sieve methods. The Turán-Kubilius inequality asserts that

$$\begin{aligned} \sum _{n\le x} (\omega (n)-\log \log x)^2=O(x\log \log x). \end{aligned}$$

So, if \(\delta >0\) is fixed, the set of \(n\le x\) such that \(\omega (n)\ge (1+\delta )\log \log x\) is of counting function \(O_{\delta }(x/\log \log x)\). One can do better using sieves. Indeed, Exercise 04 in [3] shows that for fixed \(\delta >0\) we, in fact, have that

$$\begin{aligned} \#\{n\le x: \omega (n)\ge (1+\delta )\log \log x\}\ll _{\delta } \frac{x}{(\log x)^{Q(\delta )}}, \end{aligned}$$

where \(Q(\delta ):=(1+\delta )\log ((1+\delta )/e)+1\). We would like to apply such heuristics to \(N_p=2^p-1\). But note that if \(q\mid N_p\), then \(2^p\equiv 1\pmod q\). In particular, \({\displaystyle {\left( \frac{2}{q}\right) =1}}\), so \(q\equiv \pm 1\pmod 8\). But then the same proof as Exercise 04 in [3] shows that

$$\begin{aligned}&\#&\{n\le x: q\mid n \Rightarrow q\equiv \pm 1\pmod 8 \quad {\text {and}} \quad \omega (n)\ge (1+\delta )\log \log x\}\\\le & {} \frac{x}{(\log x)^{Q_1(\delta )+o(1)}} \end{aligned}$$

as \(x\rightarrow \infty \), where \(Q_1(\delta ):=(1+\delta )\log ((1+\delta )/(0.5 e))+1\). Taking \(\delta =0.36\), we get \(Q_1(\delta )=1.00086\ldots \). Thus, the probability that a number having only prime factors congruent to \(\pm 1\pmod 8\) has more than \(1.36\log \log n\) distinct prime factors is

$$\begin{aligned} O\left( \frac{1}{(\log n)^{1.00008}}\right) . \end{aligned}$$

Applying this to \(N_p\), we get

$$\begin{aligned} O\left( \frac{1}{(\log (2^p-1))^{1.0008}}\right) \ll \frac{1}{p^{1.0008}}, \end{aligned}$$

and since the series

$$\begin{aligned} \sum _{p\ge 3} \frac{1}{p^{1.0008}} \end{aligned}$$

is convergent, we are led to believe that maybe there are at most finitely many prime numbers p such that \(\omega (N_p)\ge 1.36\log p\). It has been noted that perhaps infinitely often \(\omega (N_p)\ge 2\). For example, this is the case if \(p\equiv 3\pmod 4\) is such that \(q=2p+1\) is prime. Indeed, then 2 is a quadratic residue modulo q so \(2^{(q-1)/2}\equiv 1\pmod q\), showing that \(q\mid N_p\). Since \(N_p\) is never a perfect power, in particular it cannot be a power of q, we get the desired conclusion that \(\omega (N_p)\ge 2\).

Conjecture 2

There exists \(p_0\) such that if \(p>p_0\), then \(N _p\) is squarefree.

We offer some heuristic evidence for Conjecture 2. Knowing that the prime q divides \(N_p\), the conditional probability that \(N_p\) is divisible by \(q^2\) is 1/q. Thus, the probability that \(N_p\) is not squarefree is bounded above by

$$\begin{aligned} \sum _{q: q\mid N_p~{\text {for~some~prime}}~p} \frac{1}{q}, \end{aligned}$$

and it was shown by Murata and Pomerance in [8] that the above sum is finite under GRH.

So, assuming Conjectures 1 and 2, let \(N_p:=q_1\cdots q_k\) for some distinct primes \(q_1,\ldots ,q_k\) with \(k\le 1.36\log p\). We take numbers of the form \(2^a+1\) with an odd \(a\in [5,p-2]\). We want to compute

$$\begin{aligned} \left( \frac{2^a+1}{2^p-1}\right) . \end{aligned}$$

This was done by Rotkiewicz in [12]. Namely, write the Euclidean algorithm with even quotients and signed remainders:

$$\begin{aligned} p= & {} (2k_1)a+\varepsilon _1 r_1,\quad \varepsilon _1\in \{\pm 1\},\quad 1\le r_1\le a-1\\ a= & {} (2k_2) r_1+\varepsilon _2 r_2,\quad \varepsilon _2\in \{\pm 1\},\quad 1\le r_2\le r_1-1,\\ \ldots= & {} \ldots \\ r_{\ell -2}= & {} (2k_{\ell }) r_{\ell -1} +\varepsilon _{\ell } r_\ell ,\quad \varepsilon _{\ell }\in \{\pm 1\},\quad r_{\ell }=1, \end{aligned}$$

where \(\ell :=\ell (a,p)\) is minimal with \(r_{\ell }=1\). Note that \(r_i\) are all odd for \(i=1,\ldots ,\ell \). In particular, \(r_j\ge 3\) for \(j=1,\ldots ,\ell -1\). Then

$$\begin{aligned} \left( \frac{2^a+1}{2^p-1}\right) =\left( \frac{2^p-1}{2^a+1}\right) =\left( \frac{(2^a)^{2k_1}\cdot 2^{\varepsilon _1 r_1}-1}{2^a+1}\right) = \left( \frac{2^{\varepsilon _1 r_1}-1}{2^a+1}\right) =\left( \frac{2^{r_1}-1}{2^a+1}\right) . \end{aligned}$$

The right–most equality is clear if \(\varepsilon _1=1\), and if \(\varepsilon _1=-1\), then

$$\begin{aligned} \left( \frac{2^{-r_1}-1}{2^a+1}\right)= & {} \left( \frac{2}{2^a+1}\right) ^{r_1} \left( \frac{2^{-r_1}-1}{2^a+1}\right) =\left( \frac{2^{r_1}(2^{-r_1}-1)}{2^a+1}\right) \\= & {} \left( \frac{1-2^{r_1}}{2^a+1}\right) =\left( \frac{-1}{2^a+1}\right) \left( \frac{2^{r_1}-1}{2^a+1}\right) = \left( \frac{2^{r_1}-1}{2^a+1}\right) . \end{aligned}$$

The above calculation shows how to transit from the first step to the second step, or more generally from a step with \(2^{r_j}-1\) in the bottom to a step with \(2^{r_j}-1\) in the top. For the next step, we write

$$\begin{aligned} \left( \frac{2^{r_1}-1}{2^a+1}\right) =\left( \frac{2^a+1}{2^{r_1}-1}\right) =\left( \frac{(2^{r_1})^{2k_2}\cdot 2^{\varepsilon _2 r_2}+1}{2^{r_1}-1}\right) =\left( \frac{2^{\varepsilon _2 r_2}+1}{2^{r_1}-1}\right) =\left( \frac{2^{r_2}+1}{2^{r_1}-1}\right) . \end{aligned}$$

The last inequality above is clear if \(\varepsilon _2=1\). If \(\varepsilon _2=-1\), then since \(r_1\ge 3\), we have

$$\begin{aligned} \left( \frac{2^{-r_2}+1}{2^{r_1}-1}\right) =\left( \frac{2}{2^{r_1}-1}\right) ^{r_2}\left( \frac{2^{-r_2}+1}{2^{r_1}-1}\right) =\left( \frac{2^{r_2}(2^{-r_2}+1)}{2^{r_1}-1}\right) =\left( \frac{2^{r_2}+1}{2^{r_1}-1}\right) . \end{aligned}$$

At step \(\ell \) we end up with

$$\begin{aligned} \left( \frac{2^{r_{\ell }}+(-1)^{\ell }}{2^{r_{\ell -1}}+(-1)^{\ell -1}}\right) . \end{aligned}$$

If \(\ell (a,p)\) is odd, we get

$$\begin{aligned} \left( \frac{2^1-1}{2^{r_{\ell -1}}+1}\right) =1, \end{aligned}$$

and if \(\ell (a,p)\) is even we get

$$\begin{aligned} \left( \frac{2^1+1}{2^{r_{\ell -1}}-1}\right) =-\left( \frac{2^{r_{\ell -1}}-1}{3}\right) =-\left( \frac{1}{3}\right) =-1. \end{aligned}$$

We thus get that

$$\begin{aligned} \left( \frac{2^a+1}{2^p-1}\right) =(-1)^{\ell +1}. \end{aligned}$$

We select the subset \(\mathcal {A}(p)\) of odd a in the interval \([5,p-2]\) such that \(\ell \equiv 0\pmod 2\). We assume that there are a positive proportion of such, namely that there is a constant \(c_1>0\) such that for large p, there are \(>c_1p\) odd numbers \(a\in [5,p-2]\) such that \(\ell (a,p)\equiv 0\pmod 2\). So, we have

$$\begin{aligned} \prod _{i=1}^k \left( \frac{2^a+1}{q_i}\right) =-1\quad {\text {for}}\quad a\in \mathcal {A}(p). \end{aligned}$$

We next conjecture that for such a, the values are

$$\begin{aligned} \left( \left( \frac{2^a+1}{q_i}\right) ,1\le i\le k\right) \end{aligned}$$
(1)

are uniformly distributed among the \(2^k\) vectors \({\underbrace{(\pm 1,\pm 1,\cdots ,\pm 1)}_{k~{\text {times}}}}\). Indeed, if not, then somehow for some a the value of \(2^a+1\) of the Legendre symbol \({\displaystyle {\left( \frac{2^a+1}{p_i}\right) }}\) should be determined in terms of the values of the same symbol for \(b\le a-1\). This can happen for example if:

(i):

\(2^a+1\) is a square. This never happens for \(a\ge 4\).

(ii):

\(2^a+1\) is multiplicatively dependent over \(\{2^b+1: 0\le b\le a-1\}\). This does not happen for \(a\ge 4\) because of the Carmichael’s Primitive Divisor Theorem: \(2^a+1\) has a prime factor \(p_a\) which is primitive in the sense that \(p_a\) does not divide \(2^b+1\) for any \(b\le a-1\).

Well, so we fix \(i\in \{1,\ldots ,k\}\) and search for \(a_i\) such that

$$\begin{aligned} \left( \frac{2^{a_i}+1}{q_i}\right) =(-1)^{\delta _{ij}}, \end{aligned}$$
(2)

where \(\delta _{ij}\) is the Kronecker symbol. That is, \(2^{a_i}+1\) is a quadratic residue modulo \(p_j\) for all \(j\ne i\) but it is not a quadratic residue modulo \(q_i\). Do we expect to find it? Well, let us see. Fix i in \(\{1,\ldots ,k\}\). The probability that \(2^{a_i}+1\) verifies the Legendre conditions given by (2) is \(1/2^k\) so it is \((1-1/2^k)\) that they are not satisfied. Note that since \({\displaystyle {\left( \frac{2^{a_i}+1}{N_p}\right) =-1}}\) we know that an odd number of the \(p=p_j\)’s satisfy that \({\displaystyle {\left( \frac{2^{a_i}+1}{p_j}\right) =1}}\). So, if we assume that this is so for all possible \(a_i\)’s, and assuming that these events are independent, we get that the probability that this be so is

$$\begin{aligned} \ll \left( 1-\frac{1}{2^{k}}\right) ^{c_1 p}<\left( 1-\frac{1}{p^{1.36\log 2}}\right) ^{c_1p}<\left( 1-\frac{1}{p^{0.95}}\right) ^{c_1 p}\ll \frac{1}{e^{c_1 p^{0.05}}}. \end{aligned}$$

In the above, we used that \(k<1.36\log p\) and \(1.36\cdot \log 2<0.95\). Of course, this is for i fixed and now we sum up over i from 1 to k introducing another logarithmic factor in the above count. Since the series

$$\begin{aligned} \sum _{p} \frac{\log p}{e^{c_1 p^{0.05}}} \end{aligned}$$

converges, so we expect that the above event does not occur when \(p>p_0\). So, we have the following conjecture.

Conjecture 3

Assume Conjectures 1 and 2. Write \(2^p-1=q_1\ldots q_k\) for \(p>p_0\) with prime factors \(q_1<\cdots <q_k\) and \(k<1.36\log p\). Then for each \(i=1,\ldots ,k\), there exists an odd \(a_i\in [5,p-2]\) such that equalities (2) hold.

3 Unconditional argument and our decomposition algorithm

The rest of the proof is unconditional. We will show that there exist integers \(x_i\) such that

$$\begin{aligned} (-1)=\prod _{i=1}^k (2^{a_i}+1)^{x_i}\pmod {2^p-1}. \end{aligned}$$
(3)

We will be more precise later, but the idea of our approach is the following. For a prime p below some bound (depending upon the speed of the computer), factor (via the database from the Cunningham project or the computer), \(2^p-1=q_1\cdots q_k\), (\(q_i\) primes), and for each i we search for \(a_i\) in \([5,p-2]\) odd such that for each such, \(2^{a_i}+1\) is a QR (quadratic residue) modulo \(q_j\) for all \(j\ne i\) in \(\{1,\ldots ,k\}\) and a QNR (quadratic non-residue) modulo \(q_i\). We then generate some primitive roots modulo \(q_i\) and compute the invertible matrix \(\mathcal {B}\) and find values for the \(x_i\)’s. There is no reason why we should not expect this to happen to odd integers n (again under some manageable bound) and do the same for \(2^n-1\) (choose a odd with \(\gcd (a,n)=1\)). We now detail this below.

Write \(q_i-1=:2^{\alpha _i} R_i\) for \(i=1,\ldots ,k\), where \(R_i\) is odd. Let

$$\begin{aligned} R:={\text {lcm}}[R_i:1\le i\le k] \end{aligned}$$

and write \(x_i=y_ iR\) for \(i=1,\ldots ,k\). Let \(\rho _i\) be a primitive root modulo \(q_i\). Write

$$\begin{aligned} 2^{a_i}+1=\rho _j^{b_{ij}}\pmod {q_j}. \end{aligned}$$
(4)

Conditions (2) show that \(b_{ij}\equiv \delta _{ij}\pmod 2\). Equation (3) holds if and only if it holds one prime \(q_j\) at a time. Thus, we want

$$\begin{aligned} \rho _j^{(q_j-1)/2}\equiv \rho _j^{R\sum _{i=1}^k y_i b_{ij}}\pmod {q_j}, \end{aligned}$$

which holds provided that

$$\begin{aligned} \frac{(q_j-1)}{2}\equiv R\sum _{i=1}^k y_i b_{ij}\pmod {q_j-1}. \end{aligned}$$

This in turn is equivalent to

$$\begin{aligned} 2^{\alpha _j-1} \equiv (R/R_j) \sum _{i=1}^k y_i b_{ij}\pmod {2^{\alpha _j}}. \end{aligned}$$

Since \(R/R_j\) is odd, it follows that it is invertible modulo \(2^{\alpha _j}\). Writing \((R/R_j)^*\) for the inverse of \((R/R_j)\) modulo \(2^{\alpha _j}\), we get that

$$\begin{aligned} 2^{\alpha _j-1} (R/R_j)^*\equiv \sum _{i=1}^k y_i b_{ij}\pmod {2^{\alpha _j}}. \end{aligned}$$

Since \((R/R_j)^*\) is odd the left–hand side is just \(2^{\alpha _j-1}\pmod {2^{\alpha _j}}\). Thus,

$$\begin{aligned} 2^{\alpha _j-1} \equiv \sum _{i=1}^k y_i b_{ij}\pmod {2^{\alpha _j}}. \end{aligned}$$

This is a linear system of modular equations for \(i=1,\ldots ,k\). To see that it is nondegenerate note that the coefficient matrix \(\mathcal {B}=(b_{ij})_{1\le i,j\le k}\) modulo 2 is in fact the identity matrix. Hence, its determinant is an odd integer, so invertible modulo powers of 2, which shows that there exist an integer solution \(y_1,\ldots ,y_k\). To solve it, we can generate for each i, j the number \(b_{i,j}\pmod {2^{\alpha _j}}\) appearing in (4) as an integer in the interval \([0,2^{\alpha _j}-1]\). Having done that, we solve the linear system

$$\begin{aligned} \sum _{i=1}^k y_i b_{ij}=2^{\alpha _j-1}\quad {\text {for}}\quad j=1,2,\ldots ,k. \end{aligned}$$

This is non-degenerate since the determinant of the coefficient matrix is odd. Thus, \((y_1,\ldots ,y_k)\) are some rational numbers. Now we treat them as residue classes modulo \(2^{\alpha }\), where \(\alpha :=\max \{\alpha _i: 1\le i\le k\}\) (by inverting the odd determinant modulo \(2^{\alpha }\)). These ones are the \(y_i\)’s that we are looking for.

We implemented this and checked it for all primes \(p\le 250\). We present our approach in Algorithm 1.

Algorithm 1
figure a

 .

Full size image

The factorization of \(2^p-1\) is known for all primes \(p<1000\). Surely, we can use the same algorithm modulo \(2^n-1\) for \(n\le 250\) and odd. Note that if

$$\begin{aligned} 2^n-1=\prod _{j=1}^k q_j^{\alpha _j}, \end{aligned}$$

then we only want to find a relation of the form

$$\begin{aligned} (-1)\equiv \prod _{i=1}^k (2^{a_i}+1)^{x_i}\pmod {q_1\ldots q_k}. \end{aligned}$$
(5)

Indeed, if we have found the above relation, then

$$\begin{aligned} q_1\ldots q_k\mid (2^{a_1}+1)^{x_1}\cdots (2^{a_k}+1)^{x_k}+1. \end{aligned}$$

Writing \(Q:=(2^n-1)/(q_1\ldots q_k)\), we then get easily that

$$\begin{aligned} (2^n-1)\mid (2^{a_1}+1)^{x_1 Q} (2^{a_2}+1)^{x_2 Q}\cdots (2^{a_k}+1)^{x_k Q}+1. \end{aligned}$$

Thus,

$$\begin{aligned} (-1)\equiv \prod _{i=1}^k (2^{a_i}+1)^{x_i Q}\pmod {2^n-1}. \end{aligned}$$

Thus, we factor \(2^n-1\), take \(q_1,\ldots ,q_k\) to be all its distinct prime factors and attempt to find some numbers \(a_1,\ldots ,a_k\) in \([5,n-2]\) such that the congruences (2) are satisfied. If we are successful, then the argument based on the matrix with an odd determinant will work to find a solution of (5), which in turn can be easily lifted to a solution modulo \(2^n-1\). The factorizations of \(2^n-2\) with weight 2 factors for odd \(33 \le n \le 249\) are given in Table 1, in the appendix.

Remark 1

We have checked that Algorithm 1 works for most primes up to 250. But there are a few primes like 47 for which there is no \(a_j \in [5, p-2]\) such that \(\left( \frac{2^{a_j}+1}{q_i}\right) =(-1)^{\delta _{ij}}\). In these cases, we use the following trick. We first find \(a_i\) and calculate \((\frac{2^{a_j}+1}{q_i})=(-1)^{d_{i,j}}\). Ideally, \(d_{i,j}\) should be Kronecker symbols, but if they are not, we can just record what they are. Because \(d_{i,j}\) are no longer Kronecker symbols, we cannot be certain that the system is solvable because it may have an even determinant and we cannot invert the matrix modulo powers of 2. However, we checked primes (and odd integers) up to 250. We observed that in the case of failure, we can use this trick and always get suitable \(a_i\)’s such that the corresponding matrix has odd determinant, and is therefore invertible.

4 Further comments

One can go further than our choice of bound, namely 250, by using our method. We have yet to encounter an exponent for which we cannot apply Algorithm 1. If there is such an exponent n for which we cannot find \(a_j\), \(d_{i,j}\) as above, then we can involve cubics in the factorization of \(-1\pmod {2^n-1}\). More precisely, we do something similar as above using \(2^{a_i}+2^{b_i}+1\) and check if we can find such powers \(a_i,b_i\) such that the number above is a quadratic nonresidue modulo \(q_i\) and quadratic residue modulo \(q_j\) for all \(j\ne i\). The rest of Algorithm 1 runs unchanged.

While, via Carlitz’ result, we know that any permutation can be decomposed as a composition of inverses and affine functions, it would also be interesting to check whether one can modify our method in this paper to other exponents, other than the inverse and surely, the Gold \(2^k+1\) exponents, to directly find their decomposition in quadratics, or quadratics and cubics, and we leave that for future work and the interested reader.