Discussion :

[sandaff]

Bonjour tout le monde;

Il y a une question qui tarode l'esprit que j'aimerais savoir:

Sachant que nous ne connaisons pas les facteurs premiers d'un nombre composé impair, comment peut on encadrer soit le plus petit diviseur ou le plus grand diviseur; soit le deux?

Il y a t-il de possibilité de faire ce calcul sur ce nombre composé et les valeurs qui encadre soit plus proche du diviseur?

si N est le nombre et p et q les deux divisurs p superieur à q;
valinf<p<valsup ou valinf<q<valsup
ou les deux :
valinf1<q<valsup1 et valinf3<p<valsup4

Merci d'avance pour votre eclaircisement!

[Flodelarab]

Bonjour

À partir de 5, tous les nombres premiers sont de la forme 6n±1. On peut donc aller de 6 en 6. Le petit facteur est entre 2 et racine de N. Le grand facteur est entre racine de N et N.

[sandaff]

Merci pour votre intervention;

ça encadre mais pas très proche en prenant chaque nombre;

si c'est trop eloigner le calcul deviendra long qui n'arrangera pas.

[wiwaxia]

Bonjour,

... À partir de 5, tous les nombres premiers sont de la forme 6n±1. On peut donc aller de 6 en 6 ...

La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 21, 23 ...
conduit à des écarts alternativement égaux à 2 et 4, valeurs données par l'expression itérative x_k+1 = 6 - x_k ;
on les obtient par des instructions du type

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
d:= 1; e:= 4;
REPEAT
  d:= d + e; e:= 6 - e; ...
UNTIL <condition d'arrêt>

[Jipété]

Yep !

La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 21, 23 ...

21 !

[wiwaxia]

Bonjour

Exact. La suite des exemples était:... 19, 23, 25, 29, 31 ...

[Flodelarab]

Exact. La suite des exemples était:... 19, 23, 25, 29, 31 ...

25 ! 25 n'est-il pas le carré de 5 ?

[sandaff]

Bonjour,
La succession des entiers possiblement premiers 5, 7, 11, 13, 17, 19, 23 ...
conduit à des écarts alternativement égaux à 2 et 4, valeurs données par l'expression itérative x_k+1 = 6 - x_k ;
on les obtient par des instructions du type

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
d:= 1; e:= 4;
REPEAT
  d:= d + e; e:= 6 - e; ...
UNTIL <condition d'arrêt>

J'aime beaucoup votre intervention!

surtout merci pour tous ceux qui ont intervenu et j'espère que s'il y d'autre idées concernant ma question, une solution qui pourrait encadrer de tout près l'un des diviseurs premiers d'un nombre je serrai très ravis.

[wiwaxia]

Bonjour

25 ! 25 n'est-il pas le carré de 5 ?

Faut pas pousser ! J'ai repris la première suggestion de Flodelarab

À partir de 5, tous les nombres premiers sont de la forme 6n±1.

en proposant d'utiliser la suite des nombres impairs non multiples de 3: 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 ... .
Si tous les nombres premiers dépassant 3 sont de la forme (6*k ± 1), tous les termes de la suite ne sont pas, eux, nécessairement premiers puisqu'on y retrouve les multiples de⁽¹⁾ 5, 7, 11, 13 ... etc ; j'ai bien parlé des

nombres possiblement premiers

, sous-entendant ainsi qu'ils ne le sont pas tous.

L'emploi de cette liste constitue l'un des algorithmes les plus simples pour la recherche des diviseurs d'un nombre entier.

(1) Correction consécutive au contrôle intransigeant de Jipété.

[wiwaxia]

... Sachant que nous ne connaissons pas les facteurs premiers d'un nombre composé impair, comment peut on encadrer soit le plus petit diviseur ou le plus grand diviseur; soit le deux?

Il y a t-il de possibilité de faire ce calcul sur ce nombre composé et les valeurs qui encadre soit plus proche du diviseur? ...

