Discussion:Algorithme de Freivalds
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Composantes du vecteur de test
modifierPourquoi les composantes du vecteur de test seraient nécessairement 0 ou 1 ?
Certes, cela simplifie le calcul des produits matrices-vecteurs — on évite les multiplications, on ne fait que sélectionner les index des composantes des vecteurs lignes de notre matrice à additionner.
Cependant, est-ce qu'on ne gagnerait pas à choisir d'autres nombres ? Dans un anneau fini Z/nZ, on a ainsi le choix entre n composantes (de 0 à n-1).
En restreignant les entrées à $M_n(Z/2Z)$, on restreint également l'image de l'application qui à $x$ associe $A\cdot (Bx)$. Cela ne devrait pas changer la fiabilité du test et réduit à priori les performances, mais on devrait mentionner le choix de 0 ou 1 dans l'algorithme ? Cilisso (discuter) 12 octobre 2022 à 12:38 (CEST)