1
$\begingroup$

Suppose $n=pq$, where $p,q$ are prime numbers.

Let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$.

In trail division, we check $n \mod i$ for the values of $i$ from 2 to $\sqrt{n}$, to find the value of $p$ and then we calculate $\dfrac{n}{p}$ to get $q$.

In general, the time complexity is (assuming finding remainder and division takes place in constant time) $\sqrt{n}$.

How to calculate cryptographic time complexity?

Suppose $b$ is the number of bits to represent $n$ in binary format, then can I directly substitute in $\sqrt{n}$, so that I can get $2^{\frac{b}{2}}$.

Or should it be calculated as $(\sqrt{n}-1)*$ time taken for modulo operation $+$ time taken for division?

How to arrive at time complexity in terms of $b$?

How much time does it take for calculating modulo and division in terms of bits? If we substitute those values, finally should we get $2^{\frac{b}{2}}$?

Improve this question
$\endgroup$
1
$\begingroup$

Your assumption "(assuming finding remainder and division takes place in constant time)" is not fulfilled here. We are dealing with big numbers and division complexity is some function M(b) where M is the complexity of your multiplication algorithm, e.g., Schönhage-Strassen with O(b log b log log b). Schoolbook division is of order b².

Note that for cryptographic purposes n is really huge; even a polynomial time algorithm in n (exponential in b) is not feasible here.

EDIT: A note on complexity computation: Only leading terms in a sum are relevant, lower order terms are always negligible. When you complexity is already exponential, you can neglect polynomial factors. Therefore the complexity of division is just mentioned to make clear that your assumptions did not hold in the first place, it turns out to be negligible in the course of the argument.

NOTE: This all assumes a classical computer as model of computation. With a quantum computer, you can factorize an integer in polynomial time using Shor's algorithm. Current published Quantum Computers have 14 QBits and can factorise the integer 15 (fifteen). Apply Moore's law and some leeway for non-published Quantum Computers and you have an estimate when this kind of cryptography will be broken.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yeah, my doubt is how to calculate the time complexity in such cryptographic algorithm. Isnow time complexity will $(2^{\frac{b}{2}}-1)*b \log b \log \log b + b^2$? $\endgroup$ – hanugm Nov 16 '15 at 13:07
  • 1
    $\begingroup$ Add a ceiling function and you are well in the order of magnitude $2^{\lceil\frac{b}{2}\rceil}$ (all other factors don't really matter, given the size of the product) $\endgroup$ – jk - Reinstate Monica Nov 16 '15 at 13:12
  • $\begingroup$ Does the time complexity for a modulo operation is $b^2$? $\endgroup$ – hanugm Nov 23 '15 at 4:22
  • $\begingroup$ Is it correct that answer is $b*2^{b/2}$? $\endgroup$ – hanugm Nov 23 '15 at 4:28
  • 1
    $\begingroup$ You can neglect the factor $b$. When you expand $2^\frac{b}{2}$ into a power series, all powers of $b$ will occur. Multiplying the power series with $b$ will not change the overall picture (just increase all powers by $1$. $\endgroup$ – jk - Reinstate Monica Nov 23 '15 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.