Réduction de Barrett

En arithmétique modulaire, la réduction de Barrett est un algorithme de réduction introduit en 1986 par Paul D. Barrett[1]. Une façon naïve de calculer :

serait d'utiliser un algorithme de division rapide ; la réduction de Barrett est un algorithme conçu pour optimiser cette opération en supposant constant et , remplaçant les divisions par des multiplications.

Idée générale

Soit l'inverse de comme nombre à virgule flottante. Alors

est la fonction partie entière. Le résultat est exact, tant que est calculé avec une précision suffisante.

Réduction de Barrett à un mot machine

Barrett a initialement considéré une version de l'algorithme ci-dessus sur les nombres entiers qui tiennent dans un seul mot machine.

En calculant avec la méthode ci-dessus, mais avec des entiers, l'analogue évident serait la division par :

func reduire(a uint) uint {
  q := a / n  // La division retourne implicitement la partie entière du résultat
  return a - q * n
}

Cependant, la division est lente et, dans les algorithmes de cryptographie, peut ne pas être une opération en temps constant sur certains processeurs. Ainsi, la réduction de Barrett approxime par la valeur , car la division par est juste un décalage de bits vers la droite, donc est très rapide.

Afin de calculer la meilleure valeur pour étant donné , on considère :

Pour que soit un entier, on a besoin d'arrondir d'une certaine manière. Arrondir à l'entier le plus proche donnerait la meilleure approximation mais peut faire que soit plus grand que , qui peut provoquer un soupassement arithmétique. Ainsi, est généralement utilisé.

La fonction reduire ci-dessus peut donc être approximée par :

func reduire(a uint) uint {
  q := (a * m) >> k // ">> k" est le décalage de k bits vers la droite.
  return a - q * n
}

Cependant, puisque , la valeur de dans cette fonction peut être un peu trop petite, et ainsi est seulement garantie d'être dans plutôt que comme c'est généralement requis. Une soustraction conditionnelle peut corriger cela :

func reduire(a uint) uint {
  q := (a * m) >> k
  a -= q * n
  if n <= a {
    a -= n
  }
  return a
}

Puisque est seulement une approximation, l'intervalle de validité de doit être considéré. L'erreur sur l'approximation de est:

Ainsi, l'erreur sur la valeur de est . Tant que , la réduction sera valide, d'où . La fonction de réduction peut ne pas donner immédiatement un mauvais résultat quand mais la borne sur doit être respectée pour garantir une réponse correcte dans le cas général.

En choisissant de plus grandes valeurs de , l'intervalle des valeurs de pour lesquelles la réduction est valide peut-être augmentée, mais de plus grandes valeurs de peut causer des dépassements d'entiers.

Exemple

Regardons le cas en utilisant des entiers de 16 bits.

La plus petite valeur de qui a du sens est car si alors la réduction ne sera valide que pour des valeurs qui sont déjà minimales ! Pour une valeur de sept, . Pour une valeur de huit . Ainsi ne donne aucun avantage car l'approximation de , dans ce cas , est exactement la même que . Pour , on obtient , qui donne une meilleure approximation.

Maintenant, considérons les intervalles de validité pour et .

Dans le premier cas, donc implique . Puisque est un entier, la valeur maximum effective est 478. (En pratique la fonction donne le bon résultat jusque 504.)

Si on prend alors et donc la valeur maximum de est 7387. (En pratique la fonction donne le bon résultat jusque 7473.)

La valeur suivante de qui donne une meilleure approximation est 13, donnant . Cependant, notons que la valeur intermédiaire dans les calculs va dépasser la capacité d'un entier 16 bits non-signé lorsque , ainsi fonctionne mieux dans cette situation.

Preuve de l'intervalle de validité pour un certain k

Soit le plus petit entier tel que . Prenons comme valeur raisonnable pour dans les équations précédentes. Comme dans les fragments de code ci-dessus, soit

  • et
  • .

Grâce à la fonction partie entière, est un entier et . Aussi, si alors . Dans ce cas, en écrivant le fragment de code en expression :

La preuve que est alors immédiate :

Si , alors

Puisque indépendamment de , on obtient :

Réduction de Barrett à plusieurs mots machine

La motivation initiale de Barrett pour sa réduction était l'implémentation de RSA, lorsque les valeurs en question dépassent la taille d'un mot machine. Dans cette situation, Barrett donne un algorithme qui approxime la version à un mot ci-dessus mais pour des valeurs sur plusieurs mots. Pour plus de détails, voir la section 14.3.3 de Handbook of Applied Cryptography[2].

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Barrett reduction » (voir la liste des auteurs).
  1. P. Barrett, Advances in Cryptology — CRYPTO' 86, vol. 263, coll. « Lecture Notes in Computer Science », , 311–323 p. (ISBN 978-3-540-18047-0, DOI 10.1007/3-540-47721-7_24), « Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor »
  2. Alfred Menezes, Paul Oorschot et Scott Vanstone, Handbook of Applied Cryptography (ISBN 978-0-8493-8523-0 et 0-8493-8523-7, lire en ligne Inscription nécessaire)

Voir aussi

