Exponentiation rapide

En informatique, l'exponentiation rapide est un algorithme utilisé pour calculer rapidement de grandes puissances entières. En anglais, cette méthode est aussi appelée square-and-multiply (« mettre au carré et multiplier »).

Écriture mathématique

La première façon de calculer une puissance $x n$ est de multiplier $x$ par lui-même $n$ fois. Cependant, il existe des méthodes bien plus efficaces, où le nombre d'opérations nécessaires n'est plus de l'ordre de $n$ mais de l'ordre de $ln(n)$ .

Par exemple, en base 2, $n=\sum _{k=0}^{d}a_{k}2^{k}$ pour $a_{k}\in \{0,1\}$ . Donc,

x^{n}=x^{a_{0}}(x^{2})^{a_{1}}(x^{2^{2}})^{a_{2}}\dots (x^{2^{d}})^{a_{d}}

Il faut ainsi $d$ opérations pour calculer tous les $x^{2^{k}}$ , puis $d$ opérations supplémentaires pour former le produit des $(x^{2^{k}})^{a_{k}}$ . Le nombre total d'opérations est donc $2 d$ , qui est bien de l'ordre du logarithme de $n$ . Cette simple remarque algébrique conduit à l'algorithme présenté dans la section suivante.

Algorithme

Soit $n$ un entier strictement supérieur à $1$ , supposons que l'on sache calculer, pour chaque réel $x$ , toutes les puissances $x k$ de $x$ , pour tout $k$ , tel que $1 \leq k < n$ .

Si $n$ est pair alors $x n = (x 2) n /2$ . Il suffit alors de calculer $y n /2$ pour $y = x 2$ .
Si $n$ est impair et $n > 1$ , alors $x n = x (x 2) (n - 1)/2$ . Il suffit de calculer $y (n - 1)/2$ pour $y = x 2$ et de multiplier le résultat par $x$ .

Cette remarque nous amène à l'algorithme récursif suivant qui calcule $x n$ pour un entier strictement positif $n$ :

