"Mighty" Euler Quotients - One query to rule them all

Fermat quotients have been mentioned several times in this blog and they are fascinating peace of math. 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 $n\cdot q^*_n(2) = (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$, whereof $\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 our restriction $\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 $i <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)$. Finally we get the result:

\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

Set $n=161$. We start by questioning the oracle $\mathcal{O}$: \begin{equation}q^*_{161}(2) \leftarrow \mathcal{O}\end{equation} which turns out to be \begin{equation} q^*_{161}(2) = 33816881184689536741701824341045288095 \end{equation} The binary representation of $q^*_{161}(2)$ is

\begin{align*}
&110010111000011100100111110000000110010111\\
&000011100100111110000000110010111000011100\\
&10011111000000011001011100001110010011111
\end{align*}  

1. Factorization of $n$. The binary length of $q^*_{161}(2)$ is $125$, so we have

✔️

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

Hence $p+q = 161-132+1 = 30$, which leads to the following quadratic polynomial $161/q+q = 30 \Leftrightarrow q^2-30q+161 = 0$, which correctly solves to $q_1=7$ and $q_2=23$. Since $\binom{7}{23} = -1$, we set $p=23$ and $q=7$.

2. Class number h(-p). The Hamming weight of $q^*_n(2)$ is $60$ so we compute

✔️

\begin{equation} \frac{132}{4} - \frac{60}{2} = 33-30 = 3 = h(-23) \end{equation}

3. Class number h(-n). We count the number of pairs $(0,0)$ in $q^*_n(2)$ which is $C(q^*_n(2),[0,0]) = 48$, which allows to compute $h(-161)$:

✔️

\begin{equation} 2\cdot 48 - 4\cdot 3 - 2(40 - 1 - 5) = 96 - 12 - 68 = 16 = h(-161) \end{equation}

3. Class number h(-q). We compute $23\cdot q^*_{161}(2)$ which has the following binary representation
\begin{align*}
&100100100100100100100100100100100100100\\
&100100100100100100100100100100100100100\\
&100100100100100100100100100100100100100\\
&1001001001001
\end{align*} The Hamming Weight is $\text{HW}(23\cdot q^*_{161}(2)) = 44$, hence we get

✔️

\begin{equation} \frac{7-1}{2}-\frac{44}{23-1}  = 3 - 2 = 1 = h(-7) \end{equation}

Below you find some code for Sage, which you can use to test it yourself.

Code

# Utility: Find the next prime > p such that q ≡ r (mod m) 
# and 2 has order (q−1)/2 mod q
def next_prime_mod_order(p, r, m):
    q = next_prime(p)
    while (q % m != r) or (Mod(2, q).multiplicative_order() != (q-1)/2):
        q = next_prime(q)
    return q

# Oracle function as defined in the problem
def ORACLE(n):
    return Integer((2^euler_phi(n) - 1) / n)

# Step 0: Setup
B1 = 6 # Start value for p
B2 = 20 # Start value for q

# Choose n = pq, both primes with p,q ≡ 7 mod 8 
# and is 2 of order (p−1)/2 and (q-1)/2 respectively
p = next_prime_mod_order(B1, 7, 8)
q = next_prime_mod_order(B2, 7, 8)

if (p == q):
    print(f"Error: p = q");
    exit(-1);
n = p * q

print(f"Starting integer:\nn = {n}")

# Step 0: Ask the oracle
EQ = ORACLE(n)

# Step 1: Recover φ(n) from EQ
phi = floor(log(EQ, 2)) + floor(log(n, 2)) + 1
print(f"φ(n) = {phi}")

# Solve system: x*y = n and x + y = n - φ(n) + 1
var('x y')
solutions = solve([x*y == n, x + y == n - phi + 1], x, y)
p_sol = solutions[0][0].rhs()
q_sol = solutions[0][1].rhs()

# Correct the ordering using the Legendre symbol
if legendre_symbol(q_sol, p_sol) == 1:
    p_sol, q_sol = q_sol, p_sol

print(f"Recovered primes:\np = {p_sol}, q = {q_sol}")

# Step 2: Compute class number h(-p)
hw = EQ.popcount() 
print(f"Hamming weight of EQ: {hw}")
h_p = phi / 4 - hw / 2
print(f"h(-{p_sol}) = {h_p}")

# Step 3: Compute class number h(-n)
# Pad binary digits of EQ to length φ
binary_digits = EQ.digits(2)
binary_digits = [0] * (phi - len(binary_digits)) + binary_digits

# Count number of 00-pairs (with wraparound)
C = sum(1 for i in range(len(binary_digits)) 
        if binary_digits[i % len(binary_digits)] == 0 and
           binary_digits[(i + 1) % len(binary_digits)] == 0)
print(f"Number of 00 pairs in EQ: {C}")

h_n = 2 * C - 4 * h_p - 2 * (floor(n/4) - floor(p_sol/4) - floor(q_sol/4))
print(f"h(-{n}) = {h_n}")

# Step 4: Compute class number h(-q)
hw = Integer(p_sol*EQ).popcount()
print(f"Hamming weight of p*EQ = {hw}")
h_q = (q_sol-1)/2-hw/(p_sol-1)
print(f"h(-{q_sol}) = {h_q}")

####### Verification #######
print(f"\nVerification with Sage build-in functions")
K = QuadraticField(-p_sol, 'x')
hp = K.class_number();
K = QuadraticField(-q_sol, 'x')
hq = K.class_number();
K = QuadraticField(-n, 'x')
hn = K.class_number();
print(f"h(-{p_sol}) = {hp}")
print(f"h(-{q_sol}) = {hq}")
print(f"h(-{n}) = {hn}")