What if $\sigma_0(n)$ could be computed efficiently? (Part 2)

In the first post regarding this topic, i sketched why an algorithm that counts the number of prime factors of an integer could lead to an algorithm that actually could factorize that integer. The application of such an algorithm to different number fields would lead to non-trivial information about the prime factors due to the definition of prime numbers in $\mathbb{Q}(\sqrt{d})$. The hope is, that this information would eventually allow us to reconstruct the entire prime numbers.

In this post i will show some basic facts about different number field and what information they leak about prime factors of $n$ if $\sigma_0(n)$ is known.



We begin with two common facts about quadratic fields:

Theorem. Every quadratic field is of the form $\mathbb{Q}(\sqrt{d})$, where $d$ is a square-free rational integer not equal to $1$. The ring of integer of a quadratic field $\mathbb{Q}(\sqrt{d})$ is of the form $\mathbb{Z}[\omega]$, where $\omega$ is given by $\omega =  \frac{1+\sqrt{d}}{2}$, if $d \equiv 1\pmod{4}$ $\omega =  \sqrt{d}$, if $d \equiv 2\pmod{4}$ or $d \equiv 3\pmod{4}$

Theorem [Discriminant and Norm]. The discriminant $D$ of a quadratic field $\mathbb{Q}(\sqrt{d})$ is given by $D = d$ if $d\equiv 1\pmod{4}$ $D = 4d$ if $d\equiv 2\pmod{4}$ or $d\equiv 3\pmod{4}$  The norm of an element $\zeta = a+b\omega \in \mathbb{Z}[\omega]$ is $N(\zeta) = \left| a^2+ab-\frac{d-1}{4}b^2 \right|$ if $d \equiv 1\pmod{4}$ $N(\zeta) = \left| a^2-db^2 \right|$ if $d \equiv 2\pmod{4}$ or $d \equiv 3\pmod{4}$

The next Theorem gives the complete characterisation of primes in quadratic fields / rings:

Theorem [Primes characterisation [1]]  Let $\mathbb{Q}(\sqrt{d})$ have the unique factorization property and $D$ the discriminant of the quadratic field, then If the natural prime $p$ is a product $\pi_1\pi_2$ of primes of $\mathbb{Q}(\sqrt{d})$, then $N(\pi_1) = N(\pi_2) = p$. Otherwise, $p$ is a prime $\pi$ of $\mathbb{Q}(\sqrt{d})$ and $N(\pi) = p^2$. Any odd natural prime $p$ not divisor of $D$ (or $d$) is a product $\pi_1\pi_2$ of primes $\mathbb{Q}(\sqrt{d})$ if $D$ (or $d$) is a quadratic residue modulo $p$. Otherwise, it is itself a prime $\pi$ of $\mathbb{Q}(\sqrt{d})$. If $2$ is not a divisor of $D$, which implies $D$ is odd, hence $d \equiv 1\pmod{4}$ then $2$ is a product $\pi_1\pi_2$ of primes of $\mathbb{Q}(\sqrt{d})$ is $d \equiv 1\pmod{8}$. Otherwise, $d \equiv 5\pmod{8}$ and $2$ is a prime of $\mathbb{Q}(\sqrt{d})$. Any (odd or even) natural prime $p$ which is a divisor of $D$, is equal to a product $\pi_1\pi_2$ of primes of $\mathbb{Q}(\sqrt{d})$. Only in this the prime factors $\pi_1$ AND $\pi_2$ are associates.

For the next Theorem, we need the $\chi_d(x)$ character.

• If $x = p$ is an odd natural prime and $p \nmid p$, then $\chi_d(p) = \binom{d}{p}$, whereof $\binom{d}{p}$ is the usual Legendre symbol
• If $x=2$ is not a divisor of $D$, hence, $d \equiv 1\pmod{4}$, then $\chi_d(2) = 1$ if $d \equiv 1\pmod{8}$ and $\chi_d(2) = -1$ if $d\equiv 5\pmod{8}$
• If $x = p^2$ and $p$ is a natural prime not divisor of $D$, then $\chi_d(p^2) = 1$.

And the reformulation due to [2] is:

Theorem Let $\mathbb{Q}(\sqrt{d})$ have the unique factorization property and $D$ the discriminant of the quadratic field, then the prime of this field are those numbers $\pi$ whose norm $N(\pi) =n$ has one of the following properties: $n$ is a prime divisor of $D$. In this case $n$ is the product of two associated primes of the field $n = p$ and $p$ is a natural prime that does not divide $D$, such that $\chi_d(p) = 1$. In this case $p$ is the product of two non-associated primes of $\mathbb{Q}(\sqrt{d})$ $n = p^2$ is the square of a prime $p$ not a divisor of $D$ such that $\chi_d(p) = -1$. In this case $p$ is itself a prime of $\mathbb{Q}(\sqrt{d})$

