Congruences

par **Mario2015** » 05 Jan 2015, 16:09

@chan79
Merci.
C`est bien beau quand n fait 4-5 chiffres imagine un n de 500 chiffres, tu fais comment?
Avec n premier, des algos resolvent cela (meme 1000 chiffres) mais avec un n composite pas moyen.
http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

J`abandonne pour l`instant, le temps de trouver des raccourcis ou des trucs de matheux. Reformuler le probleme.

par **chan79** » 05 Jan 2015, 16:31

Mario2015 a écrit:@chan79
Merci.
C`est bien beau quand n fait 4-5 chiffres imagine un n de 500 chiffres, tu fais comment?
Avec n premier, des algos resolvent cela (meme 1000 chiffres) mais avec un n composite pas moyen.
http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

J`abandonne pour l`instant, le temps de trouver des raccourcis ou des trucs de matheux. Reformuler le probleme.

C'était juste un commentaire, comme tu le demandais au début de ce post.
Ca me parait difficile d'expliciter simplement les solutions, s'il y en a, surtout avec des paramètres.

par **Mario2015** » 05 Jan 2015, 16:43

On peut faire une hypothese restrictive qui ne marche pas pour tous les cas :
- donner une valeur a z(z+1). C`est un parametre que l`on peut estimer de maniere probabilistique. Pour certains n cela peut-etre z(z+1)= 0 ou 2 ou 6 ou 12 etc...
Mais meme dans pareil cas la difficulte reste.

par **Mario2015** » 05 Jan 2015, 16:48

On ne sait pas d`avance si telle valeur de z marcherait ou pas mais il y a possibilite de donner une valeur estimative de z qui pourrait donner lieu a une solution.
J`essaie de prouver que la valeur de z(z+1)=0 (z=0) peut marcher avec n`importe quel n mais cela reste difficile quand n croit.

par **Mario2015** » 05 Jan 2015, 16:53

Pour tout z fixe d`avance l`equation serait de la forme :

y^2+ay+b = 0 mod n

Existe-t-il un y pour toute valeur fixe de z?

Si oui il y a moyen de bricoler meme avec un n non premier.

par **zygomatique** » 05 Jan 2015, 20:20

je répète ce que j'ai déjà dit ....

qu'on n'ait que l'équation x(x + a) + y = 0 [n] ou qu'on y rajoute la condition x - y + b = z(z + 1) ou non on sait théoriquement résoudre ce problème ... car on sait résoudre une équation du second degré ...

épictou !!!

ensuite évidemment dans la pratique, les cas particuliers (n premier ou non, relation entre a, b et n, ....), l'ingéniosité ou non rendra difficile ou non sa résolution .....

mais dans tous les cas on sait trouver théoriquement les solutions ou prouver qu'il n'y en a pas ...

par **Mario2015** » 05 Jan 2015, 21:08

zygomatique a écrit:je répète ce que j'ai déjà dit ....

qu'on n'ait que l'équation x(x + a) + y = 0 [n] ou qu'on y rajoute la condition x - y + b = z(z + 1) ou non on sait théoriquement résoudre ce problème ... car on sait résoudre une équation du second degré ...

épictou !!!

ensuite évidemment dans la pratique, les cas particuliers (n premier ou non, relation entre a, b et n, ....), l'ingéniosité ou non rendra difficile ou non sa résolution .....

mais dans tous les cas on sait trouver théoriquement les solutions ou prouver qu'il n'y en a pas ...

En general les mathematiciens divergent peu sur les problemes de base, mais la, tu me surprends.
Si tu prouves qu`il y a toujours une solution pour z=0 a cette equation :
y^2+ay+c = 0 mod n (avec a et c des nombres de 400 a 500 chiffres et plus)
n est = d*p*q (d est un petit nombre a au plus 2 chiffres, p et q des nombres premiers de 300 chiffres et plus)
et que tu en trouves une SEULE en un temps raisonnable (une journee ordi), je te certifie que tu aurais la medaille FIELDS.

Je te file tout le raisonnement et toute la demonstration si tu es pret a relever le defi.

par **zygomatique** » 05 Jan 2015, 21:13

Mario2015 a écrit:En general les mathematiciens divergent peu sur les problemes de base, mais la, tu me surprends.
Si tu prouves qu`il y a toujours une solution pour z=0 a cette equation :
y^2+ay+c = 0 mod n (avec a et c des nombres de 400 a 500 chiffres et plus)
n est = d*p*q (d est un petit nombre a au plus 2 chiffres, p et q des nombres premiers de 300 chiffres et plus)
et que tu en trouves une SEULE en un temps raisonnable (une journee ordi), je te certifie que tu aurais la medaille FIELDS.

Je te file tout le raisonnement et toute la demonstration si tu es pret a relever le defi.

ensuite évidemment dans la pratique, les cas particuliers (n premier ou non, relation entre a, b et n, ....), l'ingéniosité ou non rendra difficile ou non sa résolution .....

prouver qu'il n'y a pas de solution c'est résoudre le pb ....

on sait résoudre théoriquement ce problème...

pratiquement voir ma citation au dessus !!!!

par **kikiou** » 05 Jan 2015, 21:26

svp svp svp je suis dsl pour le dérrangement mais personne n'a voulu m'aider
soit E un ensemble non videet f une application de E===E.pour toute partie a non vide de E.on pose B=A inter f(complément de A)
on suppose f est injective
montrer que f ne posséde pas de point fixe dans B
montrer que si A inclus dans f(A) alors B=l'ensemble vide
2)on donne e=z
a)on suppose f(n)=2n qq soit n appartient a Z et que A=im f.déterminer B
b)f(n)=2n+1 qq soit n appartient a A et A=2Z.déterminer B merciiiiiiiii

par **Mario2015** » 05 Jan 2015, 21:38

Il y a 2 choses differentes en matiere de non solution.
Prouver l`inexistence d`une solution est une chose.
Prouver qu`il n`y a pas de solution compte tenu de la technologie actuelle en est une autre.
Or dans mon cas, je sais que la solution EXISTE (je peux le prouver sur des nombres a moins de 30 chiffres) mais compte tenu de la technologie actuelle, on ne peut pas cela demanderait un siecle ou plus.
Je peux donner des exemples detailles sur des nombres de petite taille.

Merci pour ta contribution.

par **Mario2015** » 06 Jan 2015, 14:06

On peut prouver qu`il existe toujours au moins une solution de x correspondant a z=0.

