Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau autre
Arithmétique(Cryptographie)
Posté par robby3
Bonsoir tout le monde,j'aurais besoin de votre aide sur un exercice d'arithmétique...
Citation :
On suppose que
est un nombre premier impair tel que =1)
a)Supposons que
et que ![b^2\eq a[p^{i-1}]](https://latex.ilemaths.net/ile_tex.cgi?b^2\eq a[p^{i-1}])
Montrer qu'il existe un unique
tel que ![x^2\eq a[p^{i}]](https://latex.ilemaths.net/ile_tex.cgi?x^2\eq a[p^{i}])
et ![x\eq b[p^{i-1}]](https://latex.ilemaths.net/ile_tex.cgi?x\eq b[p^{i-1}])
Décrire comment ce
peut-etre calculé.
b)Utiliser la méthode proposée pour calculer les racines carrés de
modulo 
et modulo 
à partir de l'équation ![6^2\eq 17[19]](https://latex.ilemaths.net/ile_tex.cgi?6^2\eq 17[19])
c)pour tout
,montrer que le nombre de solutions de l'équation ![x^2\eq a[p^i]](https://latex.ilemaths.net/ile_tex.cgi?x^2\eq a[p^i])
est soit 0 soit 2.
On suppose que
a)Supposons que
Montrer qu'il existe un unique
Décrire comment ce
b)Utiliser la méthode proposée pour calculer les racines carrés de
c)pour tout
j'attend vos propositions,je n'ai pas réussi à commencer!
Salut robby, 
Il y a un truc qui me gêne dans ton énoncé... On passe de congruences modulo p^(i-1) à F_(p^i) et manifestement pour le type, il est équivalent de dire que "a est un carré dans F_(p^i)" et "x²=a [p^i]"... c'est franchement gênant car F_(p^i) n'est pas un "corps de nombres" (ie, F_(p^i) on peut pas le confondre impunément avec Z/p^iZ)...
Sois j'ai rien compris (ce qui ne m'étonnerai que très peu) sois il y a une grosse ambugüité dans ton énoncé. T'es sur de lui?
Salut Schumi,j'ai pas bien compris ce que tu comprenais pas,mais quand j'écris
c'est
sinon le reste j'ai vérifier,c'est bien ça!
Ah d'accord, je prefère ça.
F_(p^i) n'a rien à voir (ou presque) avec Z/p^iZ. L'un est un corps l'autre pas.
J'y réfléchis.
Citation :
Je vous laisse travailler
Je vous laisse travailler
>Ah bah non!
maintenant que t'es là aide nous!
Bon Dimanche Kévin!
Citation :
Oui romu, mais pour i différent de 1 c'est faux.
Oui romu, mais pour i différent de 1 c'est faux.
J'ai rien dit moi
Je viens à peine de me réveiller
salut à tous
Héhé, je crois avoir trouvé:
b²=a (p^i).
Alors il existe un entier k tel que a=b²+kp^(i-1).
On remarque que b est forcément inversible dans Z/p^iZ.
On pose alors: x = b - k/(2b)p^(i-1) (ça a bien un sens dans Z/p^iZ). Je crois bien qu'il fonctionne celui-là.
Parce que a est premier avec p, donc b² aussi et par suite b. (enfin, dans les grandes lignes, ça se tient).
Sinon, je pose x = b + k/(2b)p^(i-1) (dans Z/p^iZ).
Pourquoi?
Tu me mets un énorme doute là.
Je détaille donc:
Bon déjà, on remarque facilement que modulo p^(i-1) on a bien x=b. revient à la définition si tu veux.
x = b+ k/(2b)p^(i-1) dans Z/p^iZ.
On met au carré: x²= b²+ kp^(i-1)+ (k/(2b)p^(i-1))² (ce dernier terme étant bien évidemment nul). D'où x²= a non?
Franchement, tu m'as mis un de ces doutes là...
Ben le 1er pourquoi?
Je crois qu'on est dans un vrai dialogue de sourd depuis quelques messages... Je suis vraiment désolé du désordre que j'ai pu mettre dans ce topic.
non non c'est bon!
donc on est d'accord!
faut montrer qu'il est unique et comment on peut facilement le calculer...
pour l'unicité,on en prend un autre et on montre qu'ils sont égaux(ok)
il faut donc décrire comment ce x peut-etre calculer.
une idée Schumi?
On remarque que dans Z/p^iZ il a p éléments x tel que x=b dans Z/p^iZ (je l'ai pas réellement prouvé mais il me semble que c'est vrai).
Reste à prouver que parmi ces p éléments, il n'y en a qu'un qui convient.
Pour cela, je prendrai mon "x" défini dans les posts précédants. Il suffirait de prouver que parmi les translatés: x+j*p^(i-1) (où j est dans [|0,p-1|] il n'y que pour j=0 que x²=a dans p^i.
Ceci nous donne donc l'algorithme souvhaité pour trouver ledit "x".
On suppose connu b.
Si b convient aussi dans Z/p^iZ alors on s'arrête.
Si b ne convient pas, on essaie avec b+p^(i-1). S'il convient, on s'arrête.
Si b+p^(i-1) ne convient pas, on essaie avec b+2p^(i-1).
Et ainsi de suite.
On est sur de s'arrêter à un moment (précisemment, en au plus p étapes).
On a donc bien un algorithme.
A vérifier, mais ça devrait être bon.
Je t'en prie. (T'as vérifié? C'est bon?).
Pour la 2), je te laisse faire et pour la 3), j'y réfléchis c'te aprèm. Je te tiens au courant.
Bon, en fait ça a pas l'air si méchant que ça la 3).
Déjà, on commence par régler le cas où a=1.
Je te laisse vérifier dans Z/p^i Z l'équation x²=1 n'admet que 2 solutions: 1 et -1. (Attention quand même, c'est pas aussi triviale que ça en a l'air).
Cas général:
Supposons que l'équation admet au moins une solution. On l'appelle x_0.
On doit alors résoudre: x²=x_0² dans Z/p^i Z. Comme x_0 est inversible (puisque a l'est), il vient qu'on a (x/x_0)²=1 dans Z/p^iZ.
D'après le cas précédent, les solutions sont au nombre de 2: x_0 et -x_0.