Trouver x

[Anonyme]

Bonjour a tous
j'ecris sur ce forum car c'est celui qui me semble le plus adapté ...

voici mon probleme (niveau terminale S, mais le principe est de trouver la
solution !!)

alors le probleme vient du fait que dans l'atelier de maths dans lequel je
suis, on fait des "maths sup"...
aujourd'hui, on a fait un peu de cryptographie

mais le reel sujet, ...
trouver x (entier !!! qui plus est !)

donc l'equation c'est
11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
modulo193 707 721 )

je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x entier

si vous avez des astuces pour resoudre cela, je suis preneur

merci !!!!!
christophe

[Anonyme]

On Fri, 30 Jan 2004 18:32:48 +0100, rito wrote:

> donc l'equation c'est
> 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
> modulo193 707 721 )

nicolas@onesicrite:~$ factor 193707721
193707721: 193707721

Ce nombre est premier.

Puisque 11^x se termine par 1 et que 25 se termine par 5, ton égalité
peut s'écrire :
11^x=25+k×193707721 avec k se terminant par 6

> je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x entier

x=ton bidule si tu bosses dans les réels et si tu veux mon k=0, or tu
bosses dans Z/193707721Z, ce qui est un peu différent.

nicolas patrois : pts noir asocial
--
GLOU-GLOU

P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
M : Panique pas... La mer est pleine de microbes, mais tellement dilués qu'ils sont inoffensifs...
P : C'est ça... La mer, c'est de la merde homéopathique !

[Anonyme]

donc la reponse est ??
parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!


"nicolas" a écrit dans le message news:
pan.2004.01.30.19.12.01.770000@online.fr...
> On Fri, 30 Jan 2004 18:32:48 +0100, rito wrote:
>[color=green]
> > donc l'equation c'est
> > 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
> > modulo193 707 721 )
>
> nicolas@onesicrite:~$ factor 193707721
> 193707721: 193707721
>
> Ce nombre est premier.
>
> Puisque 11^x se termine par 1 et que 25 se termine par 5, ton égalité
> peut s'écrire :
> 11^x=25+k×193707721 avec k se terminant par 6
>
> > je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x entier
>
> x=ton bidule si tu bosses dans les réels et si tu veux mon k=0, or tu
> bosses dans Z/193707721Z, ce qui est un peu différent.
>
> nicolas patrois : pts noir asocial
> --
> GLOU-GLOU
>
> P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
> M : Panique pas... La mer est pleine de microbes, mais tellement dilués[/color]
qu'ils sont inoffensifs...
> P : C'est ça... La mer, c'est de la merde homéopathique !
>
>

[Anonyme]

salut rito,

je pense que tu pourrais essayer d'utiliser le fait que 11^x = (10+1)^x =
Sum( Cn,k * 10^k ) ainsi tu "connais" tous les unités, les dizaines, les
centaines etc de 11^x. Ainsi il doit etre plus simple de trouver le "k" dont
nicolas parle.

++
Gilles

"rito" a écrit dans le message de
news:bvehvg$5c8$1@news-reader2.wanadoo.fr...
> donc la reponse est ??
> parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!
>
>
> "nicolas" a écrit dans le message news:
> pan.2004.01.30.19.12.01.770000@online.fr...[color=green]
> > On Fri, 30 Jan 2004 18:32:48 +0100, rito wrote:
> >[color=darkred]
> > > donc l'equation c'est
> > > 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
> > > modulo193 707 721 )
> >
> > nicolas@onesicrite:~$ factor 193707721
> > 193707721: 193707721
> >
> > Ce nombre est premier.
> >
> > Puisque 11^x se termine par 1 et que 25 se termine par 5, ton égalité
> > peut s'écrire :
> > 11^x=25+k×193707721 avec k se terminant par 6
> >
> > > je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x entier
> >
> > x=ton bidule si tu bosses dans les réels et si tu veux mon k=0, or tu
> > bosses dans Z/193707721Z, ce qui est un peu différent.
> >
> > nicolas patrois : pts noir asocial
> > --
> > GLOU-GLOU
> >
> > P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
> > M : Panique pas... La mer est pleine de microbes, mais tellement dilués[/color]
> qu'ils sont inoffensifs...
> > P : C'est ça... La mer, c'est de la merde homéopathique !
> >
> >
>
>[/color]

