Entiers composés incognito

Olympiades mathématiques, énigmes et défis
Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 15:00

nodjim a écrit:Dans ce cas, ça me semble une gageure. On ne sait pas aujourd'hui trouver des grands nombres premiers sans tester leur primalité. S'il existait une suite simple de nombres composés à coup sûr, dont on ne connaitrait pas à priori les facteurs premiers, alors on pourrait presque construire une liste de nombres premiers avec la contraposée de cette liste.

Pas forcement.
il existe des tas de suites infinies de nombres composes mais il n`y a aucune suite infinie de TOUS LES NOMBRES COMPOSES (hormis les cribles).
C`est deja interessant de produire une suite de nombres composes (a coup sur) qui ne soit pas triviale (pairs, ou nultiple de p, etc...).
C`est un exercice interessant (j`en ai publie quelques-unes tres speciales).



Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 24 Sep 2015, 15:23

Prend un grand nombre N au hasard et un entier a
Calcules a^(N-1) mod N, si ça fait 1, recommence tout, si ça fait pas 1, bravo, N est un nombre composé et on ne connaît (a priori) rien de ses facteurs.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 15:29

Determine un parametre k>10
Choix 2 grands nombres (>10^50) au hasard : m et n

A=(m*(m+1)*(m+2)*....*(m+k)) + (n*(n+1)*(n+2)*....*(n+k))

A est surement un nombre composite

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 15:32

Doraki a écrit:Prend un grand nombre N au hasard et un entier a
Calcules a^(N-1) mod N, si ça fait 1, recommence tout, si ça fait pas 1, bravo, N est un nombre composé et on ne connaît (a priori) rien de ses facteurs.


Il y a des algorithmes pour produire des nombres RSA.
Produit k nombres RSA et multiplie-les entre eux.

Bref, je ne sais pas ce que cherche celui qui a pose la question.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 16:35

archiM a écrit:Il faut que A soit composé à coup sûr. Pas de test, un algorithme.

Le A que j`ai propose est a 100% compose.
Facile a prouver.
Vas-y teste-le si tu veux.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 18:00

Autre exemple (il y en a une infinite)

B= produit (3*(2^n)-1) avec n variant de k a k+l

l>0 aussi grand que tu veux
k>1 aussi grand que tu veux

Tu peux obtenir un nombre compose B dont tu ne connais pas la factorisation si tu choix les bonnes valeurs de k et de l

Au lieu de 3 tu peux choisir n`importe quel nombre pair ou impair (>=2)

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 14:31

par zygomatique » 24 Sep 2015, 18:55

il semble évident que B soit un nombre composé .. puisque c'est un produit .... et on a même des diviseurs ....
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 19:22

zygomatique a écrit:il semble évident que B soit un nombre composé .. puisque c'est un produit .... et on a même des diviseurs ....


On a ses premiers facteurs c`est evident.
Rien ne nous dit que 3*(2^n)-1 est factorisable si n est suffisamment grand.
De plus, tout depend de ce que cherche celui qui a poste.
J`ai propose les nombres de Sierpinsky et les nombres de Riesel.
S`il veut des nombres similaires a Riesel et Sierpinsky il est possible d`en produire des "similaires".
J`en ai trouve un qui n`est premier que pour un nombre limite (5 ou 6 si je me souviens).
Qu`il explicite clairement ce qu`il veut.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 19:46

archiM a écrit:Attention Mario, dans ton exemple, on connait les diviseurs de B. Le défi est de construire une suite ne donnant que des composés DONT LES DIVISEURS SONT INCONNUS. C'est à dire des composés obtenus autrement que par leur produit. La factorisation vient après.
Le test de Fermat, par exemple, produit de temps en temps des composés incognitos, mais jamais de manière continue.