La recherche des diviseurs éventuels d'un nombre impair (N) exige de passer par l'énumération des entiers impairs ne dépassant pas (√N); en l'absence de toute information sur le nombre de départ, il n'existe malheureusement pas de raccourci par cadrage des solutions recherchées.

On a par exemple:
# 1000000000000009 = 179*5586592178771 (l'identification du plus petit diviseur est alors très rapide);
# 1000000000000003 = 14902357 * 67103479 (les calculs sont alors 83000 fois plus longs):
# 1000000000000037 est premier (il faut donc effectuer plus de dix millions de vérifications).

La seule amélioration envisageable est d'utiliser une suite comportant une plus forte densité de termes premiers, par ex. la suite définie par

d MOD 30 = {1, 7, 11, 13, 17, 19, 23, 29 ...} , valable au-delà de 5 .

Le gain obtenu (8/30 = 27% de candidats à la primalité au lieu de 2/6 = 33%) se révèle décevant au regard de la complication de l'algorithme ... mais on aborde là un autre sujet de discussion.

[Jipété]

Salut,

nombres possiblement premiers

C'est quoi, un nombre possiblement premier ?
Pour moi, grand béotien devant l'éternel, un nombre est premier ou pas et ce possiblement n'a rien à faire là, si ce n'est pour embrouiller les choses...

... puisqu'on y retrouve les multiples 5, 7, 11, 13 ... etc

Manque pas un mot, là ?

Bon week-end,

[wiwaxia]

Salut

... C'est quoi, un nombre possiblement premier ?
Pour moi, grand béotien devant l'éternel, un nombre est premier ou pas et ce possiblement n'a rien à faire là, si ce n'est pour embrouiller les choses ...

Je parlais évidemment de l'ensemble des entiers considérés, de la forme N = 6*k ± 1, susceptibles d'être premiers, sans que l'on puisse déduire leur éventuelle primalité de leur expression générale - et non pas des valeurs simples citées en exemple dans l'ordre croissant, et pour lesquelles la réponse va de soi.

D'ailleurs, il n'y a plus de réponse immédiate pour les grandes valeurs entières - du moins en ce qui me concerne, par ex. lorsque k = 10²⁰:
# 6E20 + 1 est premier, tandis que
# 6E20 - 1 = 157197917×3816844468747 résulte du produit de deux facteurs premiers; il appartient au type d'entiers impairs composés que recherche Sandaff.

À l'opposé, la réponse est unique dans le cas des autres ensembles apparentés de nombres entiers: (6*k + 2), (6*k + 3), (6*k + 4) sont tous multiples de 2 ou 3, donc composés.

[tbc92]

@Wiwaxia,
Tu dis que le calcul est 83000 fois plus long pour 14902357 * 67103479 que pour 179*5586592178771.
Par un petit changement d'algorithme tout simple, je pense que le calcul est 83000 fois plus rapide pour 14902357 * 67103479 que pour 179*5586592178771.

Comme Sandaff s'intéresse aux questions de Cryptographie (il a publié différents trucs sur le sujet), les nombres qu'il est amené à manipuler sont plus souvent du type 14902357 * 67103479 que 179*5586592178771.

[wiwaxia]

Bonjour,

... Par un petit changement d'algorithme tout simple, je pense que le calcul est 83000 fois plus rapide pour 14902357 * 67103479 que pour 179*5586592178771.

Comme Sandaff s'intéresse aux questions de Cryptographie (il a publié différents trucs sur le sujet), les nombres qu'il est amené à manipuler sont plus souvent du type 14902357 * 67103479 que 179*5586592178771.

Lequel ? Je brûle de connaître un procédé aussi simple et efficace, ayant moi-même été confronté à la lenteur des calculs impliquant des nombres premiers !

