"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

Proof: Otherwise you could break X

⬛ Some of you may be familiar with this situation. From time to time you find yourself thinking about a new approach to a problem that you know is difficult. And although you know that you should
probably be doing something more productive, you try new ideas to tackle the problems.

And every now and then you stumble across a more or less basic fact that prevents your idea from working. I will try to give some examples that may surprise you. I will focus on the three main problems: discrete logarithm problem, factorization problem and the class number computation problem.

Often the examples come from situations that similar to:

    Alice: "I have a great idea. What if you could find some object O that has property P and Q."

    Bob: "Perfect, O is well known and P and Q seem not that restrictive."

A few days later.

    Alice: "I can not find such an object. All objects either have P or Q but not both."

    Bob: "Yeah, you are right, probably there is some theorem that we don't know."

There are probably many more examples or better ones. But at least all of the three examples below crossed my road during the last years.

Methods to compute the class number

The class number is an important term from algebraic number theory. It specifies the order of the class group of an algebraic number field $K$ and can be interpreted as the number of different ways to factorize an element of $K$ into prime elements. If the class number is equal to $1$, the $K$ is called a unique factorization domain, e.g. the integers $\mathbb{Z}$. It is long known that for imaginary quadratic fields the class number is $1$ only for the values: $$K = \mathbf{Q}(\sqrt{d}), d \in \{-1,-2,-3,-7,-11,-19,-43,-67,-163\}$$ There are a surprisingly large number of ways to compute the class number of a quadratic field, which i want to show you next.