# Examples #

We neglect divisors of $D$.
1. $d=-1$, $\mathbb{Z}[\omega=\sqrt{-1}]$. Discriminant $D = -4$. Then we have the primes:

• $\zeta = (p+b\omega) \in \mathbb{Z}[\omega]$ and $b=0$, $p \in \mathbb{P}$ and $p \equiv 3\pmod{4}$.
  Proof: then $N(\zeta) = p^2$. If $p \equiv 3\pmod{4}$, then $\chi_{-1}(p) = \binom{-1}{p} = -1$.
• $\zeta = (a+p\omega) \in \mathbb{Z}[\omega]$ and $a=0$, $p \in \mathbb{P}$ and $b \equiv 3\pmod{4}$.
  Proof: analog
• $\zeta = (a+b\omega) \in \mathbb{Z}[\omega]$ and $\left|a^2+b^2\right| = a^2+b^2 = p \in\mathbb{P}$ and $p\equiv 1\pmod{4}$.
  Proof: It is $N(\zeta) = a^2-db^2 = a^2+b^2 = p$. Only primes of the form $p \equiv 1\pmod{4}$ can be written as the sum of two squares.

2. $d=3$, $\mathbb{Z}[\omega=\sqrt{3}]$. Discriminant $D = 12$. Then we have the primes:

• $\zeta = (p+b\omega) \in \mathbb{Z}[\omega]$ and $b=0$, $p \in \mathbb{P}$ and $p \equiv  \{5,7\} \pmod{3}$
  Proof: It is $N(\zeta) = p^2$. $\chi_3(p) = \binom{3}{p} = \binom{p}{3}(-1)^{(p-1)/2}$, hence $p \equiv \{5,7\}\pmod{12}$ to make $\chi_3(p) = -1$.
• $\zeta = (0+p\omega) \in \mathbb{Z}[\omega]$ and $a=0$, $p \in \mathbb{P}$ and $p \equiv \{5,7\}\pmod{12}$  to make $\chi_3(p) = -1$.
  Proof: analog
• $\zeta = (a+b\omega) \in \mathbb{Z}[\omega]$ and $N(a+b\omega) = \left|a^2-3b^2\right| = p \in\mathbb{P}$, hence $p\equiv \{1,11\}\pmod{3}$.
  Proof:  $\chi_3(p) = 1 = \binom{3}{p} = \binom{p}{3}(-1)^{(p-1)/2}$, hence $p \equiv \{1,11\}\pmod{12}$ to make $\chi_3(p) = -1$.

3. $d=7$, $\mathbb{Z}[\omega=\sqrt{7}]$. Discriminant $D = 28$. Then we have the primes:

• $\zeta = (p+b\omega) \in \mathbb{Z}[\omega]$ and $b=0$, $p \in \mathbb{P}$ and $p \equiv  \{5,11,13,15,17,23\} \pmod{28}$
  Proof: It is $N(\zeta) = p^2$. $\chi_7(p) = \binom{7}{p} = \binom{p}{7}(-1)^{(p-1)/2\cdot 3} = \binom{p}{7}(-1)^{(p-1)/2}$, hence $p \equiv \{5,11,13,15,17,23\} \pmod{28}$ to make $\chi_7(p) = -1$.
• $\zeta = (0+p\omega) \in \mathbb{Z}[\omega]$ and $a=0$, $p \in \mathbb{P}$ and $p \equiv \{5,11,13,15,17,23\} \pmod{28}$
  Proof: analog
• $\zeta = (a+b\omega) \in \mathbb{Z}[\omega]$ and $N(a+b\omega) = \left|a^2-7b^2\right| = p \in\mathbb{P}$, hence $p\equiv \{1,3,9,19,25,27\} \pmod{28}$.
  Proof:  $\chi_7(p) = 1$ if  $\chi_7(p) = \binom{7}{p} = \binom{p}{7}(-1)^{(p-1)/2\cdot 3} = \binom{p}{7}(-1)^{(p-1)/2}$, hence $p \equiv \{1,3,9,19,25,27\} \pmod{28}$ to make $\chi_7(p) = 1$.

Note that there are only $8$ different euclidean number fields with $d\equiv 2\pmod{4}$ or $d\equiv 3\pmod{4}$, these are

1. $d \equiv 2\pmod{4}$: $d = -2, 2, 6$
2. $d \equiv 3\pmod{4}$: $d = -1, 3, 7, 11, 19$

