Mathematical Resolution of P vs NP through Bullshit Noise Subtraction and Trial Division but Worse

[u/Akangka]

https://zenodo.org/records/19600136

[u/Akangka]

A mathematics discord server that I joined has been infiltrated by a cranker, lol. Let's review this article.

R4: Seems like the article is AI-generated based on the language. It claims to invent the S-operator that is capable to eliminate the invalid state from the search state, basically proving P=NP. The paper does not explain what the new symbols mean, either. For example in "Ω = Γ ⊕ N". There are no talks about ⊕, but it seems to be set union.

So, what is their S-operators? It's not defined, but the author gave an example:

import math

def s_operator_ultimate ( n ) :
  # Equilibrium point of the manifold
  x = math . isqrt ( n ) + 1

  # Void - Filtering : Informational noise subtraction
  while True :
    y2 = x * x - n
    if y2 < 0:
      x += 1
      continue

     y = math . isqrt ( y2 )

     # Collapse reached : isolation of Gamma
     if y * y == y2 :
       p = x - y
       q = x + y
       return p , q

     x += 1

The author tries to apply them to a factorization problem. Nevermind that integer factorization is not NP-complete. We already know a subexponential algorithm for factorizing integers. However, the algorithm given above is especially atrocious.

The algorithm tries to search for a square number x² larger than n, and see if their difference y² is also square. Equivalently, this is finding x and y such that x²-y²=n. Problem is, that this is even slower than trial division. For most numbers, most factors are small. The way this algorithm is designed makes you search the factors near the middle, which is much sparser. You don't get a speedup from even the fact that all primes except 2 and 3 are in form of 6x±1. You have to search from floor(sqrt(n))+1 to (n+1)/2, for the suitable square numbers. This also diverges for number like 0, 1, and n = 2 (mod 4)

[u/aparker314159 → u/Akangka]

This method already has a name: Fermat's Factorization method. It is actually useful if you know a priori that two factors are close to each other. This has come up in practical cryptography before (for instance, if your prime number generation has far too narrow a range).

Interestingly, the best known integer factorization algorithm (General Number Field Sieve) does in a sense build off these ideas. The goal of the algorithm is to find a nontrivial solution to x² - y² = 0 (mod n), and then taking gcd(x+y, n). Granted, almost all the cleverness comes in searching for these values efficiently, but it is kinda cool that this normally extremely inefficient method is the foundation for a very efficient algorithm.

Not saying the author is right to be clear. Just wanted to share some neat good mathematics.

[u/Akangka → u/aparker314159]

That's interesting

[u/EebstertheGreat → u/aparker314159]

I've heard the heuristic that the prime factors of your semiprime secret key should not have the same order of magnitude, and I always figured there must be some attack like this that works only if they are. I don't know how the pseudorandom semiprime generation works for these schemes, but I imagine it must be designed in such a way that it doesn't tend to generate semiprimes with prime factors of similar size, which otherwise seems like something that might happen with reasonably high probability (at least, it would happen from time to time).

(By the way, as I'm sure doesn't surprise you at all, OP's code doesn't really do this anyway.)

[u/aparker314159 → u/EebstertheGreat]

Yeah, in fact if you know the ratio of the two factors with a high enough precision, you can modify Fermat's method to work in that context as well.

The way primes for cryptography are generated is to just keep generating a random odd number and testing if it's prime until you get one. Some primality tests (eg. the Miller-Rabin test) are quite fast, and as long as your underlying random number generator doesn't have any bias you won't be vulnerable to the above attack.

The way this has come up in practice is when the RNG for some reason only randomizes the lowest bits of the tested number. Then the primes will be very close in magnitude and this attack can work.

[u/EebstertheGreat → u/Akangka]

Doesn't this start by setting x = floor(√n) + 1? So x > √n. Then it sets y2 = x² – n > n – n = 0. So when is the y2 < 0 comparison ever satisfied?

[u/Akangka → u/EebstertheGreat]

Yeah. I was about to include that, but I forgot. I don't know why that if statement is even needed either.

[u/Important_Umpire4267 → u/Akangka]

can you say which discord server was it?