Peux-tu definir tres exactement un compose incognito?
Ou du moins donner un exemple.
Monsieur tout le monde voit tout de suite si un nombre est divisible par 3 ou par 11 etc....
Il fait son petit calcul et trouve.
Quelle difference entre le calcul rapide de MTLM et un programme qui teste les 10.000 premiers nombres premiers? Aucune si ce n`est la taille du calcul.
Il faut clarifier davantage ta question a mon avis.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 19:53

Si tu veux dire par compose incognito un nombre compose dont on ne connait pas les diviseurs en un temps raisonnable (compte tenu de la technologie actuelle), la je te dirais que personne ne le sait.
On sait produire un tres grand nombre semi-premier. Seul celui qui le produit sait quels sont ses 2 facteurs.
Quant a produire un nombre semi-premier sans en connaitre les facteurs soi-meme, ou un nombre compose produit de plusieurs grands nombres premiers, personne pour l`instant n`en est capable.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 24 Sep 2015, 20:07

@Mario:
A=(m*(m+1)*(m+2)*....*(m+k)) + (n*(n+1)*(n+2)*....*(n+k))

Ce nombre est trivialement pair si k>1.
et multiple de 3 si k>2
etc...

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 20:16

nodjim a écrit:@Mario:
A=(m*(m+1)*(m+2)*....*(m+k)) + (n*(n+1)*(n+2)*....*(n+k))

Ce nombre est trivialement pair si k>1.
et multiple de 3 si k>2
etc...

Ca je le sais. C`est l`evidence meme.
Si ce monsieur veut epater la galerie et donner un nombre compose que personne ne peut factoriser (si c`est son but), je peux lui founir une formule pour cela.
Je peux savoir si un nombre ayant certaines proprietes et factorisable, je peux en connaitre les facteurs. Il me suffit de produire 2 tres grands nombres premiers de les multiplier et de lui fournir ce nombre.
Ce monsieur demande un nombre dont on ne connait pas les divisieurs (le on veut dire quoi).
Si "on" veut dire un programme ou un calcul trivial (pair, ou multiple de 3 etc..., il y a les nombres RSA sur leur site.
Il y a des milliards de nombres RSA qui servent a crypter. Il aura l`embarras du choix.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 20:18

Ce debat ne peut avancer que si le posteur clarifie la definition de compose incognito.
Incognito par qui?
Par MTLM?
Par le plus pousse des programmes de factorisation?
What?

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 20:24

On peut confectionner un programme informatique qui cherche lui-meme de tres grands nombres premiers (500 chiffres et plus). Il existe des tests de primalite pour cela.
Il les multiplie et vous les balance.
Le programme connait les facteurs mais pas vous ou quelqu`un d`autre.
Si c`est cela incognito, eh bien, qu`il implemente le programme.
Tous les outils existent sur internet.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 24 Sep 2015, 20:33

Oui Mario, on ne sait pas vraiment ce que veut ArchiM, s'il veut des nombres difficiles à factoriser ou quoi. C'est ce que j'ai écrit tout au début.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 24 Sep 2015, 20:39

A=x^3+y^3 est factorisable

Il suffit de choisir x+y= un grand nombre (500 chiffres et plus de l`eclater en 2 : une partie impaire et l`autre pair. On choisit les x + y qui conviennent et on verifie si (x^3+y^3)/(x+y) est aussi un nombre premier.
Et le tour est joue!

Je donne l`exemple de peits nombres

x+y=13

13=1+12
=2+11
=3+10
etc....
on clacule tous les x^3+y^3 et on chercher un (x^3+y^3)/13 qui soit premier.

On aurait les nombres 1729,1339,1027....559

1339=13*103 (les 2 sont premiers) il y en a d`autres.

Avec de tres grands nombres il est impossible que quelqu`un puisse savoir sauf s`il sait que ce nombre est la somme de 2 cubes.

Il y a infinite de polynomes aisement factorisables.
On a l`embarras du choix.

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 25 Sep 2015, 09:25

C'est bien. Cependant, on en revient tjs à tester la primalité de (x^3+y^3)/(x+y). De plus, il y a un grand écart entre les 2 facteurs, ce qui signifie qu'on peut assez vite casser la décomposition du produit. Avec les codes RSA, on fait le produit de 2 premiers (probabilistes) de taille équivalente.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 20 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite