Démontrer qu'une fonction est bijective et définir sa réciproque



  • Bonjour amis Mathforeux.

    Oui, je sais, je n'aurais pas dû donner le titre en langue anglaise.
    Aussi j'implore les intervenants de proposer leur(s) solution(s) en français.

    Voilà le problème :
    Soit E l'ensemble des entiers naturels de 0 à 526 (0 et 526 inclus).
    Soit f l'application de E dans E définie par :
    f(x) ≡ x77x^{77} [modulo 527]
    Démontrer que f est bijective et définir sa réciproque.

    Bonne chance à tous.



  • Pour l'aspect pragmatique.

    print sorted([(x**77)%527 for x in range(527)])==sorted(range(527))

    shloub@shloub-laptop:~$ python math.py
    True



  • Peut-être, mais je ne comprends pas.
    Peux-tu traduire ?



  • range(527) c'est E.
    D'un côté je prends la liste des (x**77)%527 pour tout x de E, de l'autre E.
    Pour vérifier l'égalité des ensembles, je trie les deux listes et demande si l'égalité est vérifiée.
    La réponse est oui en une fraction de seconde.



  • En termes mathématiques, si je comprends bien, tu vérifies que f(E) = E ?
    Dans ce cas, tu prouves seulement que f est surjective.

    De plus, un programme informatique constitue à mes yeux une simple vérification, pas une démonstration mathématique : il me suffit pour cela de remplacer 527 par une lettre, par exemple n, vérifiant certaines conditions.

    Enfin, tu ne définis pas la réciproque.



  • Je pense que tu as compris l'idée.
    f(E)=E montre entre autres que j'ai 527 images différentes pour 527 valeurs différentes, il me semble que ça définit une bijection discrète.

    Informatique ou non, l'énumération est une preuve comme une autre. Je peux réaliser les même calculs à la main (ce sera -légèrement- plus long). Tu veux peut-être expliciter ces conditions pour que l'énumération naïve ne soit plus possible.

    Je peux définir la réciproque de la même manière (je ne suis pas sûr qu'elle te plaise, elle est peu compacte).

    l=sorted([((x**77)%527,x) for x in range(527)])
    for i in l:
    print "f("+str(i[0]).replace("L","")+")="+str(i[1])

    http://pastebin.com/RE08bk8V



  • Bref, pour définir la réciproque, tu lis la table "à l'envers".
    Ce n'est pas exactement ce que j'entendais par "définir".
    Citation
    Tu veux peut-être expliciter ces conditions pour que l'énumération naïve ne soit plus possible.Bon, je modifie mon énoncé :
    Soit p et q deux entiers premiers impairs, et soit n = p.q.
    Soit u un inversible de Z/φ(n)Z .
    Soit f de Z/nZ dans lui-même, définie par f(x) = xux^u
    Démontrer que f est bijective et définir sa réciproque .
    Tu as reconnu un codage RSA, (d'où le titre), mais il y a un petit piège.



  • J'ai en effet du mal à voir le piège.



  • Le codage est basé sur le théorème de Fermat-Euler, qui impose que x soit premier avec n.
    f définit donc une bijection de (Z/nZ)* sur lui-même.
    Il faut démontrer que c'est quand même une bijection de Z/nZ sur lui-même.



  • On traite ce cas particulier à l'aide du théorème des restes chinois si je me souviens bien.



  • (Pardon pour le double-post.)



  • Citation
    On traite ce cas particulier à l'aide du théorème des restes chinois si je me souviens bien.Je ne vois pas bien comment : peux-tu détailler ?



  • Je t'avoue que je n'ai pas envie de détailler énomément, mais je crois que l'on montre n=0 mod pq <=> n=0 mod p et n=0 mod q.
    Un sens est plus facile que l'autre, cela dit je crois que c'est assez direct avec l'isomorphisme Z/pqZ -> à (Z/pZ)*(Z/qZ) exhibé par ce fameux théorème.



  • Puisque n = p.q, on a évidemment n ≡ 0 modulo pq (ou modulo n)
    De plus, n étant multiple de p, on a n ≡ 0 modulo p (pareil pour q).
    Je ne vois pas bien ce que tu souhaites établir avec le théorème chinois.
    J'espère que la notation (Z/nZ)* ne t'abuses pas :
    il ne s'agit pas de Z/nZ {0} mais de l'ensemble des inversibles de Z/nZ.
    Ainsi, Z* = {+1 ; -1}



  • Pardon, la lettre n était mal choisie, je crois qu'il s'agit plutôt de ton x en l'occurrence.



  • Ah. Mais pas besoin du théorème chinois.
    si x n'est pas premier avec n, c'est soit un multiple de p, soit un multiple de q. Donc congru à 0 modulo p ou q.
    Excuses-moi, mais pour le moment tu n'as rien démontré.
    Peut-être pourrais-tu commencer par définir ce que pourrait être la réciproque de f ?



  • x -> x^(u⁻¹ mod (p-1)(q-1)) mod n ?



  • Exact.
    Mais cela n'est valable que si x est premier avec n.
    Tu dois donc établir le résultat lorsque x n'est pas premier avec n.
    En d'autres terme, si tu notes v l'inverse de u modulo (p-1)(q-1), tu dois démontrer que xuvx^{uv} ≡ x modulo n , même dans ce cas.



  • Comme dit précédemment, si x n'est pas premier avec n, il est multiple de p ou q.
    Par le théorème des restes chinois on peut vérifier la congruence en n par celle en p et celle en q. L'une des deux est évidente (les deux côtés sont multiples de p (ou q)). Pour l'autre on peut décomposer la puissance et obtenir le résultat de manière similaire à la démonstration via le théorème de Fermat.



  • Je ne vois pas.
    Le théorème chinois établit l'isomorphisme entre le groupe multiplicatif (Z/nZ)* et (Z/pZ)× (Z/qZ)
    Mais quel rapport avec la question posée où le but est précisément de se débarrasser des étoiles ?



  • Démontrer a = c mod(pq) revient à démontrer a=c mod(p) et a=c mod(q), je pense que c'est là l'intérêt de ce théorème.



  • Ce que tu dis est vrai, mais excuse mon ignorance, je ne vois pas le rapport avec la question posée :
    "si tu notes v l'inverse de u modulo (p-1)(q-1), tu dois démontrer que xuvx^{uv} ≡ x modulo n , même lorsque x n'est pas premier avec n."



  • « démontrer que xuv ≡ x modulo n» est décomposable par ce moyen.



  • Peux-tu détailler ?
    Je t'en serai reconnaissant.
    P.S : faute de frappe : c'est évidemment xuvx^{uv} et pas xuv



  • Démontrer a = c mod(pq) revient à démontrer a=c mod(p) et a=c mod(q), je pense que c'est là l'intérêt de ce théorème.

    a vaut x^(uv), c vaut x et n vaut pq donc on a
    « démontrer que x^(uv) ≡ x modulo n» revient à démontrer que x^(uv) ≡ x modulo p et x^(uv) ≡ x modulo q, non ?



  • Exact, et comment démontrer que xuvx^{uv} ≡ 0 modulo p ?



  • Je dois avouer ne plus me souvenir cette partie.



  • Ce n'est pas urgent puisqu'il s'agit d'une énigme (dont je connais la réponse).
    Toutefois, il est intéressant de réussir cette partie du problème, car c'est précisément là qu'est l'os hélas.
    Tant que x est premier avec n, le résultat découle immédiatement du théorème de Fermat-Euler.
    Mais il faut réussir à répondre à la question dans le cas où x n'est pas premier avec n, sinon adieu la bijection.



  • p étant premier, tout x est soit premier avec p soit multiple de p ?



  • Oui.


 

Encore plus de réponses par ici

Il semble que votre connexion ait été perdue, veuillez patienter pendant que nous vous re-connectons.