0
\$\begingroup\$

Background

You are probably familiar with the "asymptotic time complexity" concept, which provides a way to measure how fast an algorithm runs as the input gets larger. For instance, if an algorithm needs \$2n+3\$ steps to compute the answer for input of (binary) length \$n\$, we say it is of complexity \$O(n)\$. In case you are not familiar with it, here are some links to refresh your memory.

You are probably also familiar with the prime factorization problem, where you need to decompose some given integer \$N\$ into the product of prime numbers \$p_1p_2p_3\dots\$ . For the sake of simplicity, we will only consider integers composed of two primes (\$N = p q\$), where the two primes are approximate in size (i.e. around \$\sqrt N\$). We measure the time complexity of a prime factorization algorithm by the number of arithmetic operations, as a function of the bit-length \$n\$ of \$N\$. For instance, the naive trial division algorithm tries to divide \$N\$ with every number from 2 to the \$\sqrt N\$, which is about \$2^{\frac n2}\$ numbers. So we say the complexity of the algorithm is \$O(2^{\frac n2})\$, which grows exponentially as \$n\$ gets bigger.

It would be very convenient (and devastating!) if we can find an algorithm that runs in time \$O(n^k)\$, where \$k\$ is some fixed number. But we haven't found any, and the current state-of-the-art algorithm runs in sub-exponential time (i.e. slightly faster than exponential). (By the way, Shor's algorithm, which runs on quantum computers, runs in \$O(n^3)\$, but we are not concerned with quantum computers here.)

Task

This is a very, very ambitious task. Your challenge, should you accept it, is to write a working prime factorization program/function/etc. that runs in polynomial complexity (i.e. \$O(n^k)\$ for some \$k\$) if mathematically possible, and runs in exponential complexity if not, with unlimited memory.

Your input is a positive integer N in binary, that is guaranteed to be equal to the product of two primes with similar size. It can be input in any way you would like. Your output is the two factors p and q, such that p,q > 1 and pq == N. You should explain, if not evident, why your algorithm runs in the required time complexity.

To be more precise on the complexity class, let \$p_n,q_n = O(2^{\frac n2})\$ be prime number sequences. And \$N_n = p_nq_n = O(2^n)\$. The program should run in the required time complexity when \$N_n\$ is fed into the input.

To clarify: it is not mathematically proven whether there are algorithms that runs in \$O(n^k)\$ for some \$k\$, but it must be either true or false. If it turns out to be true, your algorithm should run in polynomial complexity (\$O(n^m)\$ for some constant \$m\$, it may or may not be the optimal one). And if it turns out to be false, your algorithm should at least run as fast as the naive algorithm. (Note that the big-O notation is downward compatible. So if you run faster than required it is OK.) As an extreme case, if you proved that there is no prime factorization algorithm in polynomial time, you can just go ahead and implement a naive algorithm. But if so, you need to accompany your program with a proof that polynomial algorithms are not possible.

If you are still bewildered, here is a hint on a possible way of attack.

Hint: you can look at Gödel's machine, but there are other, easier ways out there! In short, a Gödel machine implements a program that checks whether a proof is correct. It constantly searches for algorithms that can replace part or all of its code. And if the code is proved correct (by proof searching) and faster, it replaces the original code. Since it takes a fixed amount of time to obtain the best algorithm (and to prove stuff), for large tasks, the optimal algorithm will be used eventually, and thus making the whole program optimal (asymptotically, and with an unimaginable large (but constant) overhead).

(You are not recommended to read this unless you get stuck) A related codegolf challenge. This may or may not contain what you need. The only solution to that challenge does the work in some ad-hoc way.

This is , so the answer with the smallest byte count wins. Standard loopholes apply.

Additional bonuses and clarification

Your byte count is multiplied by

  • 0.9 if your program can handle arbitrary positive integers, instead of those of the form \$N = pq\$.
  • 0.8 if your algorithm is essentially different from the one described in the first hint.
  • 0.01 if you can point out the actual time complexity your algorithm runs in!

Your language, especially golfing languages, may not completely support basic arithmetic operations (e.g. addition, subtraction, multiplication, division, remainder, exponentiation, bitwise operation on fixed size numbers, so bignum operations should be broken up to the basic ones). In that case, the equivalent combination of operations can count as one step when computing the time complexity. (The actual counting method shouldn't affect the asymptotic complexity.)

Example cases

Input: 1111      # 15 in binary format
Output: 11, 101  # 15 = 3 x 5
Output: 3, 5     # output in decimal format is permitted

Input: 1000...00001      # with 31 zeros, i.e. 2^32 + 1
Output: [641, 6700417]   # you can tweak the output a little, if it shortens your code

Input: 1111101001    # 1001 in binary format
Output: {7, 11, 13}  # bonus if you can handle this case
\$\endgroup\$
  • 1
    \$\begingroup\$ @SurculoseSputum The restrictions and scoring criteria are different. But yes, the task is identical. \$\endgroup\$ – Trebor Jun 21 at 4:00
  • 2
    \$\begingroup\$ @SurculoseSputum This challenge poses asymptotic restrictions, in which constant factor improvements are not relevant. The linked challenge almost exclusively depends on constant factor improvements. \$\endgroup\$ – Trebor Jun 21 at 4:08
  • 1
    \$\begingroup\$ I think that this is basically the same as the subset sub problem, you liked in the spoiler. It is mostly the same set-up with a slight tweak to the task. So I am going to vtc as duplicate of that. However I agree with you that it is not a duplicate of fastest semiprime factorization, and I think it is an good challenge. I hope to see more challenges from you in the future. \$\endgroup\$ – Wheat Wizard Jun 21 at 4:23
  • 4
    \$\begingroup\$ I will say for future challenges, I am not a fan of bonuses as are many members here. They are on our list of things to avoid. \$\endgroup\$ – Wheat Wizard Jun 21 at 4:27
  • 1
    \$\begingroup\$ If I can take unlimited memory, can I take unlimited number of processors as well? \$\endgroup\$ – Abigail Jun 21 at 9:16