Question de mathsMathsRaisonnement et algorithmes

Comment un ordinateur calcule-t-il une très grande puissance en peu d'opérations ?

En élevant au carré plutôt qu'en multipliant pas à pas, on calcule 3¹³ en 5 multiplications au lieu de 12, et xⁿ en environ 2 log₂ n : un invariant démontre que l'algorithme est juste.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 10 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En cryptographie, j'ai lu que les ordinateurs calculent des puissances avec des exposants de plusieurs centaines de chiffres. Multiplier un nombre par lui-même autant de fois prendrait plus de temps que l'âge de l'Univers. Pourtant mon téléphone le fait en un instant. J'ai découvert l'exponentiation rapide, qui repose sur une idée simple : élever au carré, et j'ai voulu prouver qu'elle donne le bon résultat.

L'enjeu et les notions du programme

Concevoir un algorithme efficace, démontrer sa correction par un invariant (récurrence) et mesurer son coût avec le logarithme.

Mathématiques

Propriétés des puissances : $x^{2 k} = (x^{k})^{2}$ x^(2k)=(x^(k))² (collège, seconde)
Algorithmique : boucle while, division euclidienne par 2 en Python (seconde, première)
Raisonnement par récurrence (terminale)
Logarithme : nombre de chiffres binaires de $n$ n (terminale)

Le plan de l'exposé en 10 min

1. Introduction : la méthode naïve
1,5 min
Calculer $x^{n}$ xⁿ en multipliant $x$ x par lui-même demande $n - 1$ n-1 multiplications : 12 pour $3^{13}$ 3¹³, presque un million pour $x^{1000000}$ x^(1 000 000). Problématique : peut-on faire beaucoup mieux, et comment être sûr que le résultat est juste ?
2. L'idée : élever au carré
3 min
$x^{2} = x \times x$ x²=x× x, $x^{4} = (x^{2})^{2}$ x⁴=(x²)², $x^{8} = (x^{4})^{2}$ x⁸=(x⁴)² : trois multiplications donnent $x^{8}$ x⁸. Comme $13 = 8 + 4 + 1$ 13=8+4+1 ( $1101$ 1101 en binaire), $3^{13} = 3^{8} \times 3^{4} \times 3$ 3¹³=3⁸×3⁴×3 : 3 carrés et 2 produits, soit 5 multiplications au lieu de 12.
Règle récursive : $x^{n} = (x^{n /2})^{2}$ xⁿ=(x^(n/2))² si $n$ n est pair, $x^{n} = x \times (x^{(n - 1) /2})^{2}$ xⁿ=x×(x^((n-1)/2))² si $n$ n est impair.
3. L'algorithme et sa preuve
4 min
On part de $r = 1$ r=1, $b = x$ b=x, $e = n$ e=n. Tant que $e > 0$ e>0 : si $e$ e est impair, $r \leftarrow r \times b$ r← r× b ; puis $b \leftarrow b^{2}$ b← b² et $e \leftarrow ⌊ \frac{e}{2} ⌋$ e←lfloore/2rfloor. On renvoie $r$ r.
Trace pour $3^{13}$ 3¹³ : $(r, b, e) = (1, 3, 13) \to (3, 9, 6) \to (3, 81, 3) \to (243, 6561, 1) \to (1594323, \dots, 0)$ (r,b,e)=(1,3,13)→(3,9,6)→(3,81,3)→(243,6 561,1)→(1 594 323,…,0). Et $3^{13} = 1594323$ 3¹³=1 594 323.
Invariant : $r \times b^{e} = x^{n}$ r× bᵉ=xⁿ à chaque tour. Vrai au départ ( $1 \times x^{n}$ 1× xⁿ). Si $e = 2 k$ e=2k : $r \times (b^{2})^{k} = r \times b^{2 k}$ r×(b²)^(k)=r× b^(2k). Si $e = 2 k + 1$ e=2k+1 : $(r b) \times (b^{2})^{k} = r \times b^{2 k + 1}$ (rb)×(b²)^(k)=r× b^(2k+1). À la fin, $e = 0$ e=0, donc $r = x^{n}$ r=xⁿ. Le nombre de tours est le nombre de chiffres binaires de $n$ n, environ $lo g_{2} n$ log₂ n : au plus $2 lo g_{2} n$ 2log₂ n multiplications, une quarantaine pour $n = 1 0^{6}$ n=10⁶.
4. Conclusion
1,5 min
L'ordinateur calcule $x^{n}$ xⁿ en environ $2 lo g_{2} n$ 2log₂ n multiplications grâce aux carrés successifs, et l'invariant $r \times b^{e} = x^{n}$ r× bᵉ=xⁿ prouve que le résultat est exact. J'ouvre sur le chiffrement RSA, qui calcule des puissances modulo un grand nombre : sans cet algorithme, il serait inutilisable.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

