"Mighty" Euler Quotients

 ▉ Fermat quotients have been mentioned several times in this blog. The definition is 

\begin{equation}q_p(2) = \frac{2^{p-1}-1}{p},\;\;p \in \mathbb{P} \end{equation} One can extend this definition to composite integers $n$, which are called Euler quotients. \begin{equation} q^*_n(2) = \frac{2^{\varphi(n)}-1}{n},\;\;n \in \mathbb{N} \end{equation} In this short post, i would like to demonstrate the power of these Euler Quotients.

 

Suppose you have an Oracle $\mathcal{O}$ that, given an integer $n$, returns $q^*_n(2)$. Only one such query is allowed. We treat $q^*_n(2)$ simply as a binary string and show that this string contains enough information to compute things that are otherwise hard to compute.

Therefore we assume that $n=p\cdot q$, for two distinct primes $p,q$ of the form $p \equiv q \equiv 7\pmod{8}$ and $2$ has order exactly $(p-1)/2$ and $(q-1)/2$ respectively. 

Then you can use the $q^*_n(2)$ to compute the following information:

1. Factorization of $n$. The term $(2^{\varphi(n)}-1)$ is an integer with $\varphi(n)$ bits. If we let $m$ be the bitlength of $n$, we can conclude that $q^*_n(2)$ is an integer of length $\varphi(n)-m-1$. Hence we get 

\begin{equation} \lfloor \text{log}_2(q^*_n(2))\rfloor + \lfloor \text{log}_2(n)\rfloor + 1 = \varphi(n) \end{equation}

From $\varphi(n)$ you can trivially compute $p,q$, since \begin{equation} \varphi(n) = (p-1)(q-1) = n-(p+q)+1\end{equation} From this you get $p+q$ and and hence $p$ and $q$. According to the law of quadratic reciprocity, it holds that $\binom{p}{q}\binom{q}{p} = -1$ ,for two primes of the given form. We assume w.l.o.g $\binom{q}{p} = -1$ ($\binom{\cdot}{\cdot}$ is the Legendre symbol.)

2. Class number h(-p). Point 1 was not particularly surprising. However one could compute the class number $h(-p)$, which is related to the Hamming Weight (HW) of $q^*_n(2)$. (Note: $h(-q)$ can not be computed in this way, due to the Legendre symbol $\binom{p}{q} = 1$). The relationship is \begin{equation} \frac{\text{HW}(q^*_n(2))}{4} = \frac{\varphi(n)}{8} - \frac{h(-p)}{2} \end{equation} hence

\begin{equation} \frac{\varphi(n)}{4} -  \frac{\text{HW}(q^*_n(2))}{2} = h(-p)\end{equation}

3. Class number h(-n). The class number is related to the number of "real" quadratic residues $<n/4$, i.e. all integers $<n/4$ with $\binom{i}{q}=\binom{i}{p}=1$. Therefore, counting the number of consecutive pairs of $0$s in the binary representation of $q^*_n(2)$ is sufficient. We denote this with $C(q_n^*(2), [0, 0])$. However, we must prepend leading zeros to the binary representation of $q_n^*(2)$ so that its length is exactly $\varphi(n)$. 

\begin{equation} 2C(q^*_n(2),[0,0])- 4h(-p)- 2\left(\left\lfloor \frac{n}{4} \right\rfloor - \left\lfloor \frac{q}{4} \right\rfloor - \left\lfloor \frac{p}{4} \right\rfloor\right) = h(-n) \end{equation}

4. Class number h(-q). Here we do a little trick. We multiply $q^*_n(2)$ by $p$ and then compute its Hamming weight:

\begin{align} &\frac{q-1}{2} - 2\left(\frac{2}{p-1}\frac{\text{HW}(p\cdot q^*_n(2))}{4}\right)
= \frac{q-1}{2} - \frac{\text{HW}(p\cdot q^*_n(2))}{p-1}
= h(-q)
\end{align}

Note: For all information above ($\varphi(n), h(-p), h(-q), h(-n))$ that we got from $q^*_n(2)$ there exist no efficient algorithm if $n$ is large (except in special cases).

Example