Nombre premier sans "calcul"

**leg** · 14/09/2005, 11h33

Envoyé par M_A_L

Je ne sais pas ce qu'il fait comme calcul, et j'en connais encore moins sur la presque totalité de ces posts... mais si il a pu tester tt ces NP en un temps si courts.... c'est que ça doit marcher. J'ai hate de voir lorsque tu aura fini ça.

sauf si c'est un logiciel qui donne les racines primitives d'une quantité de nombres premiers , que l'on trouve sur internet.
Mais le probléme est tout autre . comme le fait remarquer Martini-bird . [d'abord il me semble incorect de parler et de critiquer un disparu car si on était a son époque, je pense que notre cher sph aurait reçu une fourre de coup de baton]
Ce qui est étonnant:
comment voulais vous faire un programme Mathématique
a) sans savoir le résultat que vous allez obtenir et surtout vous demandez a votre programme de sortir les racines primitives sans savoir ce qu'est une racine primitive ni même comment elle se calcule.
b) si vous testez un entier n en utilisant ces racines primitives pour savoir si il est premier c'est qu'au moins, vous savez ce que sont des racines primitives de P , vous n'allez quand même pas faire un programme sans savoir ce que vous faite ou ce que vous trouver comme résultat?????.
c) je vais démonter mon informatique le remonter a l'envers et je suis sûr de résoudre l'hypothèse de notre cher disparu...
pour répondre au nombre que j'ai mis, 19*2(43)-1 qu'elle est sa racine primitive ?
ou est'il premier? la réponse est: 19 que multiplie un nombre de mersenne composé..
que vien faire le nombre de bit la dedans comme l'à déjà souligné quelqu'un un peu plus haut...?

**SPH** · 14/09/2005, 12h05

Envoyé par Moma

Salut,
D'ailleurs, j'aimerais bien que tu me dises pourquoi le fait de trouver une racine primitive modulo n prouve la primalité de n (Prends par exemple n=4, il n'y a que deux inversibles, où alors n=9, et regarde les puissances de 2

).

Interessant... C'est peut etre pour cela qu'en testant plus de 90000 NP, la racine primitive equivalante a 2^x (avec x>1) n'est jamais trouvé ! .... de meme que le '9' que tu evoques...

ps: pour exemple : 2(458) veux dire que la racine primitive 2 a ete solicité 458 fois parmis les 90000 np

ps2: leg : le psychologue SPH te le dit : tu es influencable

invite588fad4e · 14/09/2005, 12h33

Envoyé par leg

sauf si c'est un logiciel qui donne les racines primitives d'une quantité de nombres premiers , que l'on trouve sur internet.
Mais le probléme est tout autre . comme le fait remarquer Martini-bird . [d'abord il me semble incorect de parler et de critiquer un disparu car si on était a son époque, je pense que notre cher sph aurait reçu une fourre de coup de baton]
Ce qui est étonnant:
comment voulais vous faire un programme Mathématique
a) sans savoir le résultat que vous allez obtenir et surtout vous demandez a votre programme de sortir les racines primitives sans savoir ce qu'est une racine primitive ni même comment elle se calcule.
b) si vous testez un entier n en utilisant ces racines primitives pour savoir si il est premier c'est qu'au moins, vous savez ce que sont des racines primitives de P , vous n'allez quand même pas faire un programme sans savoir ce que vous faite ou ce que vous trouver comme résultat?????.
c) je vais démonter mon informatique le remonter a l'envers et je suis sûr de résoudre l'hypothèse de notre cher disparu...
pour répondre au nombre que j'ai mis, 19*2(43)-1 qu'elle est sa racine primitive ?
ou est'il premier? la réponse est: 19 que multiplie un nombre de mersenne composé..
que vien faire le nombre de bit la dedans comme l'à déjà souligné quelqu'un un peu plus haut...?

Il y a eu pas mal de grande d'écouverte qui ont été un ''coup de bole''... il a peut- être effectivement trouvé une technique par hasard, en cherchant moin loin et différemment de ses prédecesseur.