x^{n} = {(x^{n /2})^{2} x (x^{(n - 1) /2})^{2} n pair n impair 13 = (1101)_{2} = 8 + 4 + 1 xⁿ= (x^(n/2))² n pair ; x (x^((n-1)/2))² n impair 13=(1101)₂=8+4+1 (r, b, e) : (1, 3, 13) \to (3, 9, 6) \to (3, 81, 3) \to (243, 6561, 1) \to (1594323, \cdot, 0) (r,b,e): (1,3,13)\to(3,9,6)\to(3,81,3)\to(243,6 561,1)\to(1 594 323,\cdot,0) invariant : r \times b^{e} = x^{n} invariant : r\times bᵉ=xⁿ

Conclusion : la réponse à la question

En élevant au carré et en lisant l'exposant en binaire, on calcule $x^{n}$ xⁿ en un nombre d'opérations de l'ordre de $lo g_{2} n$ log₂ n au lieu de $n$ n. L'invariant, démontré comme une récurrence, garantit le résultat.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Combien de multiplications pour x¹⁶ ?

Quatre carrés : $x^{2}, x^{4}, x^{8}, x^{16}$ x²,x⁴,x⁸,x¹⁶, contre 15 multiplications naïves.

Pourquoi l'algorithme s'arrête-t-il ?

$e$ e est un entier naturel qui diminue strictement ( $⌊ e /2 ⌋ < e$ lfloor e/2rfloor<e pour $e \geq 1$ e≥1).

Combien de chiffres binaires a un entier n ?

$k$ k chiffres si $2^{k - 1} \leq n < 2^{k}$ 2^(k-1)≤ n<2^(k), soit $k = ⌊ lo g_{2} n ⌋ + 1$ k=lfloorlog₂ nrfloor+1.

Est-ce le nombre minimal de multiplications ?

Pas toujours : $x^{15}$ x¹⁵ demande 6 multiplications par cette méthode, mais 5 suffisent ( $x^{2}, x^{3}, x^{6}, x^{12}, x^{15}$ x²,x³,x⁶,x¹²,x¹⁵). L'algorithme est rapide sans être optimal.

Écrivez le test « e est impair » en Python.

e % 2 == 1, et la division entière s'écrit e // 2.

Combien de multiplications naïves et rapides pour x¹⁰⁰⁰ ?

Naïvement 999. En binaire, $1000 = (1111101000)_{2}$ 1 000=(1111101000)₂ a 10 chiffres dont 6 égaux à 1 : 9 carrés et 5 produits, soit 14 multiplications (le premier produit, $1 \times b$ 1× b, ne compte pas).

Quel lien avec le raisonnement par récurrence ?

L'invariant se prouve exactement comme une hérédité : vrai avant un tour, il reste vrai après ; l'initialisation est l'état de départ.

Les pièges qui coûtent des points

Écrire $x^{a + b} = x^{a} + x^{b}$ x^(a+b)=x^(a)+x^(b).
Oublier de multiplier r quand l'exposant est impair.
Prouver l'algorithme sur un exemple seulement.

Revoir les notions

Autres questions : raisonnement et algorithmes

Toutes les questions de maths →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-NSI →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →