0
$\begingroup$

If I am multiplying two numbers $m$ and $n$, where $n$ has $k$ digits and $m$ has at most $n/2$ digits, will it be considered polynomial time or exponential time in terms of $k$?

Addition (by proxy of mod): This multiplication's time will be exponential in $k$ (answering the above), yet polynomial in size of $m$. Will it be called an efficient result or not?

$\endgroup$
2
  • 2
    $\begingroup$ Plese read the "Do we accept basic level/homework questions?" section of our help page on what's on-topic. Is anything unclear with "please provide an indication of what you are not understanding / need clarification on and your attempts at solving it?" $\endgroup$
    – fgrieu
    Dec 11 '20 at 15:53
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – fgrieu
    Dec 11 '20 at 17:33
1
$\begingroup$

The maximum size of $m$ is $n/2$, and the maximum value of $n$ is $10^k-1$. It follows that the size of $m$ is exponential in $k$. Since (when $n>0$) the multiplication algorithm must read the whole of $m$, and that takes time at least proportional to the size of $m$, it follows that the complexity is at least exponential in $k$.

From a theoretical standpoint, the multiplication is thus not efficient for security parameter $k$, since efficient is defined as time bounded by a polynomial of the security parameter.

If the security parameter was $n$, the algorithm could be efficient (and we could prove that by exhibiting a multiplication algorithm with cost bounded by a polynomial in $n$, which is easy: the schoolbook algorithm turns out to be enough; this is left as an exercise to the reader).

In a crypto context, we want the security parameter to be such that it makes the normal user's cost at most polynomial (i.e. efficient), but the attacker's (conjectured) cost at least super-polynomial (hopefully exponential). Thus if our algorithm is to be considered interesting, then

  • if that multiplication is to be performed by the user, it must be efficient and thus our parameter can't be $k$.
  • if that multiplication is to be performed by an attacker in an attack, but not by the legitimate user, our parameter can be $k$, and probably should be. The multiplication then can be efficient (and is, unless the multiplication algorithm is abysmally inefficient).
$\endgroup$
5
  • $\begingroup$ Actually, the complexity is performed with the number of bits representation. Though, you can argue that in the Big-Oh notation that is a constant term, we still use the number of bits. Finally, In recent work, the cost of multiplication is shown to be $n\log n$. $\endgroup$
    – kelalaka
    Dec 11 '20 at 19:35
  • $\begingroup$ @kelalaka: when doing large integer arithmetic, complexity is often expressed per number of digits (or limbs) in the base used (see this reference). As you mention, that does not change the complexity class, or even the degree of the complexity polynomials. I was careful to write my answer so that it is valid regardless of the exact cost of multiplication. I wrote about the practical consequences of the recent work you mention here. $\endgroup$
    – fgrieu
    Dec 11 '20 at 21:24
  • $\begingroup$ In complexity classes, it is taught as the number of bits as common agreement, AFAIK. Isn't the Brent and Zimmermann give the table in bits? Since the OP is a beginner they would like to learn that way? $\endgroup$
    – kelalaka
    Dec 11 '20 at 21:44
  • 2
    $\begingroup$ @kelalaka: yes, the modern unit for complexity parameter in crypto is bits. That has evolved over time, and initially that was number of characters in the key for symmetric systems, and number of decimal digits in number-theoretic crypto (the only mention of bit in the original RSA article is to disparage them). And when it comes to compute the cost of a multiplication algorithm on a computer with the schoolbook algorithm, Karatsuba, Toom-Cook, or Montgomery modular multiplication, references tend to count words (aka limbs) rather than bits. $\endgroup$
    – fgrieu
    Dec 12 '20 at 7:55
  • $\begingroup$ Made small edits. Thanks for the last comment, too, $\endgroup$
    – kelalaka
    Dec 12 '20 at 17:57

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.