[Anonyme]

On Fri, 30 Jan 2004 22:27:51 +0100, rito wrote:

> donc la reponse est ??
> parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!

Je n'en sais rien, je ne vais pas résoudre l'exercice à ta place.

nicolas patrois : pts noir asocial
--
GLOU-GLOU

P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
M : Panique pas... La mer est pleine de microbes, mais tellement dilués qu'ils sont inoffensifs...
P : C'est ça... La mer, c'est de la merde homéopathique !

[Anonyme]

ptet une piste
11^7 = 11 (7) (petit théorème de fermat)
11^7 = 25 (7)

[Anonyme]

rito wrote:
> Bonjour a tous
> j'ecris sur ce forum car c'est celui qui me semble le plus adapté ...
>
> voici mon probleme (niveau terminale S, mais le principe est de trouver la
> solution !!)
>
> alors le probleme vient du fait que dans l'atelier de maths dans lequel je
> suis, on fait des "maths sup"...
> aujourd'hui, on a fait un peu de cryptographie
>
> mais le reel sujet, ...
> trouver x (entier !!! qui plus est !)
>
> donc l'equation c'est
> 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
> modulo193 707 721 )

Au pire on a x < 193 707 721
Je ne pense pas que ce problème puisse être résolu littéralement
puisque c'est l'un des problèmes majeurs de cryptographie (avec
la factorisation en nombres premiers).
Qu'en pensent les experts en corps de galois ?

Anh Vu

[Anonyme]

On Fri, 30 Jan 2004 22:27:51 +0100, rito wrote:

> donc la reponse est ??
> parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!

Tu devrais te faire un petit programme qui teste chaque valeur de x entre
1 et 193707720 en calculant des restes.

nicolas patrois : pts noir asocial
--
GLOU-GLOU

P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
M : Panique pas... La mer est pleine de microbes, mais tellement dilués qu'ils sont inoffensifs...
P : C'est ça... La mer, c'est de la merde homéopathique !

[Anonyme]

le porbleme, c'ets que je ne suis " qu'en " Terminale S ...

je ne comprends donc pas tout ...
(je ne fais meme pas spé maths pour vous dire ...)

cette question n'ets nullement un exercice.
juste une question de connaissance personnelle ...

nicolas a parle d'un programme je cite
"Tu devrais te faire un petit programme qui teste chaque valeur de x entre 1
et 193707720 en calculant des restes."
euh .. je fais comment ca ?

j'ai acces a mapple ceci dit !

merci de m'éclairer

christophe

"Gilles Soulier" a écrit dans le message news:
bvfa1l$dl4$1@bisounours.iiens.net...
> salut rito,
>
> je pense que tu pourrais essayer d'utiliser le fait que 11^x = (10+1)^x =
> Sum( Cn,k * 10^k ) ainsi tu "connais" tous les unités, les dizaines, les
> centaines etc de 11^x. Ainsi il doit etre plus simple de trouver le "k"
dont
> nicolas parle.
>
> ++
> Gilles
>
> "rito" a écrit dans le message de
> news:bvehvg$5c8$1@news-reader2.wanadoo.fr...[color=green]
> > donc la reponse est ??
> > parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!
> >
> >
> > "nicolas" a écrit dans le message news:
> > pan.2004.01.30.19.12.01.770000@online.fr...[color=darkred]
> > > On Fri, 30 Jan 2004 18:32:48 +0100, rito wrote:
> > >
> > > > donc l'equation c'est
> > > > 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier = 25
> > > > modulo193 707 721 )
> > >
> > > nicolas@onesicrite:~$ factor 193707721
> > > 193707721: 193707721
> > >
> > > Ce nombre est premier.
> > >
> > > Puisque 11^x se termine par 1 et que 25 se termine par 5, ton égalité
> > > peut s'écrire :
> > > 11^x=25+k×193707721 avec k se terminant par 6
> > >
> > > > je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x[/color][/color]
entier[color=green][color=darkred]
> > >
> > > x=ton bidule si tu bosses dans les réels et si tu veux mon k=0, or tu
> > > bosses dans Z/193707721Z, ce qui est un peu différent.
> > >
> > > nicolas patrois : pts noir asocial
> > > --
> > > GLOU-GLOU
> > >
> > > P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
> > > M : Panique pas... La mer est pleine de microbes, mais tellement[/color][/color]
dilués[color=green]
> > qu'ils sont inoffensifs...[color=darkred]
> > > P : C'est ça... La mer, c'est de la merde homéopathique !
> > >
> > >
> >
> >[/color]
>
>[/color]