{\mbox{puissance}}(x,\,n)=\left\{{\begin{matrix}x,&{\mbox{si }}n{\mbox{ = 1}}\\{\mbox{puissance}}(x^{2},\,n/2),&{\mbox{si }}n{\mbox{ est pair}}\\x\times {\mbox{puissance}}(x^{2},\,(n-1)/2),&{\mbox{si }}n{\mbox{ est impair}}\\\end{matrix}}\right.

En comparant à la méthode ordinaire qui consiste à multiplier $x$ par lui-même $n - 1$ fois, cet algorithme nécessite de l'ordre de $O (log n)$ multiplications et ainsi accélère le calcul de $x n$ de façon spectaculaire pour les grands entiers.

La méthode fonctionne dans tout semi-groupe et est souvent utilisée pour calculer des puissances de matrices, et particulièrement en cryptographie, mais aussi pour calculer les puissances dans un anneau d'entiers modulo $q$ . Elle peut être aussi utilisée pour calculer des puissances d'un élément dans un groupe, en utilisant pour les puissances négatives la règle : $puissance(x, - n) = (puissance(x, n)) -1$ . C'est cette méthode que l'on applique lorsque l'on effectue la multiplication de deux nombres chiffre par chiffre en base 2 : le groupe est $(\mathbb {Z} ,+)$ .

Voir aussi

Liens externes

(en) Implémentation dans divers langages de programmation, sur rosettacode.org
(en) Nombre exact de multiplications avec cet algorithme : suite A014701 de l'OEIS

Read other articles:

Vicente Rondón

Vicente Rondón Nazionalità Venezuela Altezza 191 cm Pugilato Categoria Pesi medi, mediomassimi e massimi Termine carriera 1974 Carriera Incontri disputati Totali 59 Vinti (KO) 40 (23 per KO) Persi (KO) 16 (7) Pareggiati 1 Statistiche aggiornate al marzo 2020 Modifica dati su Wikidata · Manuale Vicente Paúl Rondón (Andrés Bello, 29 luglio 1938 – Caracas, 28 dicembre 1992) è stato un pugile venezuelano, campione mondiale WBA dei pesi mediomassimi. Indice 1 Biografia 1.1...

Laura Ricciardi

American Filmmaker (b. 1970) Laura RicciardiBorn1970 (age 53–54)EducationManhattan College (BA)New York Law School (JD)Columbia University School of the Arts (MFA in Film)Notable workMaking a Murderer Seasons 1 & 2AwardsPrimetime Creative Arts Emmy Awards (3) Laura Ricciardi (born 1970)[1] is an American filmmaker. Ricciardi is best known for the Netflix documentary television series Making a Murderer, which she cocreated with filmmaker Moira Demos. Along with Demos, Ri...

Sten

Disambiguazione – Se stai cercando altri significati, vedi Sten (disambigua). StenUno Sten Mk. IITipoMitra Origine Regno Unito ImpiegoUtilizzatoriRegno Unito, Commonwealth, Francia, Israele, Italia, Movimenti clandestini e di Resistenza ConflittiSeconda guerra mondiale, Guerra di Corea, Crisi di Suez, Resistenza italiana, Guerra in Malesia, Guerra di Indocina (tra gli altri) ProduzioneProgettistaReginald V. Sheperd Harold J. Turpin Date di produzione1941-? Numero prodot...

Associazione Sportiva Roma 1998-1999

Voce principale: Associazione Sportiva Roma. AS RomaStagione 1998-1999 Sport calcio Squadra Roma Allenatore Zdeněk Zeman Presidente Franco Sensi Serie A5º (in Coppa UEFA) Coppa ItaliaOttavi di finale Coppa UEFAQuarti di finale Miglior marcatoreCampionato: Delvecchio (18)Totale: Delvecchio (23) StadioOlimpico Abbonati33 256[1] Maggior numero di spettatori75 290[1] vs Lazio(11 aprile 1999) Minor numero di spettatori41 126[1] vs Empoli(31 gennaio 19...

Development of COVID-19 tests

History of medical research Part of a series on theCOVID-19 pandemicScientifically accurate atomic model of the external structure of SARS-CoV-2. Each ball is an atom. COVID-19 (disease) SARS-CoV-2 (virus) Cases Deaths Timeline 2019 2020 January responses February responses March responses April responses May responses June responses July responses August responses September responses October responses November responses December responses 2021 January responses February responses March respo...

Lembah Sind

Koordinat: 34°17′21″N 74°48′45″E / 34.28917°N 74.81250°E / 34.28917; 74.81250 Lembah Sind Valley Wayil, Lembah Sind Negara India Provinsi Jammu dan Kashmir Region Divisi Kashmir Kabupaten Ganderbal Munisipalitas Kangan Batas Zojila (timur)Lembah Kashmir (barat) Sungai Sungai Sind Titik tertinggi - lokasi Baltal - elevasi 9.364 m (30.722 ft) Titik terendah - lokasi Wayil - elevation 5.505 ft (1.678 m...

Сибирский горный козёл

Сибирский горный козёл Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКла�...

سيرج حاروش

سيرج حاروش معلومات شخصية الميلاد 11 سبتمبر 1944 (80 سنة)[1][2] الدار البيضاء[3][4][5] مواطنة فرنسا[6] عضو في الأكاديمية الفرنسية للعلوم، والأكاديمية الوطنية للعلوم، والمعهد الجامعي الفرنسي [لغات أخرى]‏، والأكاديمية الأمريكي�...

四人帮

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。此條目可能包含原创研究。 (2018年3月29日)请协助補充参考资料、添加相关内联标签和删除原创研究内容以改善这篇条目。详细情况请参见讨论页。此條目需要补充更多来源。 (2010年2月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一�...

Mines on the Italian front (World War I)

A mine gallery in the ice at Pasubio The Italian front in 1915–1917, initial Italian conquests shown in blue The mines on the Italian front during the First World War comprised a series of underground explosive charges of varying sizes, secretly planted between 1916 and 1918 by Austro-Hungarian and Italian tunneling units beneath their enemy's lines along the Italian front in the Dolomite section of the Alps. Background From 1915, the high peaks of the Dolomites range were an area of fierce...

Río Coa

Coa Côa Ubicación geográficaCuenca Río DueroNacimiento Sierra de las Mesas(Sabugal)Desembocadura Duero(Vila Nova de Foz Côa)Coordenadas 40°16′29″N 6°55′28″O / 40.274822222222, -6.9244833333333Ubicación administrativaPaís PortugalRegión Beira AltaDistrito GuardaCuerpo de aguaLongitud 130 kmSuperficie de cuenca 2521 km²Mapa de localización [editar datos en Wikidata] El río Coa[1] es un río portugués que nace en Fóios, Sabugal, ...

Paul Smith (Irish writer)

This article is about the writer and playwright. For other people with the same name, see Paul Smith. Paul SmithBorn(1920-10-04)October 4, 1920Dublin, IrelandDiedJanuary 11, 1997(1997-01-11) (aged 76)Dublin, IrelandLanguagePlaywrightNationalityIrish Paul Smith (4 October 1920, Dublin, Ireland – 11 January 1997, Dublin) was an Irish writer and playwright. Biography Smith was born near Charlemont Street in Dublin, the son of a wheelwright. He became involved with the Gate Theatre at 16 y...

Cerium(III) bromide

Cerium(III) bromide Names IUPAC names Cerium(III) bromideCerium tribromide Other names Cerous bromide Identifiers CAS Number 14457-87-5 Y 3D model (JSmol) Interactive image ChemSpider 76185 Y ECHA InfoCard 100.034.936 EC Number 238-447-0 PubChem CID 292780 UNII GEM75FEL39 Y CompTox Dashboard (EPA) DTXSID60932338 InChI InChI=1S/3BrH.Ce/h3*1H;/q;;;+3/p-3 YKey: MOOUSOJAOQPDEH-UHFFFAOYSA-K YInChI=1/3BrH.Ce/h3*1H;/q;;;+3/p-3Key: MOOUSOJAOQPDEH-DFZHHIFOAB SMILES ...

نيزدين (محطة مترو أنفاق لندن)

نيزدينمعلومات عامةالتقسيم الإداري London Borough of Brent (en) البلد المملكة المتحدة شبكة المواصلات مترو لندن الخطوط Jubilee line (en) المحطات المجاورة دوليس هيل[1]على الخط: Jubilee line (en) باتجاه: Stratford tube station (en) — ويمبلي بارك[1]على الخط: Jubilee line (en) باتجاه: ستانمور الارتباطات Jubilee line (en) م�...

محمد بن محمود الآملي

محمد بن محمود الآملي معلومات شخصية الميلاد سنة 1300 آمل تاريخ الوفاة سنة 1352 (51–52 سنة) مواطنة إيران الحياة العملية المهنة رياضياتي، وشاعر، وطبيب اللغات الفارسية تعديل مصدري - تعديل محمد بن محمود الآملي (بالفارسية: محمد بن محمود آملی) طبيب وفيلسوف ...

My Bunny Lies over the Sea

1948 film by Chuck Jones My Bunny Lies over the SeaTitle card for My Bunny Lies over the SeaDirected byCharles M. JonesStory byMichael MalteseProduced byEdward SelzerStarringMel BlancMusic byCarl StallingAnimation byKen HarrisPhil MonroeBen WashamLloyd VaughanLayouts byRobert GribbroekBackgrounds byPeter AlvaradoColor processTechnicolorDistributed byWarner Bros. PicturesThe Vitaphone CorporationRelease date December 4, 1948 (1948-12-04) Running time7:29CountryUnited StatesLangu...

2018 NCAA Division I women's basketball tournament

American college basketball championship 2018 NCAA Division Iwomen's basketball tournamentSeason2017–18Teams64Finals siteNationwide ArenaColumbus, OhioChampionsNotre Dame Fighting Irish (2nd title, 6th title game,8th Final Four)Runner-upMississippi State Bulldogs (2nd title game,2nd Final Four)SemifinalistsUConn Huskies (19th Final Four)Louisville Cardinals (3rd Final Four)Winning coachMuffet McGraw (2nd title)MOPArike Ogunbowale (Notre Dame) NCAA Division I women's tournaments «20...

Sulfite

Oxyanion with a central atom of sulfur surrounded by 3 oxygen atomsNot to be confused with Sulfur trioxide. A space-filling model of the sulfite anion. Sulfites or sulphites are compounds that contain the sulfite ion (or the sulfate(IV) ion, from its correct systematic name), SO2−3. The sulfite ion is the conjugate base of bisulfite. Although its acid (sulfurous acid) is elusive,[1] its salts are widely used. Sulfites are substances that naturally occur in some foods and the human b...

Bonedriven

1997 single by BushBonedrivenSingle by Bushfrom the album Razorblade Suitcase Released16 April 1997Recorded1995–1996GenreAlternative rockLength4:32 (Album Version) 4:07 (Radio Edit)LabelTrauma/InterscopeSongwriter(s)Gavin RossdaleProducer(s)Steve AlbiniBush singles chronology Greedy Fly (1996) Bonedriven (1997) Cold Contagious (1997) Alternative coverUK CD 2 Cover Bonedriven is a song by the British rock band Bush, released on 16 April 1997. It is the third single from the band's second al...

Science Channel

Science ChannelDiluncurkan7 Oktober 1996PemilikWarner Bros. DiscoveryKantor pusatSilver Spring, Maryland, Amerika SerikatSaluran seindukTLC, Discovery Channel, Animal Planet, Discovery Health Channel, Travel Channel, Discovery Times, Discovery Kids, Discovery Home, Military Channel, Discovery Wings, Discovery Civilisation, Discovery Real Time, Discovery Travel & Living, Discovery Home and Health, Discovery en Español, Discovery HD TheaterSitus webOfficial Site Science Channel (dahulu dik...

Ledy Simarmata

Plaek Pibulsonggram

Betsy's Burglar

Penawaran Brisbane untuk Olimpiade Musim Panas 2032

Mazindol

Presiden Austria

Bentonville, Arkansas

La La Land (TV series)

SpaceX CRS-6

Operasi Insjaf

Suzanne Lalique-Haviland

الكويكب 341025