TITLE: Are $10^{10}$-digit-numbers too big for Lenstra's elliptic curve method (ECM)?
QUESTION [0 upvotes]: I would like to search prime factors of the numbers
$$10^{10^{10}}-113$$ 
and
$$10^{10^{10}}+13$$
Both numbers have no prime factor below $10^9$.
Are these numbers still too big for ECM ?
I also tried an improved (?) version of the trial division to find a factor of n :
Produce a long array of random numbers $a_1,...,a_k$. Check, if there are $i\ne j$
such that $\gcd(a_i-a_j,n) \ne 1$, but did not find a factor of one of the above
numbers with this method.

REPLY [6 votes]: On my desktop machine as of 2006, a single ECM curve run on a $10^4$-decimal-digits number with $B_1=11000$ (good for $20$-digit factors) takes more than a minute on a $2.5$-GHz core.
Modmul complexity is worse than $\operatorname{O}(n\log n)$ where $n$ is the digit-count of the operands.
Therefore, my runtime estimate for a $10^{10}$-digit-number gets to more than $2.5\cdot10^6$ minutes per curve on a single core. That's roughly $5$ years. Decide for yourself.
Edit: Nowadays memory bandwidth has increased considerably, but that speedup still leaves the above runtime in the order of several months.
{"set_name": "stack_exchange", "score": 0, "question_id": 640353}