REPOST: Re: Karatsuba threshold for unequal operand lengths

From: BRG (brg_at_nowhere.org)
Date: 11/03/05 

Date: Wed, 02 Nov 2005 23:27:57 +0000

Ray wrote:
>> ... it will then be
>> better to apply ordinary multiplication with large 'digits' - that is,
>> using the Karatsuba technique to multiply 'digits' each of whose length
>> is that of the smaller number.
> --- Brian, are you suggesting to use, in this case, a modified
> karatsuba by multiplying 2x1 digits instead of 2x2 ?

No.

As an example, if we want to multiply 148 by 9, we can first multiply 8
by 9 to give 72 - a low digit of 2 and a carry of 7 into the next digit.
 We then multiply 4 by 9 and add in the carry of 7 to give 43, a result
digit of 3 and a carry of 4. We then finally multiply 1 by 9 and add the
carry of 4 to give 13 so the result is 1332. So we can step along the
long number a digit at a time multiplying to produce a result digit and
a carry into the next digit.

Now in this process we don't have to restrict ourselves to small
'digits' - we can use very large 'Karatsuba size' digits and still use
exactly the same process. Hence we can express a number that is 2 * N
bits long as a two 'digit' number in which each 'digit' has N bits : hi
* 2^N + lo. And to multiply this by the N bit number X, we multiply lo *
X to give a low N-bit number and a carry. We then add hi * X to this
carry to give the hi N bit number and another carry into the next N bits
of the product.

In other words we just apply 'schoolbook' multiplication with huge
'digits' and use Karatsuba when we multiply these digits. The Karatsuba
part of the algorithm is not changed in any way.

   Brian Gladman

========= WAS CANCELLED BY =======:
Subject: Re: Karatsuba threshold for unequal operand lengths
From: BRG <brg@nowhere.org>
Date: Thu, 2 Nov 2005 21:21:58 GMT
Message-ID: <02081c2f_1%35027_ed3d13a0@ptn-nntp-reader04.plus.net>
Lines: 13
Path: ...news.glorb.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news-out.spamkiller.net!spool6-east.superfeed.net!spool6-east.superfeed.net!not-for-mail
Newsgroups: sci.crypt
Control: cancel <43694b6c$0$63074$ed2e19e4@ptn-nntp-reader04.plus.net>
X-Report: Please report illegal or inappropriate use to <abuse@newsfeeds.com>. Forward a copy of ALL headers INCLUDING the body. (DO NOT SEND ATTACHMENTS)
X-Comments2: IMPORTANT: Newsfeeds.com does not condone,support,nor tolerate spam or any illegal or copyrighted postings.
X-Comments: This message was posted through Newsfeeds.com

========= WAS CANCELLED BY =======:
Path: ...newsfeed.news2me.com!news.glorb.com!hwmnpeer01.lga!hwmedia!hw-filter.lga!fe10.lga.POSTED!53ab2750!not-for-mail
From: BRG <brg@nowhere.org>
Control: cancel <1$%$$-%___%$$-$$%_$@news.noc.cabal.int>
Subject: REPOST: Re: Karatsuba threshold for unequal operand lengths
Newsgroups: sci.crypt
Message-ID: <3-%$$$_-%%-_$%-_-__@news.noc.cabal.int>
Lines: 2
Date: Fri, 3 Nov 2005 17:25:02 GMT
NNTP-Posting-Host: 68.198.254.63
X-Complaints-To: abuse@cv.net
X-Trace: fe10.lga 1131048151 68.198.254.63 (Thu, 03 Nov 2005 13:02:31 MST)
NNTP-Posting-Date: Thu, 03 Nov 2005 13:02:31 MST
Organization: Optimum Online

Relevant Pages

  • Re: Tuning Karatsuba in LibTomMath
    ... And there is faster things than Karatsuba, ... In fact for multiplications my testing on an Athlon XP ... 103 digits amounts to 2884 bits which means for most RSA ... Note though that LTM is not an RSA bignum lib. ...
    (sci.crypt)
  • Re: str(bigint) is slow
    ... Tim Peters wrote: ... >> half the number of digits, and continue recursively in both halves. ... > Python uses Karatsuba for multiplication, ... Univ. of California, Irvine, School of Information & Computer Science ...
    (comp.lang.python)
  • REPOST: Re: Karatsuba threshold for unequal operand lengths
    ... > using the Karatsuba technique to multiply 'digits' each of whose length ... --- Brian, are you suggesting to use, in this case, a modified ... karatsuba by multiplying 2x1 digits instead of 2x2? ...
    (sci.crypt)
  • REPOST: Re: Karatsuba threshold for unequal operand lengths
    ... > using the Karatsuba technique to multiply 'digits' each of whose length ... karatsuba by multiplying 2x1 digits instead of 2x2? ... Newsgroups: sci.crypt ...
    (sci.crypt)
  • Re: Karatsuba threshold for unequal operand lengths
    ... >> using the Karatsuba technique to multiply 'digits' each of whose length ... long number a digit at a time multiplying to produce a result digit and ...
    (sci.crypt)
Quantcast