**SPH** · 14/09/2005, 12h40

Merci M_A_L

J'ai soumis par email ma decouverte a un polytechnicien de toute confiance (un grand ami). Il me manque en effet une mathematique a ma mathematique. J'attend son analyse...
Sans preuve, je pense que la borne de Riemann peut etre ramener a cette fourchette : au moins une racine primitive se trouve entre 2 et NP-2 (voila pkoi je bossais a partir de 7 au fait !!)

**leg** · 14/09/2005, 12h50

ps2: leg : le psychologue SPH te le dit : tu es influencable.

tu n'est pas encore fatigué, de te faire passer pour ce que tu n'est pas! et encore moins pour ta dernière trouvaille...(" je parle de psycho bien sûr")

a) il te serait pourtant facile, de montrer sommairement, que, ce que tu avances est bien le fruit de ton travail et non pas l'interprétationt d'un résultat dont tu ignorais tout, pour l'avoir demandé sur ce forum et sur ce sujet.

b) dans les deux cas tu ne peux tester en faisant un programme des nombres premiers avec des racines primitivie modulo P ni même extraire des racines primitives de P sans en connaître l'existance d'une part et qu'est ce que cela veut dire modulo X car tu oublies en plus, qu'il a fallu te l'expliquer en long en large et en travers!!

A moins bien sûr que ta psychologie te l'interdise. effectivement tu peux continuer a nous montrer des chiffres et oublier les questions que l'on te pose pour ne pas ternir ton auréole...ce ne sont que des constatations sans plus ..
A +

**invite4793db90** · 14/09/2005, 12h52

Salut,

comme indiqué en mp, la borne déduite de l'hypothèse de Riemann généralisée ( $\text{[math]}$ ) est bien meilleure: il suffit de considérer les grands nombres.

Pour p voisin de 10⁹, la borne donne environ 30 000.

Petit exercice: tracer la courbe représentative des fonctions x→6x-2 et x→ $\text{[math]}$ .

Cordialement.

**SPH** · 14/09/2005, 12h54

Envoyé par martini_bird

Salut,

comme indiqué en mp, la borne déduite de l'hypothèse de Riemann généralisée ( $\text{[math]}$ ) est bien meilleure: il suffit de considérer les grands nombres.

Pour p voisin de 10⁹, la borne donne environ 30 000.

Petit exercice: tracer la courbe représentative des fonctions x→6x-2 et x→ $\text{[math]}$ .

Cordialement.

S'il te plait, peut tu rajouter le dernier message que je t'ai envoyé et qui montre precisement ce que tu dis ?

**invite4793db90** · 14/09/2005, 12h59

Vivi pas de souci: je postais le message précédent pendant que tu me répondais:

Envoyé par SPH

Oui, je viens de m'en appercevoir !
et quand j'ai dis a l'instant sur le forum que la borne se situe entre 2 et NP-2, je dépasse la borne de riemann alors que je dis qu'elle est trop large. En fait, je m'appercois que la borne est entre 2 et 10% a 20% du NP !! Ce qui semble correspondre a riemann dans les grands nombres...

J'en profite pour faire une petite remarque: 10%, c'est la fonction x→0.1 x qui est beaucoup plus grande que x→a ln² x (ordre de grandeurs des fonctions affines et logarithmes).

Cordialement.

**SPH** · 14/09/2005, 13h14

Je
Vous
Avais
Promis
Un
Programme

non optimisé

**leg** · 14/09/2005, 13h26