A tout couple de nombres premiers impairs p et q on peut associer au moins un
couple (c,d) tel que :

|cp-dq|=1

Cela reduit mon equation a :

y=x+b

x(x+a)+x+b=0 mod n

x(x+a+1)=-b mod n

par **Mario2015** » 06 Jan 2015, 14:08

Sait-on resoudre cela en l`ignorance des facteurs de n et pour des nombres de grande taille?

par **chan79** » 06 Jan 2015, 16:42

A tout hasard ...
x(x+a+1)+b=z(z+1) peut s'écrire (2x+a+1)²-(2z+1)²=a²+2a-4b

par **Mario2015** » 06 Jan 2015, 20:33

chan79 a écrit:A tout hasard ...
x(x+a+1)+b=z(z+1) peut s'écrire (2x+a+1)²-(2z+1)²=a²+2a-4b

Un grand merci!
Laisse-moi un tout petit de temps pour rearranger tout cela en un algorithme complet.

Je ne veux pas te faire chuter de ta chaise mais tu as d`ores et deja la medaille Fields.
J`avais une solution boiteuse avant de presenter le probleme.
Je savais pertinemment qu`il existait une solution "simple" a mon probleme.
Je dois recoller les pieces du puzzle.
Quel age as-tu si ce n`est pas indiscret Chan79?
La Fields exige moins de 40 ans je crois.
Reponse dans quelques jours.

par **chan79** » 06 Jan 2015, 20:40

Mario2015 a écrit:
Je ne veux pas te faire chuter de ta chaise mais tu as d`ores et deja la medaille Fields.
.

???? :ptdr:

Me voilà bien !
Sérieusement, je n'ai fait que remarquer que l'égalité x(x+a+1)+b=z(z+1)
est l'équation d'une hyperbole. Un changement de repère en donne une équation plus simple.

par **Mario2015** » 06 Jan 2015, 21:00

chan79 a écrit:???? :ptdr:

Me voilà bien !
Sérieusement, je n'ai fait que remarquer que l'égalité x(x+a+1)+b=z(z+1)
est l'équation d'une hyperbole. Un changement de repère en donne une équation plus simple.

J`ai fait une bonne partie du chemin tout seul et j`avais un debut de solution sauf que mon chemin en termes de congruences n`etait pas le bon.
J`ai deja poste sur des forums en anglais ma demarche.
Je me suis heurte a un mur de silence. En general quand des matheux voient une faille quelque part ils deviennent bavards mais quand ils voient a l`horizon une ebauche de solution serieuse ils viennent lire et partent.
Mon post a ete lu plus de 850 fois sur un forum peu frequente.
Tu n`as pas a peter de rire.
Je suis pret a t`ecrire sur ton mail et a t`exposer le probleme depuis le depart jusqu`a ta fameuse proposition.
Merci un million de fois.
Je dois quand meme verifier un certain nombre de choses avant de crier victoire.
On a quand meme un grand nombre de couples solutions (x,z) et je peux modifier mes valeurs a et b si elles ne conviennent pas.

par **Mario2015** » 07 Jan 2015, 14:58

Apres quelques verifications, on peut dire adieu a la medaile Fields.
Ta formule quoiqu`elegante ne resoud rien en fait.
Elle est identique a n=(x+z+a+1)(x-z+a) a etant une valeur connue, x et z inconnues.
Avec cela, on ne resoud rien.
Il faut autre chose.
Retour aux congruences pour lesquelles j`avais une piste.

Merci quand meme.
Desole d`avoir ete si enthousiaste.

par **chan79** » 07 Jan 2015, 15:52

Mario2015 a écrit:Apres quelques vérifications, on peut dire adieu a la medaile Fields.

Dommage, je me voyais déjà avec un énorme nud papillon ... :ptdr:

par **zygomatique** » 07 Jan 2015, 16:51

bon mettons les points sur les i .....

bien sur qu'on sait résoudre théoriquement ce problème ... puisqu'on sait résoudre une équation du second degré ...

maintenant les valeurs particulières des différents paramètres peuvent corser (ou non) le pb ....

.... from ouam ... :lol3:

(*)

premier cas :: 2 est inversible dans Z/nZ 2 et n sont premiers entre eux

alors il existe u tel que

donc

alors on aura des solutions à chauqe fois que

pour un certain k

donc on étudie la fonction

et on regarde si c'est l'opposé d'un carré ou non ... (des résultats sont connus à ce sujet)

deuxième cas : 2 n'est pas inversible dans Z/nZ 2 divise n n est pair ... n = 2p

(+)

...

d'ailleurs (+) est vraie pour tout n .... (et on fera attention que la première implication n'est ... qu'une implication !!!! (lorsque n est pair ... mais peut-être une équivalence ... parfois ....)

Congruences

Qui est en ligne