| dbo:abstract
|
- La réduction de Montgomery est un algorithme efficace pour la multiplication en arithmétique modulaire introduit en 1985 par Peter L. Montgomery. Plus concrètement, c'est une méthode pour calculer : La méthode est surtout efficace lorsqu'un grand nombre de multiplications modulaires avec un même n doivent être effectuées car le calcul nécessite des étapes de normalisation. Elle est donc particulièrement adaptée au calcul d'exponentiation modulaire. Elle est maintenant très utilisée en cryptologie. (fr)
- In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery. Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double-width product ab using division by N and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant R > N which is coprime to N, and the only division necessary in Montgomery multiplication is division by R. The constant R can be chosen so that division by R is easy, significantly improving the speed of the algorithm. In practice, R is always a power of two, since division by powers of two can be implemented by bit shifting. The need to convert a and b into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms. However, when performing many multiplications in a row, as in modular exponentiation, intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with R a power of two are faster than the available alternatives. (en)
- モンゴメリ乗算（モンゴメリじょうざん、英: Montgomerymultiplication）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで、効率的に整数の積の剰余を求めることのできるアルゴリズムである。 応用において、特に暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余の演算にモンゴメリ乗算が用いられている。 モンゴメリ乗算の名称は提案者の Peter Montgomery に由来する。 モンゴメリ乗算はまた、モンゴメリ法 (英: Montgomery method) 、モンゴメリ剰余乗算 (英: Montgomery modular multiplication) とも呼ばれる。 (ja)
- Алгоритм Монтгомери — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведении числа в степень по модулю, когда модуль велик (порядка сотен бит).Был предложен в 1985 году Питером Монтгомери. По данным целым числам a, b < n, r, НОД алгоритм Монтгомери вычисляет В приложениях обычно берётся , так как в этом случае деление с остатком и умножение на , используемые внутри алгоритма, происходят быстро. (ru)
- 在算术运算，蒙哥马利算法(Montgomery reduction)是一种快速大数（通常是几百個二進位）， 由在1985年提出。 蒙哥马利算法利用了以下這個被稱為「蒙哥马利约分」的步驟來簡化模乘的算法： (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 27935 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- La réduction de Montgomery est un algorithme efficace pour la multiplication en arithmétique modulaire introduit en 1985 par Peter L. Montgomery. Plus concrètement, c'est une méthode pour calculer : La méthode est surtout efficace lorsqu'un grand nombre de multiplications modulaires avec un même n doivent être effectuées car le calcul nécessite des étapes de normalisation. Elle est donc particulièrement adaptée au calcul d'exponentiation modulaire. Elle est maintenant très utilisée en cryptologie. (fr)
- モンゴメリ乗算（モンゴメリじょうざん、英: Montgomerymultiplication）とは、特に時間のかかる除算を実質的に行うことなく、乗算・加算・減算・シフト演算のみで、効率的に整数の積の剰余を求めることのできるアルゴリズムである。 応用において、特に暗号理論の分野では、数百ビットを超える法による冪剰余演算が重要な役割を果たし、このような冪剰余の演算にモンゴメリ乗算が用いられている。 モンゴメリ乗算の名称は提案者の Peter Montgomery に由来する。 モンゴメリ乗算はまた、モンゴメリ法 (英: Montgomery method) 、モンゴメリ剰余乗算 (英: Montgomery modular multiplication) とも呼ばれる。 (ja)
- Алгоритм Монтгомери — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведении числа в степень по модулю, когда модуль велик (порядка сотен бит).Был предложен в 1985 году Питером Монтгомери. По данным целым числам a, b < n, r, НОД алгоритм Монтгомери вычисляет В приложениях обычно берётся , так как в этом случае деление с остатком и умножение на , используемые внутри алгоритма, происходят быстро. (ru)
- 在算术运算，蒙哥马利算法(Montgomery reduction)是一种快速大数（通常是几百個二進位）， 由在1985年提出。 蒙哥马利算法利用了以下這個被稱為「蒙哥马利约分」的步驟來簡化模乘的算法： (zh)
- In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery. (en)
|
| rdfs:label
|
- Réduction de Montgomery (fr)
- Montgomery modular multiplication (en)
- モンゴメリ乗算 (ja)
- Алгоритм Монтгомери (ru)
- 蒙哥马利算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