sph
[Sans preuve, je pense que la borne de Riemann peut etre ramener a cette fourchette : au moins une racine primitive se trouve entre 2 et NP-2 (voila pkoi je bossais a partir de 7 au fait !!)]
oui Mais ça c'est après que je je t'ai dit : on dirait des racines primitives de P
or ce que tu nous a montré c'est manifestement le résultat du calcul des racines primitives en partant de P . comment pouvait tu l'ignorer? Mais cela n'a aucune importance
rechercher la racine primitive entre 2 et NP-2 très bien .
racine primitive du 42 éme nombre de mersenne = Np
NP - 2 , tu dis que la racine primitive se trouve donc entre 2 et ce nombre, NP - 2 . Mais que pour l'instant tu ne peux le prouver; c'est dommage car tu prouverais qu'au moins, jusqu'a cette limite toutes les racines primitives modulo p se trouvent entre 2 et NP - 2 ce qui simplifirait les calculs pour tous les nombres Premiers jusqu' à cette limite .
Mais pour faire au minimum cette conjecture. il faut le montrer .
et le forum est là pour ça , car une conjecture même forte ne rapporte rien, donc tu n'as rien a craindre en expliquant ta méthode de calcule.

**SPH** · 14/09/2005, 13h32

Au moins, mon programme permettra d'atenuer ta credulité, j'espere...
Mais je ne t'en veux pas. Je reagirais comme toi si quelqu'un dirait "j'ai trouvé!! " sans jamais dire comment. J'attend la reponse de mon ami et je vous dis tout

**leg** · 14/09/2005, 14h12

voila SPH:
ton programme que je vien de tester afin qu'il n'y est aucun doute.
1111 no prime
11111 idèm
111111 "
1111111"
11111111"
111111111"
1111111111"no prime
11111111111 pas de résultat après 17 minutes.

mon algo P(30) 11111111111 non premier, et il m'a donné tous les Premier = 11(30) en 3 minutes

11111111113 = prime, et racine primitive = 5 instantané,
voila pourquoi il te faudrait expliquer ce que tu fais, car tu aurais tout a ganer et en tirer quelque chose de positif et de constructible

peut être que ton programme peu être amélioré mais pour cela il faut être plus ouvert
A+

**SPH** · 14/09/2005, 14h18

Envoyé par leg

voila pourquoi il te faudrait expliquer ce que tu fais, car tu aurais tout a ganer et en tirer quelque chose de positif et de constructible

peut être que ton programme peu être amélioré mais pour cela il faut être plus ouvert
A+

100% daccord, il s'ameliorera a coup sur quand vous connaitrez l'algo

(attention, les nombres se rapprochant dangereusement de 2 milliard peuvent dépasser dans l'algo la limite 32 bits et provoquer une erreur de calcul. Donc 11111111111 est trop grand et le programme calcul autre chose)

invited6139184 · 14/09/2005, 14h37

Heu ! C'est peut-être un détail, SPH, mais ton programme me dit que 5 n'est pas premier ...

**SPH** · 14/09/2005, 15h03

Mon PROGRAMME amélioré en recherche (rapidité)

Oui, 5 est premier mais il passait à la trappe. C'etait une faute de ma part. En fait, on devais lire "teste les nombres >5"

**leg** · 14/09/2005, 15h12

sph 2 000 000 000 c'est dérisoire comme limite.pour 32bits. le premier programme sur p(30) aussi bien en factorisation de n, que d'énumérer les Premiers allait jusqu'à 1.5 milliards de cellules, donc 1.5 mds*30, le programme sous linux va jusqu'a environ;
900 mds ce qui est tout autant dérisoire...Mais c'est suffisant pour ce que je fais.

**SPH** · 14/09/2005, 15h29

Envoyé par leg

sph 2 000 000 000 c'est dérisoire comme limite.pour 32bits. le premier programme sur p(30) aussi bien en factorisation de n, que d'énumérer les Premiers allait jusqu'à 1.5 milliards de cellules, donc 1.5 mds*30, le programme sous linux va jusqu'a environ;
900 mds ce qui est tout autant dérisoire...Mais c'est suffisant pour ce que je fais.

leg, tu es en train de comparer mon programme de 12k a un logiciel professionnel fait par une equipe de codeurs professionels qui ont egalement une approche beaucoup plus pointue que moi en math. Il n'y a donc rien de comparable...
Par contre, j'ai un algo et eux le talent ! Si on melange les 2, je pense que les mersenne premiers seraient plus facilement trouvables.
De plus, 2.1 milliard, c'est bien la limite 32 bits en comptant aussi les nombres negatif (ou, si l'on prend seulement les positif, la limite double; mais pas plus ! C'est mathematique !! carcule toi meme 2^32)

invite8c2a9674 · 14/09/2005, 16h19

Je n'est qu'un mot a dire, moi qui vient de prendre connaissance de ce post: Félicitation !!!
Je ne comprend pas grand chose mais j'attend la suite des nouvelles avec impatience...
Bon courage en tout cas

**leg** · 14/09/2005, 16h31

sph
mon algo a été programmé en c++ par un étudiant de l'essi a sophia antipolis.., 19 ans.

mais aucun algo de cette forme ne pourra jamais tester un mersenne...
ce qui est intérressant ce sont les idées que l'on peut développer pour a méliorer un autre programme et c'est de ça qu'il est question.

pour te donner une exemple personnel:
je veux savoir si 2^41 - 1 est premier ou non,
il est clair que mon algo s'arrète a 900 mds, il me faut aller jusqu'au double 2 199 mds.
la racine carrée = 1482 910
moi je part de racine carrée de U'/2 = 724 pour atteindre 117 et 117/3= A/U =39.22,
ou encore pour atteindre A/(U'-1) = 78,44
ou de a/724 = 965 pour ateindre 13367 = P facteur de M41
le but étant de trouver: A tel que A² - b² = M41, ou bien, P factorisant M41,
et j'ai même comme information Y/a = 12787.5 qui est trés peu éloigne de P = 13367
a² - b² = ((2^(p-1) -1) / 3
et bien imagine lorsqu'il me faut travailler sur 2^25 900 000 -1 le test de lucas =
25 900 000 - 1 opération
moi je risque den avoir quelque centaine de Mds avec un peu de chance
et si la chance me sourie je multiplie l'exposant par 2 et plus 1, je constate que Mn est composé;
moralité: j'évite de chercher pour rien et il ne faut surtout pas que j'ai cette chance car il ne serait pas premier

et alors il me reste plus qu'à

.
donc pour les nombres de Mersenne il me faut la formule exact qui me permette de savoir qu' un tel A existe, en trés peu d'opération du moins au maxi 10% du nombre d'opération du test de lucas, voir un nombre d'opérations linéaires quelque soit Mn.
Ce que je pense "possible" ..avec plus de connaissance dans le dommaine des résidus quadratiques..

invite3d7be5ae · 14/09/2005, 16h55

Résultat de ton algo : 0.85 secondes pour 6 chiffres (à 700 MHz) et 0.01 pour 5 chiffres.
Résultat de la méthode de division : 5 secondes pour 2 147 483 647 (à 33 MHz (une antiquité)).

Ton algo : quand j'ai multiplié par 10 le nombre, j'ai multiplié par 18 le temps.
Méthode des divisons : quand on multiplie le nb par 100, on multiplie le temps par 10.

Il ne te reste plus qu'à comparer.
Je pense que maintenant que tu vois que ton algo est en O(n), tu peux dévoiler ton algo.

**SPH** · 14/09/2005, 17h04

Envoyé par Mouette666

Je n'est qu'un mot a dire, moi qui vient de prendre connaissance de ce post: Félicitation !!!
Je ne comprend pas grand chose mais j'attend la suite des nouvelles avec impatience...
Bon courage en tout cas

Je tiens a faire un resumé complet pour tous ceux qui n'ont pas envie de tout lire; ce sera mieux.
A force de manipuler les nombres premiers, j'ai remarqué une caracteristique systematique que ne possede pas les non premiers. Et de cette caracteristique découle un nombre. Mais ce nombre, je ne l'obtient pas automatiquement (pour l'instant). En soumettant une liste de NP avec son nombre qui caracterise sa primalité (mais sans en révéler l'algo), certains ont dit que ce chiffre etait en fait 'la racine primitive modulo P' de ce NP. Pour rapelle, voici une petite liste :
NP {caracteristique}
3 {2}
5 {2}
7 {3}
11 {2}
13 {2}
17 {3}
19 {2}
23 {5}
29 {2}
31 {3}
37 {2}
41 {7}
43 {3}
47 {5}

Mon but n'etait pas de trouver des racine primitives mais apparement, je les ai trouvé et utilisé pour prouver qu'un NP est premier.
Depuis, le sujet stagne mais mon petit programme de 12k ne peux contenir une bank de référence des NP. Pourtant, il donne la primalité et le nombre que j'utilise et qui caracteriqe la primalité.
J'ai donc envoyé un email avec une description complete de ma decouverte a un ami polytechnicien et j'attend sa reponse.

C'est sûr qu'il y a differentes techniques pour montrer qu'un nombre est premier. Par exemple, ce code (a sauvegarder dans un fichier en .HTML) :

<html>
<script LANGUAGE="JavaScript">
function premier()
{
var n;
n = document.f1.a.value;
if (n>999999999999999 || n<=0 || n > Math.floor(n)) {a$= "Respectez les conditions\n \n Un entier n \n\n avec 0 < n < 1000000000000000"}
else
{
if (n % 2==0 && n>=3 || n % 3==0 && n>=4)
{if (n % 2==0 )
{a$= n.toString() + " = 2 x "+(n/2).toString()}
else
{a$=n.toString() + " = 3 x "+(n/3).toString()}
}
else
{
racn=Math.floor(Math.sqrt(n))
d=5;a=1 ; reste = 1
while (d<=racn && reste >0)
{a++ ; d=2*a+1 ; reste = n % d}
if(reste==0){a$= n.toString() + " = " +d.toString()+ " x " +(n/d).toString()}
else {a$= n.toString() + " est un nombre premier "}
}
}
alert(a$)
}
</script>

<head>
<title>testeur de nombre premier</title>
</head>

<body background="../imag/fond.gif">

<form name="f1">
<table border="1" width="100%">
<tr>
<td width="100%" align="center"><big><strong>Po ur savoir si un nombre entier est premier </strong></big></td>
</tr>
<tr>
<td width="100%" align="center"><strong>Entrez un nombre entier strictement positif avec
au maximum 15 chiffres</strong></td>
</tr>
<tr>
<td width="100%"><div align="center"><center><p><inp ut type="text" name="a" size="30"><input
TYPE="button" NAME="Bouton" VALUE="Testez votre nombre entier" onclick="premier()"></td>
</tr>
</table>
</form>
</body>
</html>

Bref, j'attend une reponse de mon ami pour vous en reveler plus...

invite36dac211 · 14/09/2005, 19h59

J'ai absoluement pas la capacités mathématiques de dire qui est dans le vrai et qui est trop scpetique ici ...
En tout cas, SPH, si tu as effectivement trouvé quelque chose, félicitation

Et à tous les membres de cette discution : félicitation pour être restez calmes et polis du début à la fin ! Ca dégénère facilement sur ce genre de sujet

PS : SPH, si jamais ton ami ne t'as pas rappeler dans la semaine, méfie toi : ton algorythme était sans doute bon

**SPH** · 14/09/2005, 20h04

Envoyé par Penangol

PS : SPH, si jamais ton ami ne t'as pas rappeler dans la semaine, méfie toi : ton algorythme était sans doute bon

lol, C'est dingue que tu dises ça car je pensais la meme chose. Je n'ai pas de nouvelle et je me dis que peut etre il a ete destabilisé par l'algo bete et mechant que je lui ai envoyé...

**invite4793db90** · 14/09/2005, 20h16

Salut,

quelques essais qui sont pas de très bonne augure:

1234577 (321 ms)
12345709 (3434 ms)
12345713 (4717 ms)
23456789 (7721 ms)
345678901 (13119 ms)
1111111113 (84452 ms)

Désolé...

Cordialement.

invite3d7be5ae · 14/09/2005, 20h37

Vous avez vu ce que j'ai écrit à la page d'avant?

Dès qu'on ajoute un chiffre, on multiplie par 17 ou 18.
Méthode des divisions : dès qu'on ajoute un chiffre, on multiplie par sqrt(10)~=3.

Envoyé par SPH

<html>
<script LANGUAGE="JavaScript">
function premier()
{
var n;
n = document.f1.a.value;
if (n>999999999999999 || n<=0 || n > Math.floor(n)) {a$= "Respectez les conditions\n \n Un entier n \n\n avec 0 < n < 1000000000000000"}
else
{
if (n % 2==0 && n>=3 || n % 3==0 && n>=4)
{if (n % 2==0 )
{a$= n.toString() + " = 2 x "+(n/2).toString()}
else
{a$=n.toString() + " = 3 x "+(n/3).toString()}
}
else
{
racn=Math.floor(Math.sqrt(n))
d=5;a=1 ; reste = 1
while (d<=racn && reste >0)
{a++ ; d=2*a+1 ; reste = n % d}
if(reste==0){a$= n.toString() + " = " +d.toString()+ " x " +(n/d).toString()}
else {a$= n.toString() + " est un nombre premier "}
}
}
alert(a$)
}
</script>

<head>
<title>testeur de nombre premier</title>
</head>

<body background="../imag/fond.gif">

<form name="f1">
<table border="1" width="100%">
<tr>
<td width="100%" align="center"><big><strong>Po ur savoir si un nombre entier est premier </strong></big></td>
</tr>
<tr>
<td width="100%" align="center"><strong>Entrez un nombre entier strictement positif avec
au maximum 15 chiffres</strong></td>
</tr>
<tr>
<td width="100%"><div align="center"><center><p><inp ut type="text" name="a" size="30"><input
TYPE="button" NAME="Bouton" VALUE="Testez votre nombre entier" onclick="premier()"></td>
</tr>
</table>
</form>
</body>
</html>

Tu es sûr de savoir optimiser un un programme.
Tu pourrais remaplacer par
{d=a+2 ; reste = n % d}.
Déjà que le java script est un language interprété.
A+

**SPH** · 14/09/2005, 20h43

Envoyé par martini_bird

Salut,

quelques essais qui sont pas de très bonne augure:

1234577 (321 ms)
12345709 (3434 ms)
12345713 (4717 ms)
23456789 (7721 ms)
345678901 (13119 ms)
1111111113 (84452 ms)

Désolé...

Cordialement.

Je sais martini. J'ai aussi repéré le chiffre 21212117 horriblement long. Je sais techniquement pourquoi !! Quand je dis qu'il manque une mathematique a ma mathematique, je parle de ca; c'est a dire de trouver le bon chiffre a utiliser dans mon algo. C'est ce que j'ai soumis a un ami...

ps : a Pole, ce n'est pas mon code, c'est un exemple internet

invite3d7be5ae · 14/09/2005, 20h47

Oups, je voulais dire : d=d+2.
C'est beaucoup plus rapide. (5s environ pour 2^31-1 et <1s pour le même nb (avec l'amélioration))

**SPH** · 15/09/2005, 14h59

En attendant des nouvelles de mon ami mathematicien, j'etudiais la conjecture de Riemann et je souhaite poser cette question :
Quel processus mathematique a suivi Riemann pour aboutir à 70((In(p)^2) ??

invite3dc2c2f6 · 15/09/2005, 15h34

Salut
Moi le prog plante pour 12345678912 ... c'est normal? (j'ai eu la flemme de le convertir en simple precision...)
Manu

invite3d7be5ae · 15/09/2005, 16h06

Oui, c'est normal. Il ne faut pas dépasser la limite de
2^31-1=2 147 483 647.
Et même moins car il y a des calculs, et si ses calculs sont plus grand que 2^31-1, le nombre obtenu est négatif et le programme plante ou donne un réponse bizarre et mauvaise.

Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Re : Nombre premier sans "calcul"

Discussions similaires

calcul d'écart "relatif", "type" ?