Et si l'on doit vraiment s'engager dans la cryptographie, il faudra envisager de très grands entiers dont les chiffres se comptent par dizaines ou centaines; les tests de primalité seront radicalement différents. Sandaff est passionné par son sujet, mais semble avoir du mal à saisir certains des problèmes rencontrés; les réponses aux questions posées se sont toujours ramenées à l'énumération (basique, je le reconnais) des diviseurs d'un entier. Pas mal de réponses ont été données sur le même thème, et il serait déjà bien qu'il ait tout compris. Le noyer dans des développements théoriques ne conduirait qu'à l'égarer, ou le décourager.

Ceci dit, je peux me tromper, et céderai volontiers la place à qui voudra l'emmener sur de nouveaux chemins.

Je reste néanmoins impatient de connaître le petit changement d'algorithme tout simple superspeed auquel il a été fait (trop brève) allusion.

[tbc92]

Au lieu de parcourir les premiers dans l'ordre ascendant {2,3,5,7 ... p(k-1), p(k) } , on les parcourt dans l'ordre descendant { p(k), p(k-1), ... 7,5,3,2}
Evidemment, ce qu'on gagne d'un côté, on le perd de l'autre.
Si les nombres à tester sont totalement aléatoires, on perd beaucoup plus que ce que l'on gagne.
Si les nombres à tester ont été préparés par un process particulier, on peut éventuellement être gagnant.

[Guesset]

Bonjour tbc,

Au lieu de parcourir les premiers dans l'ordre ascendant {2,3,5,7 ... p(k-1), p(k) } , on les parcourt dans l'ordre descendant { p(k), p(k-1), ... 7,5,3,2}
Evidemment, ce qu'on gagne d'un côté, on le perd de l'autre.
Si les nombres à tester sont totalement aléatoires, on perd beaucoup plus que ce que l'on gagne.
Si les nombres à tester ont été préparés par un process particulier, on peut éventuellement être gagnant.

En crypto, autant que je me souvienne, dans un couple de premiers participant à un nombre n, il ne faut ni avoir de valeur faible, ni de valeurs similaire (i.e. proche de sqrt(n)) justement pour éviter une factorisation trop facile. Prendre, par exemple, des premiers d'ordre de grandeur de la racine cubique de n et de la racine cubique de n².

Qu'on prenne le problème dans un sens ou l'autre n'a alors que peu d'importance.

Salut

[wiwaxia]

Au lieu de parcourir les premiers dans l'ordre ascendant {2,3,5,7 ... p(k-1), p(k) } , on les parcourt dans l'ordre descendant { p(k), p(k-1), ... 7,5,3,2}
Evidemment, ce qu'on gagne d'un côté, on le perd de l'autre.
Si les nombres à tester sont totalement aléatoires, on perd beaucoup plus que ce que l'on gagne.
Si les nombres à tester ont été préparés par un process particulier, on peut éventuellement être gagnant.

Entièrement d'accord. J'avais déjà pensé à changer l'ordre d'énumération, mais l'on mise à chaque fois sur un coup de chance, et l'on est statistiquement perdant.

Pour en revenir aux exemples cités:
# 1000000000000009 = 179*5586592178771
# 1000000000000003 = 14902357 * 67103479
les racines carrées sont très proches: √A ~ √B ~ 31622776.6
et les intervalles à parcourir pour trouver le premier diviseur sont respectivement:
a) dans le sens croissant: 179 et 14902357 ,
b) dans le sens décroissant: √A - 179 = 31622597 et √B - 14902357 = 16720419 .
Il est donc toujours plus long de procéder dans l'ordre rétrograde.

[tbc92]

Si on sait qu'on cherche 2 nombres proches de a et a^2 avec a^3 proche de n, on sait dans quel ordre parcourir les nombres premiers. Un coup dans le zig, et un dans le zag.

[sandaff]

Comme Sandaff s'intéresse aux questions de Cryptographie (il a publié différents trucs sur le sujet), les nombres qu'il est amené à manipuler sont plus souvent du type 14902357 * 67103479 que 179*5586592178771.

