About: Kochanski multiplication     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Rule105846932, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FKochanski_multiplication&invfp=IFP_OFF&sas=SAME_AS_OFF

Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange. For an n-bit multiplier, this will take n clock cycles (where each cycle does either a shift or a shift-and-add). This algorithm works. However, it is critically dependent on the speed of addition.

AttributesValues
rdf:type
rdfs:label
  • Kochanski multiplication (en)
rdfs:comment
  • Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange. For an n-bit multiplier, this will take n clock cycles (where each cycle does either a shift or a shift-and-add). This algorithm works. However, it is critically dependent on the speed of addition. (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange. The most common way of implementing large-integer multiplication in hardware is to express the multiplier in binary and enumerate its bits, one bit at a time, starting with the most significant bit, perform the following operations on an accumulator: 1. * Double the contents of the accumulator (if the accumulator stores numbers in binary, as is usually the case, this is a simple "shift left" that requires no actual computation). 2. * If the current bit of the multiplier is 1, add the multiplicand into the accumulator; if it is 0, do nothing. For an n-bit multiplier, this will take n clock cycles (where each cycle does either a shift or a shift-and-add). To convert this into an algorithm for modular multiplication, with a modulus r, it is necessary to subtract r conditionally at each stage: 1. * Double the contents of the accumulator. 2. * If the result is greater than or equal to r, subtract r. (Equivalently, subtract r from the accumulator and store the result back into the accumulator if and only if it is non-negative). 3. * If the current bit of the multiplier is 1, add the multiplicand into the accumulator; if it is 0, do nothing. 4. * If the result of the addition is greater than or equal to r, subtract r. If no addition took place, do nothing. This algorithm works. However, it is critically dependent on the speed of addition. Addition of long integers suffers from the problem that carries have to be propagated from right to left and the final result is not known until this process has been completed. Carry propagation can be speeded up with carry look-ahead logic, but this still makes addition very much slower than it needs to be (for 512-bit addition, addition with carry look-ahead is 32 times slower than addition without carries at all). Non-modular multiplication can make use of carry-save adders, which save time by storing the carries from each digit position and using them later: for example, by computing 111111111111+000000000010 as 111111111121 instead of waiting for the carry to propagate through the whole number to yield the true binary value 1000000000001. That final propagation still has to be done to yield a binary result but this only needs to be done once at the very end of the multiplication. Unfortunately the modular multiplication method outlined above needs to know the magnitude of the accumulated value at every step, in order to decide whether to subtract r: for example, if it needs to know whether the value in the accumulator is greater than 1000000000000, the carry-save representation 111111111121 is useless and needs to be converted to its true binary value for the comparison to be made. It therefore seems that one can have either the speed of carry-save or modular multiplication, but not both. (en)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software