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 code-golf, 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