Bonjour Monsieur tbc92;

Merci pour votre remarque;

Effectivement je travail avec les pseudo composés de type 14902357 * 67103479 qui a le k=83000 fois d'incrementation que moi je compte reduire par ma troisième tentative;

Je cherche donc à trouver la borne superieure comme l'exemple pris ici:
entre la limte l2=15808879 vers le plus petit diviseur m1=14902357 et tantque la borne est proche, on arrive vite.

Je suis toujours sur ma théorie en apportant des astuces telsque:
au lieu d'incrementer n comme dans mon premier algo, je calcule deux delta successives avec k1 et k2 pour delta1 et k3 et k4 pour delta2
k2-k1 est l'ecartement dont je suis entrain de voir ce que ça va donner;
le k=14902357/2 cherche ne depasse pas le premier k1 car ça diminue de k en k;
je vais vous donner la trace pour mieux comprendre:

f=9

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Entrez votre RSA nombre pour chercher ses facteurs premiers:
9
Recherche des facteurs premiers:
Delta=0
l1=1
l2=1
m1=3
m2=3
f=3*3

f=21

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
Entrez votre RSA nombre pour chercher ses facteurs premiers:
21
Recherche des facteurs premiers:
Delta=64
n=13
Racine delata=8
Le reste=0
k1=1
k2=3
n=11
Delta=240
n=11
Racine delata=15
Le reste=-15
k3=0
k4=4
Ecartement=2
Variatonk=-1
Avancer=1
Arret=0
l1=2
l2=1
m1=3
m2=7
f=3*7

f=122642609

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
Entrez votre RSA nombre pour chercher ses facteurs premiers:
122642609
Recherche des facteurs premiers:
Delta=208256
n=122620461
Racine delata=456
Le reste=-320
k1=5480
k2=5594
n=122620459
Delta=562672
n=122620459
Racine delata=750
Le reste=-172
k3=5443
k4=5631
Ecartement=114
Variatonk=-37
Avancer=-41
Arret=2740
l1=5439
l2=5481
m1=9679
m2=12671
f=9679*12671

f=1000000000000003

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
Entrez votre RSA nombre pour chercher ses facteurs premiers:
1000000000000003
Recherche des facteurs premiers:
Delta=-608861232
n=999999936754452
Delta=-102896812
n=999999936754451
Delta=403067616
n=999999936754451
Racine delata=20076
Le reste=-21840
k1=15808878
k2=15813897
n=999999936754449
Delta=1414996496
n=999999936754449
Racine delata=37616
Le reste=-33040
k3=15806686
k4=15816090
Ecartement=5019
Variatonk=-2192
Avancer=-2798
Arret=7904439
l1=15806080
l2=15808879
m1=14902357
m2=67103479
f=14902357*67103479

plus ma borne s'approche de 14902357 le calcul va vite et me permettra de s'attaquer aux nombres RSA.

une chose est claire la valeur 14902357/2 est inferieur à k1=15808878 qui perme de nous situer.

Merci

J'espere avoir des explications sur le fameux tableaux de Monsieur wiwaxia:
d MOD 30 = {1, 7, 11, 13, 17, 19, 23, 29 ...}
ou une documentation;
je compte explorer les diviseurs la densité des diviseurs entre 2*15808878+1 à m1 ou entre 15808878 à 2*14902357/2 +1

[Guesset]

Bonjour tbc92,

Si on sait qu'on cherche 2 nombres proches de a et a^2 avec a^3 proche de n, on sait dans quel ordre parcourir les nombres premiers. Un coup dans le zig, et un dans le zag.

Tu as raison. Cependant j'ai bien pris garde de ne pas écrire proches, mais d'un ordre de grandeur ce qui laisse une très grande latitude de choix au dessus comme en dessous de ces valeurs.

Enfin, c'était un exemple pour illustrer les possibilités d'être à la fois loin des valeurs faibles et de la racine carrée de n, non une règle de construction.

Salut