Sources

  • A. Bosselaers, R. Govaerts, J. Vandewalle et Douglas R. Stinson (dir.), Advances in Cryptology — Crypto'93, vol. 773, Springer, coll. « Lecture Notes in Computer Science », , 175–186 p. (ISBN 3-540-48329-2, lire en ligne), « Comparison of Three Modular Reduction Functions »
  • W. Hasenplaugh, G. Gaubatz et V. Gopal, 18th IEEE Symposium on Computer Arithmetic(ARITH'07), , 225-9 p. (ISBN 978-0-7695-2854-0 et 0-7695-2854-6, DOI 10.1109/ARITH.2007.18, lire en ligne), « Fast Modular Reduction »

Read other articles:

Census Town in West Bengal, IndiaAmkulaCensus TownAmkulaLocation in West Bengal, IndiaShow map of West BengalAmkulaAmkula (India)Show map of IndiaCoordinates: 23°36′56″N 87°04′43″E / 23.615439°N 87.078502°E / 23.615439; 87.078502Country IndiaStateWest BengalDistrictPaschim BardhamanArea • Total3.01 km2 (1.16 sq mi)Population (2011) • Total809,090 • Density270,000/km2 (700,000/sq mi)Languages*...

 

  هذه المقالة عن طريق تيزي وزو الساحلي. لمعانٍ أخرى، طالع تيزي وزو (توضيح). الطريق الوطني رقم 24في الجزائر مسار الطريق الوطني رقم 24 اسم آخر = طريق بجايةأو ڤݘايث أو بݘايث أو البلد الجزائر  تاريخ التصنيف طريق مزدوج، طريق سريع. المميزات الطول 230 كيلومتر الاتجاه غرب-شرق الن...

 

Cosimo de' Medicide Oude 1389 - 1464 Heer van Florence Periode 1434 - 1464 Voorganger - Opvolger Piero di Cosimo de' Medici Vader Giovanni di Bicci Moeder Piccarda de' Bueri Dynastie Huis Medici Cosimo de' Medici de Oude (Florence, 27 september 1389 - Careggi (Florence), 1 augustus 1464) was een zoon van bankier Giovanni di Bicci en een telg uit het roemruchte geslacht de' Medici. Hij was de eerste van zijn familie die de facto over Florence zou heersen als Heer van Florence. Biografie Cosimo...

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. SaudadeSutradara Katsuya Tomita ProduserDitulis oleh Toranosuke Aizawa Katsuya Tomita PemeranWesley BandeiraSinematograferTakako TakanoTanggal rilis 25 Juni 2011 (2011-06-25) (Locarno) 22 Oktober 2011 (2011-10-22) (Jepang) Durasi167 ...

 

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (avril 2018). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » En pratique : Quelles sources sont attendues ? Comm...

 

У Вікіпедії є статті про інші населені пункти з такою назвою: Цетуля. село Цетуля Церква Святого МиколаяЦерква Святого Миколая Країна  Україна Область Львівська Район Яворівський Громада Яворівська міська громада Код КАТОТТГ UA46140110740062899 Основні дані Засноване 1481 Насел

2013 American filmComputer ChessTheatrical release posterDirected byAndrew BujalskiWritten byAndrew BujalskiProduced byHouston KingAlex LipschultzStarringPatrick RiesterWiley WigginsMyles PaigeRobin SchwartzGerald PearyGordon KindlmannCinematographyMatthias GrunskyEdited byAndrew BujalskiDistributed byKino LorberRelease dates January 21, 2013 (2013-01-21) (Sundance) July 17, 2013 (2013-07-17) (United States) Running time92 minutesCountryUnited StatesLangu...

 

School of philosophical thought Sixteenth-century portrait of John Calvin by an unknown artist In the philosophy of religion, Reformed epistemology is a school of philosophical thought concerning the nature of knowledge (epistemology) as it applies to religious beliefs.[1] The central proposition of Reformed epistemology is that beliefs can be justified by more than evidence alone, contrary to the positions of evidentialism, which argues that while non-evidential belief may be benefic...

 

1290 anti-Jewish decree by Edward I of England This article is about the 1290 Edict of Expulsion from England. For the 1492 Edict of Expulsion from Spain, see Alhambra Decree. For other historic instances of Jews being expelled from the lands where they resided, see Expulsions and exoduses of Jews. This is a part of the series onHistory of theJews in England Medieval Early history (1066–1290) Exchequer of the Jews Early literature Synod of Oxford (1222) Statute of Jewry (1253) Statute of th...

Lamberthus JitmauWali Kota Sorong ke-2Masa jabatan22 Agustus 2017 – 22 Agustus 2022PresidenJoko WidodoGubernurDominggus MandacanWakilPahimah IskandarPendahuluWelly Tigtigweria (Plh.)PenggantiGeorge Yarangga (Pj.)Masa jabatan11 Juni 2012 – 11 Juni 2017PresidenSusilo Bambang YudhoyonoJoko WidodoGubernurAbraham Octavianus AtururiEko Subowo (Pj.)Dominggus MandacanWakilPahimah IskandarPendahuluJonathan Annes JumamePenggantiWelly Tigtigweria (Plh.) Informasi pribadiLahir(1...

 

В Википедии есть статьи о других людях с фамилией Полянский. Леонид Петрович Полянский Дата рождения 24 октября 1975(1975-10-24) Место рождения Жмеринка, Винницкая область, Украинская ССР, СССР Дата смерти 20 февраля 2014(2014-02-20) (38 лет) Место смерти Киев, Украина Страна  Украи...

 

Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Stephanus (Begriffsklärung) aufgeführt. Stephanus mit den Attributen Märtyrerpalme und Steinen. Der Heilige trägt die Dalmatik eines Diakons. Stephanus auf dem Wappen von Lank-Latum mit Spargelbündeln und Erdbeeren Stephanus ist im Neuen Testament ein Diakon der Jerusalemer Urgemeinde. Er gilt als erster Märtyrer des Christentums und wird daher oft auch als Erzmärtyrer oder Protomärtyrer bezeichnet. Sein Name deu...

Bintang Donald Trump di Hollywood Walk of Fame Artikel ini bagian dariseri tentangDonald Trump Presiden Amerika Serikat Kepresidenan Transisi Pelantikan Garis waktu Keputusan eksekutif proklamasi pengampunan Perjalanan 2017 2018 2019 internasional KTT Riyadh Singapura Helsinki Hanoi DMZ Penutupan Jan 2018 2018–2019 Jajak pendapat Unjuk rasa Foto di St. John Pandemi COVID-19 di Gedung Putih Proses pemakzulan Upaya pemakzulan Kontroversi Trump–Ukraina Pengangkatan pejabat Kabinet susunan Du...

 

American pornographic actress and director (1938–2010) Juliet AndersonJuliet Anderson, at the Free Speech Coalition's Night of the Stars, July 12, 2001.BornJudith Carr[1](1938-07-23)July 23, 1938[2]Burbank, California, U.S.[2]DiedJanuary 11, 2010(2010-01-11) (aged 71)[3]Berkeley, California, U.S.Other namesAunt Peg, Judith Anderson, Juliett Anderson, Judy Fallbrook, Ruby Sapphire, Judy Carr, Alice Rigby Juliet Anderson (born Judith Carr),[3]...

 

5

Ferrari P4/5 by PininfarinaInformasiProdusenFerrari / PininfarinaJuga disebutFerrari P4/5Masa produksi2006 1 unitPerakitanTurin, Italia (Pininfarina)Bodi & rangkaKelasMobil sportPintuKupu-kupu Ferrari P4/5 by Pininfarina adalah sebuah mobil yang dirancang ulang oleh Pininfarina, dengan model asli mobil sport Ferrari Enzo yang diproduksi oleh perusahaan mobil Italia, Ferrari. Mobil ini dibuat untuk sutradara James Glickenhaus, dan merupakan satu-satunya di dunia. Sejarah Ferrari ...

Retrato de caballero con una pata de león Autor Lorenzo LottoCreación años 1520Ubicación Museo de Historia del Arte de Viena (Austria)Material Óleo y TablaTécnica óleo sobre lienzoDimensiones 95,5 centímetros x 69,5 centímetros[editar datos en Wikidata] El Retrato de Leonino Brembati o Retrato de caballero con una pata de león es una pintura al óleo sobre lienzo de 95,5 x 69,5 cm de Lorenzo Lotto, de 1524-25 aproximadamente y conservado en el Kunsthistorisches Museum...

 

Ukrainian writer (born 1939) This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Valeriy Shevchuk – news · newspapers · books · scholar · JSTOR (May 2014) (Learn how and when to remove this template...

 

Species of protozoan parasite Trypanosoma tungarae Scientific classification Domain: Eukaryota Phylum: Euglenozoa Class: Kinetoplastea Order: Trypanosomatida Family: Trypanosomatidae Genus: Trypanosoma Species: T. tungarae Binomial name Trypanosoma tungaraeBernal & Pinto, 2016 Trypanosoma tungarae is a species of giant trypanosome, a protozoal parasite, which infects the túngara frog and is thought to be transmitted by members of the midge genus Corethrella. It was discovered in 201...

Eastern Catholic territorial jurisdiction in Rome, Italy Territorial Abbacy of Saint Mary of GrottaferrataAbbatia Territorialis Beatissimæ Mariæ Cryptæferratæ [1]Santa Maria di GrottaferrataCathedral of Exarchial Monastery of St. Mary of GrottaferrataLocationCountryItalyEcclesiastical provinceHoly See[1]StatisticsParishes1Churches1Schools1Members87[2]InformationDenominationItalo-Albanian Catholic ChurchRiteByzantine RiteEstablished1937[1]CathedralExarchial ...

 

Census-designated place in California, United StatesGratoncensus-designated placeGraton storefronts on north side of Graton Road between Ross Road and South Edison StreetLocation in Sonoma County and the state of CaliforniaCoordinates: 38°26′15″N 122°51′59″W / 38.43750°N 122.86639°W / 38.43750; -122.86639Country United StatesState CaliforniaCountySonomaArea[1] • Total1.579 sq mi (4.090 km2) • Land1.57...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!