La procédure consistant à transformer une base donnée d'un réseau (un sous-groupe discret de R^n engendré par des combinaisons linéaires entières de vecteurs) en une base dont les vecteurs sont plus courts et plus proches de l'orthogonalité tout en engendrant le même réseau.

Principe

Appliquer des opérations unimodulaires préservant l'intégralité pour diminuer les longueurs et améliorer l'orthogonalité mesurée par les coefficients de Gram–Schmidt ; les algorithmes pratiques (LLL, BKZ, réduction de Minkowski) font un compromis entre qualité de réduction et coût temporel et cherchent à approcher SVP ou les minima successifs.

Démonstration

Exemple dans Z^2 : base b1 = (4,1), b2 = (1,3). Des opérations de réduction de taille et Gram–Schmidt peuvent transformer ceci en une base réduite où un vecteur est (1,3) et l'autre (3,-1) ou dans une paire plus courte et plus orthogonale ; appliquer LLL à une base 4×4 entière révèle souvent des vecteurs beaucoup plus courts facilitant les problèmes de réseau (CVP/SVP).

Mauvaise application

Supposer qu'un algorithme de réduction polynomial trouve toujours le vecteur le plus court (SVP) ou considérer toute base réduite comme unique ; utiliser Gram–Schmidt en arithmétique flottante sans contrôle peut briser l'intégralité et conduire à des conclusions fausses.

Conséquence

Une base réduite accélère généralement les algorithmes sur réseaux, fournit des vecteurs courts utiles en cryptanalyse ou pour les relations entières, et donne des approximations canoniques des minima successifs ; la qualité de la réduction influence directement la solvabilité des problèmes difficiles sur réseaux.

Inversion

La notion inverse est l'expansion de base ou la diagonalisation orthogonale qui ne préserve pas le réseau (orthonormalisation réelle) — ces opérations détruisent l'intégralité et la structure discrète, contrairement aux transformations unimodulaires qui préservent le réseau.

Limite

S'applique aux réseaux dans R^n donnés par des bases entières et des transformations unimodulaires ; exclut les groupes additifs non discrets, les modules sur d'autres anneaux que Z sauf adaptation, et les procédures qui modifient le réseau (changements non unimodulaires).

Tension sémantique

La tension vient de l'opposition entre l'orthogonalisation euclidienne (QR/Gram–Schmidt en réels) et la réduction de réseau : la première optimise l'orthogonalité mais ignore l'intégralité, la seconde préserve la structure entière au prix d'une approximation de l'orthogonalité et des vecteurs les plus courts.

Synthèse

La réduction de base de réseau est l'application contrôlée de transformations unimodulaires entières et d'opérations de réduction de taille pour produire une base du même réseau dont les vecteurs sont plus courts et plus orthogonaux au sens mesuré, en équilibrant coût computationnel et proximité aux solutions SVP/SIVP.