Congruences

[Bambino9999]

Bonsoir,

J'aimerai solutionner ce problème ou du moins avoir un coup de main. Merci

(x(n-x) mod n) mod p = 0 (corrigé)

n et p sont connus

n,x,p entiers positifs > 3
n semi-premier impair (produit de 2 nombres premiers)
p premier > à la racine carrée de n
x
Je cherche surtout des orientations et des conseils.
Existe-t-il des algorithmes pour solutionner rapidement ce genre de problème avec un nombre de plus de 300 chiffres par exemple.

Merci pour tout conseil

[le_passager]

x(n-x) est multiple de p. Etant donne que p est premier, x est multiple de p ou n-x est multiple.

[Bambino9999]

x(n-x) est multiple de p. Etant donne que p est premier, x est multiple de p ou n-x est multiple.

Désolé j'ai commis une erreur dans l'énoncé.
Il était tard hier, j'ai écrit de mémoire mon énoncé d'où l'erreur, l'omission .
Je pars vraiment du mauvais pied sur ce forum.

[le_passager]

[quote="Bambino9999"]Bonsoir,

J'aimerai solutionner ce problème ou du moins avoir un coup de main. Merci

(x(n-x) mod n) mod p = 0 (corrigé)

n et p sont connus

n,x,p entiers positifs > 3
n semi-premier impair (produit de 2 nombres premiers)
p premier > à la racine carrée de n
xn on n'aura que 0. Lors du raisonnement il faut poser n=ab (a et b etant premiers). on remarquera alors que le reste ne peut pas etre 0.

[Bambino9999]

Merci beaucoup!
Je vois plus clair maintenant.

[le_passager]

je me suis trompe'. il n'y a pas que deux multiples. j'ai confondu racine de n et n/2. desole.

[Bambino9999]

je me suis trompe'. il n'y a pas que deux multiples. j'ai confondu racine de n et n/2. desole.

Ce n'est pas grave. J'ai mal posé mon problème.
En fait ce que je cherchais je l'ai trouvé ou du moins en partie.

Je cherchais si un nombre premier (ou son multiple k) pouvait être un résidu quadratique

(-x^2 mod n) mod p =0
ou (-x^2 mod n) mod k*p =0

Le critère d'Euler solutionne en partie le problème.

http://fr.wikipedia.org/wiki/Critère_d'Euler

Exemple :

n=2573 (je suppose que c'est un grand nombre et que j'ignore ses 2 facteurs 31 et 83)

Est-ce que 53 ou 53k est ou non un résidu quadratique ? Le 53 est un choix arbitraire

(-x^2 mod 2573) mod 53 =0
ou (-x^2 mod 2573) mod k*53 =0

Reste à savoir si on a un moyen de trouver directement ou rapidement les x ????