Algorithme pour nombres premiers.

[invite39dcaf7a]

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

Je donne un exemple au cas où je ne me sois pas fait comprendre : soit p = 17 et q = 23. On a alors r = pq = 391. Ne connaissant pas p et q, puis-je arriver à trouver que p = 17 (ou 23) et q = 23 (ou 17) sachant que pq = 391 et que p et q sont deux nombres premiers à l’aide d’un algorithme ?

Je précise que j’ai le niveau bac (pour ce qui est des maths) et que j’ai un ordinateur de particulier, c’est-à-dire que ce n’est pas un supercalculateur.

Je sais bien que plus p et q sont grands, plus ils seront difficiles (ou plutôt longs) à trouver. Mais je n’ai l’ambition que de trouver deux nombres premiers de deux chiffres (comme dans l’exemple), pas plus…

Ma question est donc de savoir si c’est réalisable et si oui, pourriez –vous m’indiquer une piste ?

En vous remerciant d’avance,
Antikhippe.
-----

[yat]

A mon avis pour des nombres à deux chiffres, le mieux est de prendre tous les nombres premiers entre 2 et la racine de r, et de diviser r par chacun de ces nombres. Quand ça tombe pile, c'est que tu es sur p, et le quotient donne q.

Je sais, c'est la méthode bébète, mais je ne connais pas les méthodes utilisées pour cracker des clés rsa ou ce genre de trucs...

Pour des premiers de deux chiffres, c'est amplement suffisant.

[invite39dcaf7a]

Pour des premiers de deux chiffres, c'est amplement suffisant.

Merci yat !

J'ai pensé exactement à la même méthode que la tienne. Seulement, je voudrais savoir s'il n'y a pas d'algorithme un peu plus élaboré où il y aurait un peu plus de mathématiques.

[inviteab2b41c6]

Bein a 1e vue si tu voulais un truc avec plus de mathématiques je pense que ton calculateur prendrait plus de temps pour chaque operation...
La tu n'as ainsi pas beaucoup de calculs a faire E(racine de r) calculs pour trouver p et q.

Cela etant si tu commences apres a prendre des nombres a n chiffres avec n qui devient grand, tu risques de passer beaucoup de temps et justement s'il y'avait des algos mathématiques très développé alors la méthode RSA serait cassée...

[A voir en vidéo sur Futura]

[invite39dcaf7a]

Cela etant si tu commences apres a prendre des nombres a n chiffres avec n qui devient grand, tu risques de passer beaucoup de temps et justement s'il y'avait des algos mathématiques très développé alors la méthode RSA serait cassée...

Je suis d'accord, mais pour des cartes bancaires ou autres, ils utilisent de très grands nombres premiers... moi, des nombres de 2 à 5 chiffres suffiraient amplement ! C'est justement pour prouver que la méthode RSA est très performante aujourd'hui : au départ, je prends deux nombres premiers de 2 chiffres puis après, deux nombres premiers de 3 chiffres et ainsi de suite pour montrer comment il est de plus en plus long de trouver les 2 nombres.

[invite3d9f8ee1]

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

cette question est le principe du code à clé révélé en cryptographie.

On transmet un texte codé avec une clé (un nombre non premier très grand).

