Discussion :

[sandaff]

Bonsoir tout le monde;

Je ne sais pas si cette question à une bonne réponse ou pas.

Je voudrais savoir s'il y a une méthode permettant de trouver le rang d'un nombre composés impairs donné.

Par exemple de 1 à 100, il y a un total de 25 nombres composés impairs : 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95 et 99.

9 occupe le rang 1 et 15 le rang 2

comment savoir que 99 occupe le rang 25?

Merci pour votre aide.

[tbc92]

Il n'y a pas de formule précise toute faite. Evidemment.
Il y a des formules d'estimations assez classiques, valables pour les très grands nombres.
Généralement, on cherche la quantité de nombres premiers inférieur à un entier n. Il y a différentes formules plus ou moins précises pour obtenir une estimation de cette quantité. La plus simple de ces formules est n/ln(n)
Ensuite, par une soustraction, on obtient une estimation du nombre que tu recherches.

[Guesset]

Bonjour,

Ce n'est pas possible actuellement car c'est lié directement aux nombres premiers. S'il est possible d'avoir une densité de nombres premiers, il n'existe pas de formule directe (le comptage incrémental est loin d'être direct) qui donne son rang.

Or le négatif des nombres composés impairs est les premiers (impairs pour rester dans le même type). S'il était possible de savoir directement le rang r d'un nombre composé impair n, il serait facile de trouver directement le rang du premier immédiatement supérieur. Et réciproquement. Simplement parce que le nombre i d'impairs <= n (nombre impair) est (n-1)/2 en excluant 1.

En outre, si une telle formule existait, elle devrait retourner une valeur particulière quand elle ne trouve pas de rang, c'est-à-dire si le nombre n'est pas impair ou si c'est un premier. Nous aurions là un super test de primalité.

Salutations

[Flodelarab]

Bonjour

Utilise l'OEIS (clic ici) ou l'OEIS (clic aussi ici).

[sandaff]

Merci pour votre aide;

(n-1)/2 - n/ln(n)

Ce n'est pas facile mais j'ai réussit à réduire l’incrémentation;
Seulement je dois passer maintenant au code avec le C++ car mon code java est inaccessible, le disque est gâté donc j'ai peur de m'affronter encore avec le type bigInteger très difficile à manipuler;
mais mon souci reste le test à savoir si un nombre est décimal ou pas;

comme en java on a:

Code :

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

1
2
3
4
5
6
7
8
 
int i;
double d = 16.7;
i = (int)d;
if (i == d)
// entier
else
// décimal

mais en C++ j'ai la difficulté

en plus ça reste deux autre soucis:
-je voudrais savoir si c'est le type double qui gère les nombres RSA?
-et comment calculer la racine d'un type double en C++?

Je dois lever toutes ces question pour commencer le code, donc merci d'avance.

[Guesset]

Bonjour,

C'est toujours dangereux de faire correspondre a priori une opération informatique avec une opération mathématique sur des réels. Si c'était possible la cardinalité de la puissance du continu serait un problème réglé. Mais en informatique, toutes les grandeurs sont discrètes, y compris les flottants.

Prenons l'exemple des doubles, ils sont stockés sur 64 bits. Le maximum de valeurs différentes qu'on pourrait espérer (mais c'est inférieur) serait 2^64. Il y a donc des trous, des valeurs entières n'existent pas comme double, comme 2^60 - 1.0 par manque de précision (la mantisse a moins de 60 bits). On imagine bien que cela aura des effets aussi sur les comparaisons. Et même si le résultat est bon 99 fois sur 100, celui erroné ne se distinguera pas des autres.

Augmenter la précision des flottants améliore la situation sans faire disparaître le problème. Un simple rationnel comme 1/3 demanderait une infinité de chiffres.

Salutations

[sandaff]

Prenons l'exemple des doubles, ils sont stockés sur 64 bits.
ce qui veux dire que le type double ne gère pas les nombre RSA vue le cas de 2048 bits.

quel est le type qui le gère maintenant?

[Guesset]

Bonjour,

RSA ne travaille qu'avec des entiers (très grands) donc les flottants (doubles ou autres) n'ont rien à faire dans l'histoire.

Il faudrait commencer par étudier les algorithmes avant même de penser à un quelconque encodage.

En général, les bibliothèques qui gèrent les grands nombres (entiers) proposent des traitements de cryptage dont le RSA.

Salutations

[sandaff]

Bonsoir Mr Guesset;

Vous voulez dire que c'est plus dur que le java?

j'ai fouillé un peu et je vois le type long double et quel est sa porté et comment on l'utilise?

[sandaff]

Bonsoir;
Je veux me tourner vers Turbo pascal mais je voudrais comprendre si ces types permettent de gérer mon problème à savoir les grands nombres car je suis confus sur ces chiffres significatifs qui est 19 et 20 ici;

Extended 3.4 X 10 puissance-4932..1.1 X 10 puissance 4932 19 à 20 chiffres significatifs 10 octet

Comp -2 (puissance 63)+1..2 (puissance 63)-1 19 à 20 chiffres significatifs 8 octet

merci pour votre aide

[tbc92]

Il y a une vingtaine d'années, pour m'amuser, j'avais créé une boite à outils qui me permettait de travailler avec des entiers de 1000 ou 100000 chiffres significatifs, ou même plus.

ça ressemblait à ça :

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
Class Mon_type_entier  
   dim tb [1000]int32
end
 
function addition ( a  as mon_type_entier, b as mon_type_entier ) 
    dim somme as mon_type_entier
    retenue = 0
    for i=0 ; i<1000 ; i++ {
        c = a.tb[i]+b.tb[i]+retenue
        if c > 1000000 {
           retenue = round.inf( c / 1000000,0)
           c = mod ( c, 1000000)
        } else {
           retenue = 0
        }
        somme.tb[i]=c 
    }
    return somme
end function

Et une fonction un peu identique pour la multiplication, et pour la division ou le modulo.

[laurent_ott]

Effectivement, pour traiter des grands nombres il faut utiliser... des chaînes de caractères (type String).

La manipulation de ces grands nombres peut se faire avec des instructions simples comme celles apprises à l'école (sur les caractères un à un) mais les temps de traitement sont longs.
Heureusement il existe des méthodes qui permettent d'optimiser ces calculs en décomposant les chaînes et en les traitant comme des nombres. Ainsi une addition de deux nombres à plusieurs milliers de caractères est quasi instantanée.

J'ai récupéré à cette adresse http://fordom.free.fr/ des fonctions en BASIC (plus précisément en VBA) qui font les opérations élémentaires (sauf la division) et d'autres plus complexes (racines, exposants, test de primalité...), sur des entiers ou des flottants (positifs ou négatifs).
J'imagine que ce genre de bibliothèque existe dans d'autre langage de programmation, sinon il faudra convertir cette source (mais il y a du boulot).

Attention il faut corriger un bug dans l'addition (fonction AGN) :
Remplacer cette ligne :

Code VBA :

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

Mid$(Total, T - lr + Multiple, lr) = CStr(r)

Par les lignes ci-dessous :

Code VBA :

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

1
2
3
4
5
6
If CStr(r) = "100000000000000" Then
   Ret = 1
   Mid$(Total, T - lr + Multiple, Multiple) = "00000000000000"
Else
   Mid$(Total, T - lr + Multiple, lr) = CStr(r)
End If

J'ai utilisé ces fonctions dans une documentation qui explique la méthode de factorisation par le crible quadratique : ici
Et dans une autre qui explique la méthode de factorisation par les courbes elliptiques : ici

Comme indiqué plus haut il n'y a pas la division dans cette source alors j'ai dû en inventer (ou réinventer) une, vous trouverez cela dans le code source des fichiers joints aux documentations.

[EDIT]
il me semble que certains langages traitent les grands nombres (Perl ? et VB.NET avec BigInteger).

Cordialement.

[Flodelarab]

Bonjour

python gère de façon native les grands nombres.

[wiwaxia]

Bonjour,

... Je voudrais savoir s'il y a une méthode permettant de trouver le rang d'un nombre composés impairs donné.

Par exemple de 1 à 100, il y a un total de 25 nombres composés impairs : 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95 et 99.

9 occupe le rang 1 et 15 le rang 2

comment savoir que 99 occupe le rang 25 ? ...

Considérons l'ensemble des entiers naturels impairs premiers ou composés; en raison de l'exclusion du (1) qui ne lui appartient pas, la liste ordonnée selon l'ordre croissant commence avec (3), et tous les nombres envisagés admettent pour expression générale en fonction de leur rang (k):

I = 2*k + 1 .

Soit maintenant P(n) le plus grand nombre premier inférieur à l'entier envisagé, et de rang (n); la liste contient (n - 1) entiers premiers (du fait de l'absence du 2 , le seul nombre premier pair), et le nombre (r) d'entiers impairs composés admet pour expression:

r = k - (n - 1) = k + 1 - n .

Dans le cas où I = 99 , on a k = (I - 1)/2 = 98/2 = 49 , P(n) = 97 et n = 25 ,
de sorte que l'on obtient: r = 49 + 1 - 25 = 25
conformément à la question posée.

Le calcul implique la connaissance de la suite P(n) des nombres premiers, comme Guesset l'a signalé dès le début de cette discussion.

[wiwaxia]

L'algorithme déterminant le rang d'un entier composé impair s'apparente à celui donnant la liste des nombres premiers successifs; il comporte un test de primalité quelque peu allégé, la restriction aux nombres impairs dispensant du test de parité.

Il est possible de vérifier les résultats pour des entiers raisonnablement peu élevés par la consultation d'une liste en ligne des nombres premiers, par exemple celle à laquelle donne accès le lien suivant:

http://compoasso.free.fr/primelistwe...ste_online.php

sachant que sur le site indiqué chaque page contient (20*10 - 1) = 199 termes;
on trouve ainsi dans les deux cas suivants:

Code :

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

1
2
3
4
5
a) I =  9999    k = 9998/2 = 4999
P(n) =  9973    (page 7)     n =  6*199 + 35 = 1229    r =  5000 - 1229 =  3771
 
b) I = 99999    k = 99998/2 = 49999
P(n) = 99991    (page 49)    n = 48*199 + 40 = 9592    r = 50000 - 9592 = 40408

Le temps de calcul s'accroît considérablement lorsque le nombre testé (Nic) atteint et dépasse plusieurs centaines de millions, valeur très inférieure à la limite imposée par le Pascal (2³¹ - 1 = 2 147 483 647 pour les variables de type LongInt).
Une limitation semblable m'est apparue lors de la comparaison de deux programmes, l'un écrit en Virtual Pascal et l'autre en Python (par quelqu'un d'autre ); il s'agissait de trouver le dix-millionième nombre premier.
Par conséquent la possibilité de gérer les grands nombres débouche sur l'obligation d'accélérer les calculs.

Voici un programme simple permettant d'aborder le problème; il contient quelques procédures de confort rassemblées dans l'unité E_Texte: A_ (pose/arrêt), E(...) (couleurs/effacement), Wt(...), We(...) (affichage d'un texte ou d'un entier).

Code Pascal :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 PROGRAM Liste_Nombres_Impairs_Composes;
 
 USES Crt, E_Texte;
 
 CONST Nmax = 50000000;
 
 TYPE Tab_E = ARRAY[1..Nmax] OF LongInt;
 
 VAR Nic: LongInt; Liste: Tab_E;
 
 FUNCTION Test_Prim(n: LongInt): Bool;
   VAR Lim: LongInt; Test, Test3: Bool;
       Delta, q, r: LongInt;
   BEGIN
     Lim:= Trunc(Sqrt(n)); Test3:= ((n MOD 3)>0);
     q:= 1; Delta:= 4;
     REPEAT
       Inc(q, Delta); Delta:= 6 - Delta; r:= n MOD q;
     UNTIL ((r=0) OR (q>Lim));
     IF (Test3 AND (r>0)) THEN Test:= True ELSE Test:= False;
     Result:= Test
   END;
 
 PROCEDURE Enumeration(N_: LongInt; VAR L_: Tab_E);
   CONST C1 = 5; L1 = 3; L2 = L1 + 2;
         T = 'Rang du nombre impair compos‚: r = ';
   VAR p, r: LongInt;
   BEGIN
     p:= 7; r:= 0;
     IF Test_Prim(N_) THEN BEGIN
                             E(0010); Wt(50, L1, 'Nombre premier')
                           END
                      ELSE BEGIN
                             REPEAT
                               Inc(p, 2);
                               IF (NOT Test_Prim(p)) THEN BEGIN
                                                            Inc(r);
                                                            L_[r]:= p
                                                          END
                             UNTIL (p=N_);
                             E(0015); Wt(C1, L2, T);
                             E(0010); Write(r:9)
                           END;
   END;
 
 PROCEDURE Saisie(VAR N_: LongInt);
   CONST C1 = 5; C2 = C1 + 35; L1 = 3;
   VAR n: LongInt;
   BEGIN
     E(1015); Wt(C1, L1, 'Entier impair envisag‚:      Nic = ');
     REPEAT
       GotoXY(C2, L1); ClrEol; Read(n)
     UNTIL (Odd(n) AND (n>7));
     N_:= n; E(0012); We(C2, L1, Nic, 9)
   END;
 
 PROCEDURE Init_L(VAR L_: Tab_E);
   VAR j: LongInt;
   BEGIN
     FOR j:= 1 TO Nmax DO L_[j]:= 0
   END;
 
 BEGIN
   REPEAT
     Init_L(Liste);           // Mise … z‚ro de tous les termes de la liste
     Saisie(Nic);             // Saisie de l'entier impair
     Enumeration(Nic, Liste); // Affichage du r‚sultat
     A_
   UNTIL (Nic<10);
   A_
 END.

