4 avril 2013

10 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • Codage et cryptographie

    le 18 avril 2013 à 19:02, par Christophe Boilley

    Mais qu’on me détrompe si « ce qui se passe dans l’algorithme » n’est pas précisément ce que j’indique (et qui n’implique pas de savoir décomposer 235 en base 2, même si c’est bien une interprétation mathématique de ce qui se passe).

    Pour le lecteur curieux de passage, on construit une suite d’exposants décroissante de 235 à 1 en divisant par 2 les exposants pairs et en retirant 1 aux exposants impairs : 235, 234, 117, 116, 58, 29, 28, 14, 7, 6, 3, 2, 1. Puis on calcule successivement les résidus des puissances correspondantes en commençant par la fin : 235, 2352, 2353 = 235×2352, 2356 = (2353)2… À chaque étape, on calcule donc un produit ou un carré, suivi d’une division euclidienne.
    (Dans le cas présent, c’est encore plus rapide parce qu’on se rend compte que 20429 est congru à 2047, mais je suppose qu’on ne peut compter sur ce genre de collision en général).

    Mais on ne peut faire croire aux lecteurs qu’en cryptographie, on calcule complètement la puissance avant de passer aux congruences : la plupart du temps, les puissances en jeu ont tellement de chiffres qu’il n’est pas matériellement possible de les représenter avec toutes les particules de l’univers.

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.