# Factoring N=PQ #

Let $\mathcal{A}(d,N)$ be the algorithm that on input $N$ counts the factors in $\mathbb{Z}[\sqrt{d}]$.
Let $N = PQ$ and $\mathcal{A}(-1,N) = 3$, i.e., $N = PQ = \pi_1\pi_2\pi_3$. So one of the natural prime number $P$ and $Q$ must also be a prime in $\mathbb{Z}[\sqrt{-1}]$ and it hence must be of the form $3+4\mathbb{Z}$. The other one is, w.l.o.g., equal to $p_2p_3 = (a+b\omega)(a-b\omega) = a^2+b^2$ and hence must be of the form $1+4\mathbb{Z}$. Likewise, we can use the information $\mathcal{A}(3,N)$ and $\mathcal{A}(7,N)$ in a similar way.

Problem 1. How to combine these results without the need to test all possible combinations? Sure, one would use the chinese remainder theorem, but is the prime which is congruent to $r_{4,1}$ modulo $4$ congruent to $r_{3,1}$ or $r_{3,2}$?

Problem 2. For a ring with larger $d$, i.e., $\mathbb{Z}[\sqrt{7}]$ one gets several possible residues, i.e., $\{1,3,9,19,25,27\}$ or $\{5,11,13,15,17,23\}$ as shown in the example. One could combine this information with $\mathbb{Z}[\sqrt{-1}]$, which reduces the solution modulo $7$ to three. But in general, the number of solution increases as $d$ increases. How can one reduce the number of possible solutions that arise?

Example: $N = PQ =  29\cdot 43 = 1247$ and we want to determine $P$ and $Q$. It is $\mathcal{A}(-1,1247) = 3$. Hence either prime $P$ is $1+4\mathbb{Z}$ and $Q$ is $3+4\mathbb{Z}$ or vice versa. Actually, this is no new information since $N \pmod{4} \equiv 3$ tells us the same. Only the case $\mathcal{A}(-1,1247) \in \{2,4\}$ would have telt us new information.
Next $\mathcal{A}(7,1247) = 3$. Hence one prime is equal to $\{1,3,9,19,25,27\}$ modulo $28$ and the other $\{5,11,13,15,17,23\}$. Which actually is not new at all.
Next $\mathcal{A}(3,1247) = 2$. Hence both factor $P$ and $Q$ are congruent to either $5$ or $7$ modulo $12$.
Lets combine the results so far: W.l.o.g.

$P \equiv \{1,3,9,19,25,27\}\pmod{28}$ and $\{5,7\} \pmod{12}$, hence $\{29,59,65,19,25,55\}\pmod{84}$

$Q \equiv \{5,11,13,15,17,23\}\pmod{28}$ and $\{5,7\} \pmod{12}$, hence $\{5,11,41,43,73,79\}\pmod{84}$

So we successfully determined the prime factors $29$ and $43$ since they are part of the final sets.

We get the useful information of $P$ and $Q$ modulo $4$. And from the other number fields $\mathbb{Q}(\sqrt{d})$ we get around $(d-1)/2$ possible values for $P$ and $Q$ each.
But this reduced size of information we get already for another equally important number, i.e., $P+Q$, via a different and more or less trivial approach:

$PQ = N$ and $P+Q = S$, then $$P^2 + N = PS \Leftrightarrow P^2 - PS + N \equiv 0\pmod{d}$$.
Only for around $(d-1)/2$ values for $S$, this quadratic congruence has a solution.  For example in the case $N = 1247$ it is $S \equiv \{1,2,5,6\} \pmod{7}$. But for large integers, this reduction is not sufficient enough.

# Amplification #

Suppose $N=PQ$ for odd primes $P$ and $Q$. The number of prime factors of $N$ in $\mathbb{Q}[\sqrt{-1}]$ give non-trivial information whenever the answer is, that $N$ has either $2$ or $4$ prime factors in $\mathbb{Z}[\sqrt{-1}]$. For $3$ factors, one gets the same information as from $N\pmod{4}$. It is often the case in cryptography, that already a single bit of non-trivial information about a secret can be amplified to gain more information or often to break to whole cryptosystem. 

Is this case similar, i.e., is it possible to amplify this information to completely factor the integer $N$?

[1] S.I.Borewicz and I.R. Safarevic, Zahlentheorie, Birkhäuser Verlag Basel
[2] Prime numbers in quadratic fields. Published in, CWI Quarterly, Vol. 7, No. 4, p.367-394. ISSN 09225366. Author, T.J. Dekker. Date, 1994.