0
$\begingroup$

This is not necessarily a direct physics question, but I am hoping, that by posting it here, someone can give a hint from the physics perspective.

It is known, albeit not proven, that integer factorization is hard. My point of view of this is the following analogy to physics:

One-Way-functions correspond in physics to the "Arrow of time".

It is not (provenly) known if owf exist, but integer factorization is a candidate for this. ($n=pq$ is the prime decomposition of $n$, given $n$, find $p$ or $q$.)

Since in physics the "Arrow of time" increases entropy, this means that owf should also increase entropy.

Here is an example of what I mean:

Randomly choose some "regular" prime, with low bits-Shanon-entropy, $p \ge 2^N$, where $N$ is a very large number and $p$ is the smallest such prime. Similarly choose another prime $q \ge 2 ^ M$.

(So to be more clear: Randomly choose uniformly some large numbers $N,M$ and then proceed as above).

Edit: The Shannon entropy of a number $k$ in binary digits is defined as $$ H = -\log(\frac{a}{l})*\frac{a}{l} - \log(1-\frac{a}{l})*(1-\frac{a}{l})$$ where $l = \text{ floor }(\frac{\log(k)}{\log(2)})$ is the number of binary digits of $k$ and $a$ is the number of $1$-s in the binary expansion of $k$. So we view the number $k$ as a "random variable".

Let $n=pq$. Then my conjecture is that the binary digits of $n$ will have a very high Shannon-entropy compared to $p$ and $q$ (on average).

(On the other hand $p+q$ will not increase the entropy (on average).)

Here is a concrete example in SAGEMATH:

p = next_prime(2^randint(600,700))
q = next_prime(2^randint(600,700))

n = p*q

What I mean by "regular" is that $p$ and $q$ will have many zeros but very few ones and viewed as random variables will have a low entropy.

On the other hand compared to the entropy of $p,q$ the number $n$ has a high entropy.

My explanation for this is, that multiplication raises the entropy of the system $p,q$.

Now the physics question. Suppose I have a box with two container each having some particles $N$ and $M$ in size. The entropy of the left and right container are very low. Now I open the box so that the two container (which would correspond to the primes $p$ and $q$) can interact (multiplication $n=pq$). The entropy of this closed system should increase with time, as happens with the entropy of $n$.

My vague question is this: How much work does one in average have to do, to separate the particles back to their containers (integer factorization) so that the entropy of the left and right box, equals the entropies we started with?

This question could perhaps lead to insights why integer factorization is hard.

Thanks for your help.

Second Edit suggested by comment of @AndrewSteane: The relevant physics experiment as suggested by @AndrewSteane is:

1) increase in entropy corresponds to multiplication:

"If a volume $V$ of gas freely expands into a volume $2V$ (e.g. into a vacuum) then the entropy goes up. So if there are gases $A$ and $B$ both freely expanding into each other, so that each one's volume changes from $V$ to $2V$ then the entropy goes up."

2) entropy stays the same (corresponds to addition): " If volume $V$ of gas $A$ is slowly merged with volume $V$ of gas $B$ without increasing the total volume, then there is no entropy increase; the process can be done in a thermodynamicaly reversible way"

Suppose we define the "volume" of a number $k$ to be $|k|$ = number of bits of $k$. Then if $|p|\approx|q|$ the number $n=pq$ will have $|n|\approx 2|p|$, so the volume doubles. If $m=p+q \approx 2p$ then the volume $|m| \approx \text{ floor} (\frac{\log(2p)}{\log(2)}) = \log(p) \approx |p|$ will roughly stay the same $|m| \approx |p|$. This would explain why addition does not increase entropy but multiplication does.

Third edit by suggestion of @probably_someone:

N  = 10^4

def entropyOfCounter(c):
    S = 0
    for k in c.keys():
        S += c[k]
    prob = []
    for k in c.keys():
        prob.append(c[k]/S)
    H = -sum([ p*log(p,2) for p in prob]).N()
    return H

def HH(l):
    return entropyOfCounter(Counter(l))

N  = 10^4
HN = []
HmXn = []
HmPn = []
for k in range(N):
    n = randint(1,17^50)
    m = randint(1,17^50)
    Hn = HH(Integer(n).digits(2))
    Hm = HH(Integer(m).digits(2))
    HmXn.append(HH(Integer(n*m).digits(2)))
    HmPn.append(HH(Integer(n+m).digits(2)))
    HN.append(Hn)

X = mean(HN)
Y = mean(HmPn)
Z = mean(HmXn)
n = len(HN)
m = n
SX2 = variance(HN)
SY2 = variance(HmPn)
SZ2 = variance(HmXn)
SXY2 = ((n-1)*SX2 + (m-1)*SY2)/(n+m-2)
SXZ2 = ((n-1)*SX2 + (m-1)*SZ2)/(n+m-2)
TXY = sqrt((m*n)/(n+m)).N()*(X-Y)/sqrt(SXY2).N()
TXZ = sqrt((m*n)/(n+m)).N()*(X-Z)/sqrt(SXZ2).N()
print TXY,TXZ,n+m-2

Output: -1.43265218355297 -32.5323306851490 19998

The second case (multiplication) increases entropy significantly. The first case ( addition) does not.

