Time Complexity of RSA Trial Division

ikeachairs

3/12/24, 2:58 AM

I'm having trouble understanding how time complexity of trial division is exponential.

If it takes $\sqrt n$ tries to factor $n$ in the worst case scenario then time complexity is $\mathcal{O}(\sqrt n)$, which I thought would mean that the number of operations grows slower than the increase in the number of inputs. So how would that be inefficient if polynomial time is considered efficient?

It makes sense that trial division would be inefficient but I can't seem to wrap my head around it in terms of time complexity. I also saw somewhere that the time complexity is actually $\mathcal{O}({e^n \over 2})$ but I'm not sure how they arrived at that.

277

1 + 0

brute-force-attack

factoring

Score:5

Crypto

James

3/12/24, 3:07 AM

Time complexity is measured as the time taken in function of the size of the input. The reason for this is that it can be used to describe the complexity of any algorithm, not just algorithms operating on numbers, and the input size is always well defined for any type of input.

A key of size $n$ bits can be a number up to $2^n$, so $\sqrt{2^n} = (\sqrt{2})^n$ divisions are required, an exponential function in $n$.

+ 1

Paŭlo Ebermann

3/13/24, 12:18 AM

The time for a division is also depending on the size of both numbers.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Time Complexity of RSA Trial Division

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.