Logarithme discret

L'objet de cet exercice est, connaissant les nombres b et n, de calculer le nombre x qui vérifie :

3x ≡ b [n]

Une autre façon de présenter le problème est de dire que l'on cherche à trouver le nombre entier x tel que, si on multiplie 3 avec lui même x fois, le reste de la division entière de ce résultat par n vaudra b.

Le seul algorithme général simple pour résoudre ce problème est d'essayer successivement les différentes valeurs de x jusqu'à en trouver une qui convient.

Par exemple, si n=23 et b=13, la solution de 3x≡13 [23] est x=5, car le reste de la division de 35=243 par 23 vaut 13. De plus, 5 est le plus petit nombre qui convient car 31≡3[23], 32≡9[23], 33≡4[23], et 34≡12[23].

Défi :

Pour cet exercice, vous avez plusieurs équations du type : 3xi≡bi [223]

Les valeurs des bi sont données en entrée et vous devez répondre en donnant la séquence des xi correspondant.

Testez votre code :

Si l'entrée du problème est : (4,6,8), alors une réponse possible est (138,181,96).

En effet :

  • le reste de la division entière (opération modulo) de 3138 par 223 vaut 4
  • le reste de la divison entière de 3181 par 223 vaut 6
  • et le reste de la divison entière de 396 par 223 vaut 8

Ce problème est tiré de c0d1ng UP 2014

Type de retour

une séquence de nombres entiers

Entrée du problème

(28, 134, 36, 101, 39, 42, 57, 75, 192, 41)

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup14 arithmétique numérique