[Anonyme]

"rito" a écrit

> j'ai acces a mapple ceci dit !
>

Dans ce cas :
msolve(11^x=25, 193707720);
devrait faire ton bonheur.

Cordialement
Stéphane

[Anonyme]

A vrai dire, j'ai juste appliqué la formule du binome de newton qui me
semble-t-il est au programme du bac.
(a+b)^n=Sum(C(n,k)*a^k*b^(n-k),k,1..n) [je reconnais que ce
n'est pas tres propre ecrit comme ca]

Concernant Maple, c'est bien de savoir resoudre une equation avec, ou de lui
faire faire une boucle pour tester des egalites.
Cependant, de tels exercices avec des modulos abracadabrantesque sont
destines a "t'empecher de faire des tests" en t'incitant a reflechir un peu.
A moins qu'on veuille que tu te serves de Maple, je pense que la resolution
peu se faire autrement.
A toi de jouer!

++

"rito" a écrit dans le message de
news:bvg465$h8i$1@news-reader3.wanadoo.fr...
> le porbleme, c'ets que je ne suis " qu'en " Terminale S ...
>
> je ne comprends donc pas tout ...
> (je ne fais meme pas spé maths pour vous dire ...)
>
> cette question n'ets nullement un exercice.
> juste une question de connaissance personnelle ...
>
> nicolas a parle d'un programme je cite
> "Tu devrais te faire un petit programme qui teste chaque valeur de x entre
1
> et 193707720 en calculant des restes."
> euh .. je fais comment ca ?
>
> j'ai acces a mapple ceci dit !
>
> merci de m'éclairer
>
> christophe
>
> "Gilles Soulier" a écrit dans le message
news:
> bvfa1l$dl4$1@bisounours.iiens.net...[color=green]
> > salut rito,
> >
> > je pense que tu pourrais essayer d'utiliser le fait que 11^x = (10+1)^x[/color]
=[color=green]
> > Sum( Cn,k * 10^k ) ainsi tu "connais" tous les unités, les dizaines, les
> > centaines etc de 11^x. Ainsi il doit etre plus simple de trouver le "k"
> dont
> > nicolas parle.
> >
> > ++
> > Gilles
> >
> > "rito" a écrit dans le message de
> > news:bvehvg$5c8$1@news-reader2.wanadoo.fr...[color=darkred]
> > > donc la reponse est ??
> > > parce que pour le moment, k'en conclus qu'il n'y a pas de solution !!
> > >
> > >
> > > "nicolas" a écrit dans le message news:
> > > pan.2004.01.30.19.12.01.770000@online.fr...
> > > > On Fri, 30 Jan 2004 18:32:48 +0100, rito wrote:
> > > >
> > > > > donc l'equation c'est
> > > > > 11 ^x =25 (193 707 721) (en litteral 11 puissance x, x entier =[/color][/color]
25[color=green][color=darkred]
> > > > > modulo193 707 721 )
> > > >
> > > > nicolas@onesicrite:~$ factor 193707721
> > > > 193707721: 193707721
> > > >
> > > > Ce nombre est premier.
> > > >
> > > > Puisque 11^x se termine par 1 et que 25 se termine par 5, ton[/color][/color]
égalité[color=green][color=darkred]
> > > > peut s'écrire :
> > > > 11^x=25+k×193707721 avec k se terminant par 6
> > > >
> > > > > je sais que x= ln25/ln11 = env 1.3423.... ... mais il faut x[/color]
> entier[color=darkred]
> > > >
> > > > x=ton bidule si tu bosses dans les réels et si tu veux mon k=0, or[/color][/color]
tu[color=green][color=darkred]
> > > > bosses dans Z/193707721Z, ce qui est un peu différent.
> > > >
> > > > nicolas patrois : pts noir asocial
> > > > --
> > > > GLOU-GLOU
> > > >
> > > > P : Ouerk ! C'est dégueulasse, j'ai bu la tasse !
> > > > M : Panique pas... La mer est pleine de microbes, mais tellement[/color]
> dilués[color=darkred]
> > > qu'ils sont inoffensifs...
> > > > P : C'est ça... La mer, c'est de la merde homéopathique !
> > > >
> > > >
> > >
> > >
> >
> >[/color]
>
>[/color]

[Anonyme]

"rito" wrote:

>le porbleme, c'ets que je ne suis " qu'en " Terminale S ...
>
>je ne comprends donc pas tout ...
>(je ne fais meme pas spé maths pour vous dire ...)
>
>cette question n'ets nullement un exercice.
>juste une question de connaissance personnelle ...
>

Il me semblait bien aussi, car ce genre de problème s'appelle le
problème du logarithme discret, et ca peut être exttrêmement difficile
à résoudre. Il faut etre sadique pour donner un exercice comme ca.

Il y a des algorithmes plus ou moins compliqués pour le résoudre, dans
ton exemple Maple prend 1 seconde pour trouver x=7130984, alors c'est
assez rapide probablement parce que 193707721 est premier.
Voir la page suivante pour des algos:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/ctcdlp.html

>nicolas a parle d'un programme je cite
>"Tu devrais te faire un petit programme qui teste chaque valeur de x entre 1
>et 193707720 en calculant des restes."
>euh .. je fais comment ca ?

Non faudrait pas faire ca, c'est trop long....
Par exemple en Maple:

for x from 1 to 193707721 do
if (11 &^ x mod 193707721=25) then break end if
end do;

est très très long sur mon pc en tout cas.

[Anonyme]

"Gilles" a écrit dans le message news:
bvgbha$6um$1@bisounours.iiens.net...
> A vrai dire, j'ai juste appliqué la formule du binome de newton qui me
> semble-t-il est au programme du bac.
> (a+b)^n=Sum(C(n,k)*a^k*b^(n-k),k,1..n) [je reconnais que
ce
> n'est pas tres propre ecrit comme ca]
>
> Concernant Maple, c'est bien de savoir resoudre une equation avec, ou de
lui
> faire faire une boucle pour tester des egalites.
> Cependant, de tels exercices avec des modulos abracadabrantesque sont
> destines a "t'empecher de faire des tests" en t'incitant a reflechir un
peu.
> A moins qu'on veuille que tu te serves de Maple, je pense que la
resolution
> peu se faire autrement.


le prof d'atelier maths m'a mis au defi de trouver le resultat ....
j'ai possibilité de me servir de mapple ... et de me demerder comme je peux
....

[Anonyme]

[color=green]
> >le porbleme, c'ets que je ne suis " qu'en " Terminale S ...
> >
> >je ne comprends donc pas tout ...
> >(je ne fais meme pas spé maths pour vous dire ...)
> >
> >cette question n'ets nullement un exercice.
> >juste une question de connaissance personnelle ...
> >
>
> Il me semblait bien aussi, car ce genre de problème s'appelle le
> problème du logarithme discret, et ca peut être exttrêmement difficile
> à résoudre
>[/color]

c'est tout a fait le but... le logarithme discret, c'est la base de la
cryptographie !