NumberWorld

Posts

Showing posts with the label Prime numbers

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.

The l-Hensel Lifting Assumption

In one of my previous posts , i talked about the possibilities to insert backdoors in prime numbers (beside the property that $p-1$ is smooth). One of the potential ideas for a backdoor was to generate primes that allow an easy lift from $\mathbb{Z}/p$ to $\mathbb{Z}/{p^2}\mathbb{Z}$. But under the consideration of the $l$-Hensel Discrete Logarithm Assumption , this should be actually hard in the general case. Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute \begin{align*} \left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2} \end{align*} Next, the Binomial Theorem gives \begin{align*} (1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2} \end{align*} and hence \begin{align*} \frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p} \end{align*}

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

What would be the consequences if the sum of divisors function with $k=0$ could be computed efficiently, that is polynomial in $\log (n)$ if $n$ is the input to $\sigma_0(n)$? Note that if $n=p_1^{e_1}p_2^{e_2}...p_m^{e_m}$ then $$\sigma_0(n) = \sum_{d|n} d^0 = \sum_{d|n} 1 = (e_1+1)(e_n+1)...(e_m+1)$$ For square-free numbers $n$, this is always a power of $2$, hence $\log_2(\sigma_0(n))$ gives the number of prime factors in this case. Furthermore, the famous AKS-algorithm gives a deterministic polynomial time algorithm, that decides if $\sigma_0(n) = 2$ or not, i.e. $n$ is prime or composite. For the general case, Terence Tao gave an heuristic argument that generally this should be as hard as factoring a number: " There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty ...

Backdooring Discrete Logarithms in $\mathbb{Z}^*_p$

In one of my previous post , i talked about the (potential) backdoor in the pseudo random number generator described in SP800-90 Dual Ec PRNG. The backdoor could be exploited by the usage of some perhaps existing secret relation among two given constants. The concept of elliptic curves cryptography and its whole theory is much more complicated than the cryptography based on the finite fields $\mathbb{F}_p$ for a large prime number $p$. Implementing a backdoor in that case seems to be harder. Some people indeed say, that we should switch back to the good old fields $\mathbb{Z}^*_p$ to increase the confident in our systems.

Learning a Sine-Wave to break Cryptography

A few month ago, i locked up myself into a mental hole, by trying to solve or at least partially solve the following a problem. I named it "Learning a Sine Wave", because you can think of it, as finding the period of a sine function given some hints. Problem-Definition . Assume you have a sufficient long integer interval $I=[0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \mathsf{sign}(\sin(2x\pi/p))$. The set $Z$ contains the randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that point (i.e., the sign value). Find the secret parameter $p$. Below you find a illustration of the problem. I sine wave is drawn a seven points are marked: $10, 24, 55, 89, 122, 165, 192$. For each of those point i known the label $+1$ or $-1$. Your goal is to determine the length of one full period of the sine wave. Fig-1: Random instance for the pro...

Sum of Divisors Function - Euler's recursion

Number theory has many functions that are based on the arithmetical properties of a given input integer $n$. These functions are called number-theoretic functions . Well known examples are, e.g., the Euler's Totient Function and The Möbius Function . Since arithmetical properties often depend in one or the other way on the integer's prime factorization, these functions are usually hard to compute for large integers due to the factorization problem . One of these functions, that heavily depends on that factorization, is the Divisor Function . Definition: Divisor Function Given an integer $n$ then the divisor function $\sigma_k(n)$ is defined as $$ \sigma_k(n) := \sum_{d|n}d^k$$