Le destinataire possede une clé (un nombre premier d'environ 8 à 10 chiffres) qui lui permettra de décoder le message grace aux deux cles réunies : Les deux nombres r et p permettent d'obtenir le troisieme nombre q (nombre premier de huit à 10 chiffres) qui lui est la clé du code.

Un super CRAY ou un de ses confreres mettrait quelque chose comme 10^9 ans à tester tous les couples de nombre premiers

[invite3f53d719]

Lu,

Il existe un très grand nombre de méthodes pour factoriser les entiers, et la plupart sont assez complexes (d'un point de vue mathématique). J'ai fait un TPE sur la cryptographie, et j'ai donc du traiter un minimum la factorisation des clefs RSA. Sur cette page: http://tpe.crypto.free.fr/contenu/cl...cto/index.html , je développe la méthode du crible quadratique, qui permet de factoriser de très grands nombres. Les algorithmes modernes utilisent une version amélioré de cette méthode, mais le principe reste le même.

Eric

[invitebd686fd6]

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

Je donne un exemple au cas où je ne me sois pas fait comprendre : soit p = 17 et q = 23. On a alors r = pq = 391. Ne connaissant pas p et q, puis-je arriver à trouver que p = 17 (ou 23) et q = 23 (ou 17) sachant que pq = 391 et que p et q sont deux nombres premiers à l’aide d’un algorithme ?

Je précise que j’ai le niveau bac (pour ce qui est des maths) et que j’ai un ordinateur de particulier, c’est-à-dire que ce n’est pas un supercalculateur.

Je sais bien que plus p et q sont grands, plus ils seront difficiles (ou plutôt longs) à trouver. Mais je n’ai l’ambition que de trouver deux nombres premiers de deux chiffres (comme dans l’exemple), pas plus…

Ma question est donc de savoir si c’est réalisable et si oui, pourriez –vous m’indiquer une piste ?

En vous remerciant d’avance,
Antikhippe.

Pas un super calculateur ?

C'est trop drole ça !

Mais l'Eniac, il était 5000 foix moins puissant qu'un p4 et un de ses premiers programmes était sur les nombres premiers.

Alors si un Eniac le faisait, ton pc le fait des plus à l'aise.

[invite39dcaf7a]

Merci bien à tous pour vos réponses,

Lu,

Il existe un très grand nombre de méthodes pour factoriser les entiers, et la plupart sont assez complexes (d'un point de vue mathématique). J'ai fait un TPE sur la cryptographie, et j'ai donc du traiter un minimum la factorisation des clefs RSA. Sur cette page: http://tpe.crypto.free.fr/contenu/cl...cto/index.html , je développe la méthode du crible quadratique, qui permet de factoriser de très grands nombres. Les algorithmes modernes utilisent une version amélioré de cette méthode, mais le principe reste le même.

Eric

J'avais déjà vu ton site et je ne te cacherai pas que c'est lui qui m'a donné l'idée pour mes TPE... mais je ne m'étais pas plongé dans tes calculs. Ca a l'air assez dur mais je pense qu'en travaillant un peu, ça devrait marcher, sinon, je poserai des questions !

Maintenant, je pense que je vais essayer d'utiliser différentes méthodes pour factoriser les nombres premiers et de les comparer. Ca pourrait être assez intéressant, je pense.

[inviteab2b41c6]

Salut,
si tu veux montrer que c'est long de trouver la factorisation, tu peux peut etre le montrer mathématiquement aussi, ca se fait bien je pense...

[invite39dcaf7a]

Salut,
si tu veux montrer que c'est long de trouver la factorisation, tu peux peut etre le montrer mathématiquement aussi, ca se fait bien je pense...

Salut Quinto,

Je vois ce que tu veux dire... mais je compare les méthodes avec le nombre de symboles, le nombres de paramètres ?

[invite3f53d719]

Effectivement, c'est interressant de comparer le temps mit par les différentes méthodes pour factoriser tel nombre. Par exemple, tu peux tracer un graphe représentant en abscisse la taille du nombre, et en ordonné le temps mit pour le factoriser. Ensuite, il faut essayer de modéliser cette courbe par une fonction (par exemple exp pour la division triviale). Tu peux t'amuser aussi à démontrer ce modèle (ce qui est très complexe pour les méthodes évolués) à partir de l'algorithme utilisé. Sinon, pour le crible quadratique, il va te falloir des connaissances en arithmétique qui viendront avec le cours de spé (en esperant que tu sois spé maths). Bon courage pour ton tpe!

Eric

[leg]

Merci yat !

J'ai pensé exactement à la même méthode que la tienne. Seulement, je voudrais savoir s'il n'y a pas d'algorithme un peu plus élaboré où il y aurait un peu plus de mathématiques.

bonjour si tu cherches un algo un peu plus mathe, il y a l'algorithme P(30) il s'agit de 8 familles disjointes donc 8 séries avec a la tête de ces 8 séries un nombre premier P < 31 où 1 sera remplacé par 31 dans ton ex,17 * 23 = 391 = r ; r est congrue 1(30) r se trouve donc dans la série 1, a : 390/30 = 13 cellules de la cellule 0 = 1 par conséquent cette cellule se factorise par 17 et 23 ; ensuite tu compte a partir de la cellule = r, soit 17 cellules ou 23 cellules et tu obtient r1 ou r2; r1= 17*53 et r2= 23 *37 ce qui t'indique , que 17 va parcourir l'ensemble des P (30) ,c'est a dire la série 23 (30) et inversement 23 va parcourir la série 17(30). Pour information cet Ensemble des nombres P modulo 30 représente 26.6666.....666..des entiers naturels > 0 àl'exclsusion des 3 premiers: 2, 3 et 5 ainsi que leurs multiples! et rassure toi dans cet enssemble il y a tous les P sans exception avec leurs composés = r! le cycle de cet ensemble en partant de 1 est le suivant: 6.4.2.4.2.4.6.2 cest à dire la différence entre les nombre de cet E.p(30)
1 7 11 13 17 19 23 29
31 37 41 43 47 49 53 59.
je pense que tu as assez d'information pour tes travaux
pour positionner les bases de chaque série tu pars toujours de la céllule 0 dans cette cellule se trouve le premier P , 1 à 29 dans ton ex , la base 17 et 23 se positionne dans la treizième cellule , la base 7 et 13 dans la troisième cellule : 0,1,2,et 3 . Chaque cellule vaut 30 sauf la première qui est la cellule zéro = 1, ou 7, ou 11...ou 29 en fonction de la série que tu choisiras! dernière indication pour les séries 1 et 19 il y a 6 bases au lieu de 4 pour les autres!car tous nombres P au carré est congrue 1 ou 19 (30) donc dans la série 1, tu auras les bases 11*11, 19*19, 29*29,et 31*31
alors que pour l

[leg]

pour la série 13 modulo 30 les 4 bases sont:7 et19, 17 et 29, 13 et 31 , 11et 23 .
bon courrage amicalement.

[invite39dcaf7a]

Sinon, pour le crible quadratique, il va te falloir des connaissances en arithmétique qui viendront avec le cours de spé (en esperant que tu sois spé maths). Bon courage pour ton tpe!

Eric

Merci Eric pour ton investissement, je vais aller chercher dans tout ce que tu m'indiques. Sinon, je suis en spé maths, mais la prof de maths nous a dit qu'il faudrait viser plus haut... donc ça peut être compliqué que ça ne me dérrangera pas !

Et merci à toi, leg pour ta contribution... Je n'ai pas encore vu les modulos ou la congruence mais je vais aller regarder sur mon bouquin de maths de TS.

Merci encore à tous !

[invite3f53d719]

Sinon, je suis en spé maths, mais la prof de maths nous a dit qu'il faudrait viser plus haut... donc ça peut être compliqué que ça ne me dérrangera pas !

Fait gaffe de ne pas viser trop haut non plus, l'arithmétique deviens très vite très compliqué. Pour t'en convaincre, regarde la démo du test de Lucas-Lehmer: http://tpe.crypto.free.fr/index.html...ers/index.html . J'ai mis quelques heures à la comprendre vraiment...

[invite39dcaf7a]

Fait gaffe de ne pas viser trop haut non plus, l'arithmétique deviens très vite très compliqué. Pour t'en convaincre, regarde la démo du test de Lucas-Lehmer: http://tpe.crypto.free.fr/index.html...ers/index.html . J'ai mis quelques heures à la comprendre vraiment...

C'est ça qui est bon !!! De la récurrence, du raisonnement par l'absurde, de l'arithmétique... ça m'a l'air très intéressant !

[inviteab2b41c6]

T'as pas eu de mal pour un tel TPE?
Parce que ca nécessite pas mal de connaissances du supérieur quand meme...
Je n'ai pas trouvé la démonstration du théoreme sinon...

[invite3f53d719]

T'as pas eu de mal pour un tel TPE?
Parce que ca nécessite pas mal de connaissances du supérieur quand meme...
Je n'ai pas trouvé la démonstration du théoreme sinon...

Heu, je dois t'avouer que certains points m'ont beaucoup pris la tête, mais bon, vu que j'aime bien les maths, ca ne me dérange pas. Et puis vu que j'avais à peu près que ca à faire pendant l'année comme travail à la maison... Au moins j'aurais appris des choses interressantes Sinon, la démonstration en question est dans un rectangle jaune du III] b).

Eric

[inviteeb72d013]

Excusez-moi tout le monde !
Je viens de découvrir cette question. S'il n'est pas trop tard, voici un excellent algorithme qui nécessite des prérequis de 1°S, à savoir la résolution d'équation du 2° degré.
Cela ne posera de problème personne de ce forum.
Tout d'abord, ne parle pas de nombres de 'x' chiffres. Tu as plutôt intérêt à donner leur longueur en bits. Par exemple p et q de 6 bits (<64).

Posons N = pq avec p et q premiers de même longueur (c'est le cas le plus dur ! bien qu'à priori cela nous révèle une information sur eux deux !!)
Considérons le polynôme :
(X-p)(X-q) = 0 <==> X^2 - (p+q)X + pq = 0
<==> X^2 - sX + N = 0 avec s = p+q
rem : plusieurs chemins de niveau 1°S, T°C mènent à ce polynôme ( => exercice !! )
Factoriser N revienet donc à résoudre ce polynôme, qui n'a de solution que si son discriminant est strictement positif, soit s^2 > 4N.
Posons d = s^2 - 4N. Les solutions du polynôme sont donc (s-sqrt(d))/2 et (s+sqrt(d))/2.
Il faut donc que s et d soit pairs.
Prends alors s = l'entier pair strictement supérieur à la partie entière de sqrt(4+4N), et c'est gagné (en une seule opération !)

note : sqrt() signifie racine carré

Lorsque la longueur de N augmente, des adaptations sont nécessaires, mais cela n'est plus ta question ()...

Taraua.

[invitec0f3a9cc]

Désolé, taraua, c'était tentant, mais ça ne fonctionne pas avec le nombre 2627.

Je planche actuellement sur la définition suivante:

dans N*+, quelque soit N un nombre composé, il existe N' un nombre composé ayant un facteur commun avec N, tel que:
N' = ( R(N) + 2n )² + N - R(N)²

avec R(x) = racine entière de x

Exemples:

N=6, n=1, N'=18
N=21,n=2,N'=69
N=77,n=3,N'=209
N=143,n=2,N'=247
N=2627,n=74,N'=15651
N=2631463147,n=52634,N'=108017 33699

Se pose le problème de la progression de n pour parvenir à la factorisation.

Si quelqu'un a des idées...

[invitedebe236f]

ca methode marche tres bien sauf si les 2 nombres premier sont tres eloigne voila une amelioration
Sub a()

Dim c As Variant
Dim i As Variant
Dim f As Variant
Dim x1 As Long
Dim x2 As Long
Dim d As variant

c = 1124564891 'produit de 2 premiers

s = Int(Sqr(4 * c)) ' comme lui je calcule la somme minimale
If Int(s / 2) - s / 2 <> 0 Then s = s + 1 ' on prend un pair

For i = s To c Step 2 ' on passe tous les pair
d = i * i - 4 * c ' on calcule son d
If d > 0 Then
If Int(Sqr(d)) - Sqr(d) = 0 Then ' on verifie que c est bien un carre
x1 = (i - Sqr(d)) / 2
x2 = (i + Sqr(d)) / 2
If x1 + x2 = i Then
MsgBox "trouve"
End If
End If
End If

Next i



End Sub

[invitedebe236f]

bon la racine de 1124564891 etant 33534 un algo normal en 16767 test des nombre impair trouve

ici il faut 393419 iteration avec mon exemple c est catastrophique

[inviteeb72d013]

C'est bien CriCri !

Voici alors un complément pour toi qui "voit" certaines choses ...
Je pose N=pq avec q<q et N de longueur 2n bits
Je pose D = distance entre p et q: D = q-p
Je pose S = somme de p et q : S = q + p

Intéresse-toi à D minimum (noté Dmin), Dmax, Smin et Smax.
Piste :
. Bien sûr, Dmin et Smin sont liés entre eux.
. Bien sûr, Dmax et Smax sont liés entre eux.

A partir de Dmin et Smin, tu peux calculer p max et q min.
A partir de Dmax et Smax, tu peux calculer p min et q max.
Voilà qui te permettra d'améliorer ton algo...

Aide :
Dmin = 2 d'où Smin = sqrt(Dmin^2+4N) d'où recalcule Dmin = sqrt(Smin^2-4N).
Dmax = 2^(n-1)-2 (à priori !) (... mais il y a plus fort encore ! ( ) d'où ...
Pour être une paire (S,D) valide une condition est nécessaire (test d'arrêt) :
. 1 seul exactement d'entre les deux doit être divisible par 4, sinon tu incrémente Smin de 2 et recalcule Dmin ou décrémente Smax de 2 et recalcule Dmax.

Nous ne sommes plus très loin de la limite des acquis de T°C ...

Prends ton élan !
Taraua.

[invitedebe236f]

voila ce que j ai trouve
http://www-lipn.univ-paris13.fr/~banderier/Facto/

http://tpe.crypto.free.fr/index.html...ublique/facto/

mais bon pour se limiter a un entier long 4294967296 les divisions par les nombre impair(32768 division a faire) sont un algo suffisament rapide

[inviteeb72d013]

Cricri, les sites auxquels tu fais référence dépasse très largement le niveau de lycée et même de maths sup et spé. Là, nous ne jouons vraiment plus dans la même cours ...

Ma réponse concerne la question de antikhippe sur les "petits nombres premiers", adaptée à son niveau scolaire.
Prenons N=2336914739
alors :
init-min(N) (c'est ma fonction que je lance !)
Smin = 96684 [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0]
Dmin = 370 [1, 0, 1, 1, 1, 0, 0, 1, 0]
Pmax = 48157 [1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1]
Qmin = 48527 [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
et init_max(N) (c'est ma fonction que je lance !)
Smax = 101194 [1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0]
Dmax = 29876 [1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]
Pmin = 35659 [1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1]
Qmax = 65535 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

autre exemple :
N=2709602099
init_min(N)
Xmin = 104110 [1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0]
Dmin = 696 [1, 0, 1, 0, 1, 1, 1, 0, 0, 0]
Pmax = 51707 [1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]
Qmin = 52403 [1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1]
init_max(N)
Xmax = 106880 [1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
Dmax = 24186 [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0]
Pmin = 41347 [1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]
Qmax = 65533 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]

Plutôt que de parcourir les P ou les Q, il est plus court de parcourir S entre Smin et Smax par pas de 2.
Lorsque sqrt(S^2-4N) est un entier, nous avons D. On en déduit les facteurs P=(S-D)/2 et Q=(S+D)/2.

C'est là une introduction douce au problème de "résidus quadratiques" ...

En attendant, essaye de réécrire ton programme en réduisant ton espace de recherche.
Si tu n'y arrives pas, j'envoie ma version.

Pour le reste, vise au minimum le DEA de mathématiques pures, et fais ta thèse dans un laboratoire crypto.

Dernier post ...
Taraua.

[invite39dcaf7a]

C'est vrai que les deux documents de cricri sont très complexes pour mon petit niveau de terminale ! lol

Merci en tout cas pour vos réponses intéressantes. C'est dommage que mes TPE soient déjà passés.