Worst case of Integer factorization

Question

From Fundamental theorem of arithmetic, every integer greater than 1 either is prime itself or is the product of prime numbers, and that this product is unique, up to the order of the factors.

$$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_r^{e_r}$$

Inorder to factorize, the worst case is if the composite number is a product of two large primes. (general statement)

In RSA key generation, it is stated as follows

For security purposes, the integers p and q should be chosen at random, and should be similar in magnitude but 'differ in length by a few digits'to make factoring harder.

In Paillier key generation, it is stated as follows

Choose two large prime numbers p and q randomly and independently of each other such that $\gcd(pq,(p-1)(q-1))=1$. This property is assured if both primes are of equal length.

My doubt is, what is the actual worst case for integer factorization problem?

1) $n=pq $ and $length(p) = length(q)$ $\ge$ k, for some $k \ge 1024,2048 \cdots $

2) $n=pq$ and $|length(p)-length(q)| \le k$, for some $k \ge 1,2,3\cdots$

Provide reference stating the worst case for integer factorization with particular values of $k$

Answer 1

My doubt is, what is the actual worst case for integer factorization problem?

...

Provide reference stating the worst case for integer factorization with particular values of k

Such a statement can not be done for any class of algorithms at all, only a specific algorithm can have a worst case runtime.

In general, worst case estimations are barely used in cryptography at all, because the average case matters much more. Here's an example for that: Assume you had a new, hypothetical factorization algorithm, which has linear runtime for composite numbers on almost all inputs, but for values of the factorial function it has exponential runtime. Now the worst-case runtime is exponential, but the average is barely more than linear. And even worse: In the cases of $x!$ as input,the input is divisibly by $2$ when $x>1$, so just run the algorithm on $x!/2$ instead, with its linear runtime. This would make factorization entirely useless for cryptography - but the algorithm has exponential worst case runtime. Worst case assumptions are only useful if you can somehow reduce the average case to the worst case (possibly under randomized reductions, etc.) - for example in lattice-based cryptography these methods apply.

When looking at known factorization algorithms, there are some which scale with the size of the smallest prime factor, some scale with the total length of the numbers and some on "closeness of prime factors". In order to counter them all, suggestions like the ones you found are often made. However, those suggestions are made in reference to known algorithms not proven in any way whatsoever.

In order to get actual current state-of-the-art recommendations, keylength.com lists the recommendations of various sources with the publication date. The latest one references the BSI publication of Feb 2017 here: Publication in German, edit: found the English Verison

It has the following suggestion in the subsection RSA:

$\epsilon_1 < |\log_2(p) - \log_2(q)| < \epsilon_2$

And the suggested values for the boundaries are: $\epsilon_1 \approx 0.1, \epsilon_2 \approx 30$. The value $0.1$ for the metric would imply that $p/q$ differs from $1$ by at least a factor of $\approx 1.07177346$, which implies roughly if given the smaller prime $p$, that $q > (1+\frac{1}{14})p$, which in return means for length $b$ primes, the difference should be at least $b-4$ bits (which would mean the difference is $1/16$, but it should be $1/14$ or more).

Answer 2

If you allow the primes to be of radically different size, elliptic curve factoring could be faster than the number field sieve. But it seems like both your options preclude that happening.

Therefore, for either of your cases, the best known factoring algorithm is the number field sieve, which doesn't much care about the size of the factors. Which means that both cases are equally hard, as long as the size of the product is about the same.

As for references, any reasonably recent key length study should contain (a reference to) a reasonably complete survey on factoring algorithms, from which the above can be deduced.