$\endgroup$
  • $\begingroup$ How are you defining the Shannon entropy of a single number? Usually the Shannon entropy is defined for a probability distribution. $\endgroup$ – probably_someone Jun 24 at 6:32
  • $\begingroup$ @probably_someone: I edited the question, to clarify what I mean. $\endgroup$ – orgesleka Jun 24 at 6:42
  • $\begingroup$ Ok then, here's a counterexample to your conjecture: $2\times 2=4$, or in binary, $10\times 10=100$. Clearly $100$ has lower entropy than $10$ (which has maximal entropy). $\endgroup$ – probably_someone Jun 24 at 6:53
  • $\begingroup$ @probably_someone: How did you choose $p=q=2$? I don't think this is a counterexample: Choose very large numbers $N,M$. Let $p \ge 2^N,q\ge 2^M$ be the smallest primes. Then $p,q$ will have many 0 compared to 1 ( although I can not prove this, since it requires the existence of primes $p$ which are close to $2^N$). But $n=pq$ will increase the entropy (this is just a conjecture, I have no proof for this.). Of course it is easy to find primes $p$ and $q$ such that $n=pq$ has lower entropy, but randomly constructing the primes as I am suggesting, I think it is difficult find counterexamples. $\endgroup$ – orgesleka Jun 24 at 7:05
  • $\begingroup$ I think you need to understand the entropy of mixing better. If volume $V$ of gas A is slowly merged with volume $V$ of gas B without increasing the total volume, then there is no entropy increase; the process can be done in a thermodynamicaly reversible way. $\endgroup$ – Andrew Steane Jun 24 at 8:16
2
$\begingroup$

Just an order of magnitude estimation.

Let $p$ and $q$ be primes of the form that you propose, and write $p = 2^N + p'$, $q = 2^M + q'$. Then $n = 2^{N + M} + p'2^M + q'2^N + p'q'$.

By the prime number theorem, the size of $p'$ is around $N\ln 2$, $\log_2 N$ binary digits, and that of $q'$ is around $\log_2 M$ binary digits.

Think about how the binary expansion of $n$ looks: it will start with a 1, followed by many 0's, somewhere about the $N$'th position and around the $M$'th position a small nonzero sequence of digits of length $\log_2 N$ and $\log_2 M$, possibly partly overlapping if $N\approx M$, and again for the last $\log_2(N + M)$ binary digits.

There is no reason to assume that $p'$, $q'$ and $p'q'$ have low entropy, so we could expect them to have approximately equal numbers of ones and zeros.

Let $\alpha$ be the fraction of 1's in a number (i.e. the "probability" that a random digit is a 1), and assume that $\alpha \ll 1$. Then the entropy of the binary expansion of the number, if we treat each digit as an independent random event, is

$$H = -\alpha\log\alpha - (1 - \alpha)\log(1 - \alpha) \approx -\alpha(\log(\alpha) - 1).$$

Let's assume that $M\sim N$, just to make the expressions less cumbersome. Then the probability $\alpha\approx \frac{\log_2N}{2N}$ for both. The probability of a 1 for $n = pq$ then is $2\alpha$, and we immediately see by how much the entropy can be expected to go up.

For example, for $N,M \in \{600,\ldots,700\}$, $\alpha\approx0.0072$, so

$$H(p)\approx H(q) \approx 0.062$$

while

$$H(n) \approx 0.109$$

For the sum of the primes, we get (again assuming $M\sim N$) that $p + q\approx 2p$, which has $N+1$ digits, and $p' + q'\approx 2p'$, which has $\log_2(N+1)$ binary digits, so that, since we don't expect $p' + q'$ to have low entropy for any reason, $\alpha$ doesn't really change at all.

EDIT Entropy was computed in base $e$, changed to bits (base 2).

As remarked by @probably_someone, convergence is somewhat slow. To get a better approximation, one can take into account that the number always start and end with a 1, and be explicit about the difference between $N$ and $M$ to estimate the number of ones in $n$.

$\endgroup$
  • $\begingroup$ @probably_someone $p'$ is of the order $N$, not $2^{N-1}$. If $N$ is not large, the number of zeros obviously is not large either. $\endgroup$ – doetoe Jun 24 at 19:12
  • $\begingroup$ @probably_someone Also, neither 559231 nor 590207 is the first prime after a power of 2 $\endgroup$ – doetoe Jun 24 at 19:13
  • $\begingroup$ @probably_someone I think I understand your confusion now (I thought the same too when I first read the question): the statement that the entropy of a product tends to be larger than that of the factors is obviously false, but the OP deliberately starts out with low-entropy primes. This is what I assumed too: $p$ and $q$ are the first primes after $2^N$ and $2^M$ $\endgroup$ – doetoe Jun 24 at 19:16
  • $\begingroup$ Even with that restriction, the statement doesn't really appear to hold. A script that tries pairs of first primes after powers of two for every power of two from $2^{20}$ to $2^{100}$ found that, of 3,240 cases, only 2,218 had the product have a higher entropy than either of the factors. That's a lot closer to half-and-half than I would expect if the estimate in your answer worked. $\endgroup$ – probably_someone Jun 24 at 19:37
  • $\begingroup$ @probably_someone That certainly would be... I'll try to do the same as you did later tonight, to see what is going wrong $\endgroup$ – doetoe Jun 24 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.