"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

Ed Scheidts Mayan Symbols

 ▉ In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue.

▉ Mayan Symbols ▉

I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols:

Figure 1 - Garage driveway of Ed Scheidt

We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can use Maps (iOS) to see their positions (See Figure 2):

Figure 2 - Birds view of the driveway with marked positions of the two symbols

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.

Kryptos - The Cipher (Part 5)

ONE of the most surprising facts about Kryptos is that no one has yet discovered the expected way to find the keywords for K1 and K2. And perhaps this missing fact is the key to why we are stuck with K4. I don't think Sanborn wanted us to bruteforce the solutions (as we did), but somehow left a clue that we haven't seen yet.

Most people believe, that the morse code messages around Kryptos should somehow encode at least the first codeword for K1 (= Palimpsest). That's why the Morse code message are often called K0.

The Morse code messages are part of two pieces of granite with contained copper plates. I found two very interesting drawings of these two installations by Monet Friedrich on [1]:

RSA as Hidden Subgroup Problem

▍The Hidden Subgroup Problem is an important problem from Computer Science / Mathematics and actually covers several well known problems as a special case. The formal statement of the problem is:

Definition [Hidden Subgroup Problem (HSP)] Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of $\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$ be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f: \mathbb{G} \rightarrow S$. The function $S$ has the special property that it can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$ ∎ 

The notation $e\mathbb{H}$ denotes the coset $$e\mathbb{H} = \left\{eh | h \in \mathbb{H}\right\}$$. Problems that can be described as an instance of the HSP are for example:

1. Integer Factorization Problem
2. Discrete Logarithm Problem
3. Shortest Vector Problem
4. Deutsch Problem
5. Simon's Problem

and probably many more. The definition of the HSP above seems very abstract, but the subgroup $\mathbb{H}$ actually covers the usual integers of interest, e.g. divisors of $\varphi(N)$ in case of the Factorization Problem or multiples of the exponents in question in case of the Discrete Logarithm Problem. Shors Algorithm is a special instance of an HSP-Solver that finds the period of the function $g^x \pmod{N}$, i.e., it finds divisors of $\varphi(N)$. However, his algorithm only works in the ablian case. How to solve the HSP efficiently for non abelian groups is not known, also for quantum computers. The Shortest Vector Problem is a hard problem for quantum computers. So it is no surprise, that the reduction from SVP to HSP brings into play a non abelian group, the dihidral group.