Les limites numériques des variables n'ont pas été testées. Il faudrait aussi envisager une programmation dynamique, par recours aux pointeurs.

[sandaff]

Considérons l'ensemble des entiers naturels impairs premiers ou composés; en raison de l'exclusion du (1) qui ne lui appartient pas, la liste ordonnée selon l'ordre croissant commence avec (3), et tous les nombres envisagés admettent pour expression générale en fonction de leur rang (k):

I = 2*k + 1 .

Soit maintenant P(n) le plus grand nombre premier inférieur à l'entier envisagé, et de rang (n); la liste contient (n - 1) entiers premiers (du fait de l'absence du 2 , le seul nombre premier pair), et le nombre (r) d'entiers impairs composés admet pour expression:

r = k - (n - 1) = k + 1 - n .

Dans le cas où I = 99 , on a k = (I - 1)/2 = 98/2 = 49 , P(n) = 97 et n = 25 ,
de sorte que l'on obtient: r = 49 + 1 - 25 = 25
conformément à la question posée.

Le calcul implique la connaissance de la suite P(n) des nombres premiers, comme Guesset l'a signalé dès le début de cette discussion.

Bonjour Monsieur wiwaxia

Vous avez une très bonne intervention même je suis un peu détourner vers python mais aussi un peu soufrant (mon cote gauche me fait mal, surtout mon avant bras, donc je n'arrive pas à bien travailler)

Je voudrais savoir comment vous trouvez n=25
si p(n)=97; on a p(25)=97 et par quelle expression que n=25;

j'ai cru que c’était une supposition mais votre deuxième intervention fait apparaître des calcules qui me fait comprendre que ce n'est pas un hasard.

[wiwaxia]

Bonjour,

... Je voudrais savoir comment vous trouvez n=25
si p(n)=97; on a p(25)=97 et par quelle expression que n=25;

j'ai cru que c’était une supposition mais votre deuxième intervention fait apparaître des calcules qui me fait comprendre que ce n'est pas un hasard.

C'est tout simplement le 25^me terme de la liste des nombres premiers:

Le repérage du rang devient de plus en plus difficile pour des nombres plus élevés, parce qu'il faut compter les pages précédant celle qui contient l'entier recherché. Le procédé trouve rapidement sa limite, et il faudrait trouver un site permettant une exploration plus efficace de la liste des nombres premiers.

L'établissement de cette liste est exclusivement algorithmique, il n'existe pas de fonction explicite p = F(n) ou n = G(p) - pour la raison qui a déjà été clairement exposée (#3)

[jack-ft]

Il y a une vingtaine d'années, pour m'amuser, j'avais créé une boite à outils qui me permettait de travailler avec des entiers de 1000 ou 100000 chiffres significatifs, ou même plus.

ça ressemblait à ça :

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
Class Mon_type_entier  
   dim tb [1000]int32
end
 
function addition ( a  as mon_type_entier, b as mon_type_entier ) 
    dim somme as mon_type_entier
    retenue = 0
    for i=0 ; i<1000 ; i++ {
        c = a.tb[i]+b.tb[i]+retenue
        if c > 1000000 {
           retenue = round.inf( c / 1000000,0)
           c = mod ( c, 1000000)
        } else {
           retenue = 0
        }
        somme.tb[i]=c 
    }
    return somme
end function

Ça revient à écrire le nombre en base 1000000.

Toute variable de type "Mon_type_entier" (comme a, b et c, ici) contient (ou plutôt représente) un "nombre" écrit en écriture "millionale", c'est-à-dire, plus précisément, avec 1000 "chiffres" compris entre 0 et 999999 (un peu comme les nombres en hexadécimal qui contiennent des chiffres compris entre 0 et 15).

Pour m'amuser, j'avais créé en 1979 un truc du même genre (mais en Fortran, sur cartes perforées) pour calculer les 100 000 premières décimales du nombre d'or en base 2... afin d'obtenir une suite pseudo-aléatoire de bits...

Maintenant, c'est plus facile d'utiliser une bibliothèque bignum (en lisp ou en python, par exemple) !

[sandaff]

C'est vraiment interréssant;
Vous pouvez m'expliquer un peu ça:

(page 7) n = 6*199 + 35 = 1229 ; n=page précédente*199+ quoi?


(page 49) n = 48*199 + 40 = 9592 n=page précédente*199+ quoi?

[sandaff]

Il n'y a pas de formule précise toute faite. Evidemment.
Il y a des formules d'estimations assez classiques, valables pour les très grands nombres.

bonsoir;
à partir de quel nombre?