Discussion :

[sandaff]

Bonjour tout le monde;

Je suis entrain de coder ma formule sur la décomposition d'un nombre en produit de facteurs premiers;

Pour l'instant le code marche avec les petites valeurs sauf à ce niveau j'ai un petit souci pour la lecture clavier qui ne répond pas; donc je suis toujours obligé d'initialiser f à décomposer:

Code :

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

f: int = int(input("Veuillez saisir le nombre entier à décomposer : "))

Bon; il y a aussi le reste de code qui ne fonctionne pas si le nombre à décomposer n'est pas un carré parfait;

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
if __name__ == '__main__': 
 
   tabpremier=[]
   tabcomposer=[]
# On  demande à l'utilisateur à saisir le nombre  qu'on convertit immédiatement en entier s'il saisie un chaine
 
   #f: int = int(input("Veuillez saisir le nombre entier à decomposer : "))
 
   f=21
 
   if miller_rabin(f, 50)==True:
         print("ce nombre est premier")
   else:
 
           print("La decomposition commence!")
           k1,k2=decompose(f)
           f1=2*k1+1
           f2=2*k2+1
           print(f"f={f1}*{f2}")
           if miller_rabin(f1,50)==True:              
              tabpremier.append(f1)
           else:              
              tabcomposer.append(f1)
 
           if miller_rabin(f2,50)==True:
              tabpremier.append(f2)
           else:
              tabcomposer.append(f2)
 
   while len(tabcomposer) != 0:
         for x in tabcomposer:
            k1,k2=decompose(x)
            f1=2*k1+1
            f2=2*k2+1
            tabcomposer.remove(x)
 
            if miller_rabin(f1,50)==True:
                tabpremier.append(f1)               
            else:
                tabcomposer.append(f1)  
 
            if miller_rabin(f2,50)==True:
               tabpremier.append(f2)              
            else:
                 tabcomposer.append(f2)
 
print("Resultat:")
 
print(tabpremier)

l'erreur est au niveau de la fonction miller-rabbin:

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
31
def miller_rabin(n, k):
 
    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification
 
    # If number is even, it's a composite number
 
    if n == 2:
        return True
 
    if n % 2 == 0:
        return False
 
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

Erreur: 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
La decomposition commence!
delta: 64
racine= 8.0
racin delta is not decimal; k1 et k2: 1 3
f=3*7
Traceback (most recent call last):
  File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 147, in <module>
    if miller_rabin(f1,50)==True:              
  File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 116, in miller_rabin
    a = random.randrange(2, n - 1)
  File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\lib\random.py", line 198, in randrange
    raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))
ValueError: empty range for randrange() (2,2, 0)
[Finished in 731ms]

avec f=25:

Code :

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

1
2
3
4
5
6
7
8
 
La decomposition commence!
delta: 0
f=5*5
Resultat:
[5, 5]
[]
[Finished in 1.4s]

le dernier problème est la conversion du grand nombre;
avec f=22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

Code :

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

1
2
3
4
5
6
7
8
9
La decomposition commence!
delta: 4026587744844483487536318615131830859270168820589264937687931746069624082190901751073970800735693961268773532158456941497347383268550394184237379432857564428082918697714124782611156420627755895559074161507012059201937483627100670423971972472547282768135772469857150537429931278057182940716774200363536136141887673102130914062979710654116235678493238795584989353758044570014034679663088386688017502671153712917960234419471976554033363387117536910299216717624957837239475202332338138290772
Traceback (most recent call last):
  File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 143, in <module>
    k1,k2=decompose(f)
  File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 58, in decompose
    racine_delta=math.sqrt(delta)       
OverflowError: int too large to convert to float
[Finished in 1.4s]

c'est vraiment une case tête, trop mesquin
merci d'avance pour votre aide

[wiztricks]

c'est vraiment une case tête, trop mesquin
merci d'avance pour votre aide

Quand vous recopiez du code sur Github, lire les commentaires qui donnent la solution....

- W

[tyrtamos]

Bonjour

Il y a quelque chose que je ne comprends pas bien dans votre démarche. Si, comme annoncé, votre objectif est d'obtenir une décomposition en facteur premier, un test de primalité comme MillerRabin ne suffit pas. Ainsi, si ce test montre que le nombre n'est pas premier, vous faites quoi pour le décomposer? Ce n'est plus du ressort de MillerRabin, mais d'un autre algorithme. Il en existe plusieurs plus ou moins complexes à programmer. J'utilise PollardRho que j'arrive à coder, mais ce n'est pas le plus rapide.

- Avec MillerRabin, on arrive à tester des nombres entiers très grands (2048 bits soit plus de 600 chiffres). A noter tout de même que pour des nombres en dessous de 100 millions, le test de primalité par division est plus rapide (en étant, en plus, exact).

- Avec PollardRho en plus pour la décomposition, voilà quelques exemples pour des nombres de 24 chiffres tirés au hasard par random.randint(...). Le temps de calcul moyen est inférieur à la seconde, mais ça peut dépasser 15 secondes dans certains cas:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
449946525836240730011144 [2, 2, 2, 22739, 2473429602424472987]
723631393653923846443861 [723631393653923846443861]
100761461480650516552474 [2, 13, 418031, 7150123, 1296579373]
309621299363859380750381 [19, 491, 7366397, 4505475319937]
470982819479871720893314 [2, 401, 8966899, 65492024992843]
659285903932670502433034 [2, 43, 419927, 18255828184441097]
440521626857087271425673 [3, 181, 811273714285611917911]
184558454917472165131677 [3, 17798911649, 3456362174591]
542761678115984315317635 [3, 3, 3, 5, 91247281, 44061114269621]
705972276260517746239783 [43, 1151, 333337, 42791779280963]
182994624593879036449624 [2, 2, 2, 137, 439, 380332342487652421]

A noter que je code en Python pur. Voir numpy ?

En conclusion, clarifiez votre demande d'aide, et je peux peut-être vous fournir des idées de codes.

[Edit] En complément, voilà d'autres exemples de décomposition en facteurs premiers de nombres de 40 chiffres (temps de calcul moyen de 20 secondes):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
3753711904607305217108603769624847061653 [23929, 677403871, 440285134733, 525962391279599]
5560027133898278890207917032936444758478 [2, 11, 349, 1784267603, 7371184950533, 55059403868999]
1802748910450276983154430265464802859162 [2, 17, 174443, 303950440991896052200167569562551]
1731251211123433768726577337410410176453 [3, 3, 547837109, 4439398675687, 79093717027581199]
3971552828077213593512200129601778672838 [2, 102953, 19288184064948149123931309090564523]
8287197061318119882356437640450778199457 [8287197061318119882356437640450778199457] <= nombre premier
8302072899528168286190020353800353394581 [8302072899528168286190020353800353394581] <= nombre premier
2881622285694505517435145848000257567126 [2, 239, 20732858915261, 290770246895356823828297]
7646974708782584761125000084787519254108 [2, 2, 3, 7, 4253, 184321, 116128861173243144142669274999]
9155024004984017851092676058122186339640 [2, 2, 2, 5, 61, 83, 189892348998494837, 238058724224647961]
8273087020381138545913560704737609994623 [17, 54804587, 6885530598347, 1289627689326588071]
5052400181155193871218188418181180739748 [2, 2, 397, 839, 1873, 25849, 78325605192845153391821107]

[sandaff]

Quand vous recopiez du code sur Github, lire les commentaires qui donnent la solution....

- W

Merci

ça me reste deux problèmes:

lecture au clavier comme indiquer dans premier post et la décomposition des grands nombres dont je vous ai montré le message d'erreur toujours dépendant de miller-rabbin;

En plus avec ce code je n'arrive pas à afficher comme je l'entend; c'est à dire f=3*3*3 par exemple;

Code :

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

1
2
3
4
5
6
print("Resultat:")
 
print(tabpremier)
print("f=")
for y in tabpremier:
  print(y,"*")

si f=27 ça m'affiche:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
la decomposition commence!
delta: 52
racine= 7.211102550927978
f=3*9
delta: 0
Resultat:
[3, 3, 3]
f=
3 *
3 *
3 *
[Finished in 11.2s]

Bonsoir Mr tyrtamos;

Je suis entrain de coder ma formule voir: https://www.developpez.net/forums/d2...poses-impairs/

je cherche à la faire évoluer en améliorant la théorie puis chasser les 2048 bits.
Merci

[tyrtamos]

Bonjour

Waouh. Si votre objectif est de craquer le chiffrement RSA, c'est gonflé, mais pourquoi pas. Malgré le nombre de mathématiciens qui s'y sont cassés les dents, il y a toujours possibilité d'une idée géniale à laquelle personne n'a encore pensé... Et si vous y arrivez, vous serez non seulement célèbre, mais aussi riche si vous vendez votre méthode (à qui?).

Actuellement, les méthodes de factorisation, au delà de la méthode de Pollard que j'utilise, sont la Factorisation de Lenstra par les courbes elliptiques (https://fr.wikipedia.org/wiki/Factor...es_elliptiques), et mieux encore le Crible général de corps de nombres (GNFS) (https://fr.wikipedia.org/wiki/Crible_alg%C3%A9brique). Mais la factorisation par cette dernière concerne des nombres d'une centaine de chiffres, et on est loin des nombres de 2048 bits (plus de 600 chiffres) du RSA.

Concernant le choix du langage, je pense que Python est mieux placé que Java, grâce aux nombreux modules mathématiques compilés en code source. Mais ce serait encore mieux en C ou C++ avec un module de type GMP (https://fr.wikipedia.org/wiki/GNU_MP). Il y a d'ailleurs un module Python qui fait le lien: gmpy2 (https://pypi.org/project/gmpy2/).

Actuellement, le seul espoir reconnu, qui est aussi une crainte, de craquer le chiffrement RSA repose sur le projet d'ordinateur quantique. Mais il y a encore du boulot avant d'y arriver...

Bon courage!

[wiztricks]

En plus avec ce code je n'arrive pas à afficher comme je l'entend; càd f=3*3*3 par exemple;

Vouloir coder des choses compliquées, sans même avoir appris à utiliser la fonction "print"?
Le message d'erreur (OverflowError) est tout aussi explicite que le premier (ValueError: empty range for randrange() (2,2, 0)).

Si vous vous retrouvez avec des erreurs en utilisant un code que vous n'avez pas conçu, trouvez un meilleur code.

Moi j'essaie juste d'aider ceux qui essaient d'apprendre à programmer et qui montrent qu'ils ont passé du temps à essayer de comprendre un minimum de choses (ça aide à se pouvoir se mettre à leur niveau pour essayer de les aider).

- W

[sandaff]

Bon courage!

Merci mais avant je suis bloqué au niveau du calcule de la racine des grands nombres;

j'ai utilisé en premier racine_delta=math.sqrt(delta) et ça donne cette erreur:

La decomposition commence!
delta: 4026587744844483487536318615131830859270168820589264937687931746069624082190901751073970800735693961268773532158456941497347383268550394184237379432857564428082918697714124782611156420627755895559074161507012059201937483627100670423971972472547282768135772469857150537429931278057182940716774200363536136141887673102130914062979710654116235678493238795584989353758044570014034679663088386688017502671153712917960234419471976554033363387117536910299216717624957837239475202332338138290772
Traceback (most recent call last):
File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 146, in <module>
k1,k2=decompose(f)
File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 58, in decompose
racine_delta=math.sqrt(delta)
OverflowError: int too large to convert to float
[Finished in 780ms]

puis ça aussi racine_delta=delta ** 0.5

La decomposition commence!
delta: 4026587744844483487536318615131830859270168820589264937687931746069624082190901751073970800735693961268773532158456941497347383268550394184237379432857564428082918697714124782611156420627755895559074161507012059201937483627100670423971972472547282768135772469857150537429931278057182940716774200363536136141887673102130914062979710654116235678493238795584989353758044570014034679663088386688017502671153712917960234419471976554033363387117536910299216717624957837239475202332338138290772
Traceback (most recent call last):
File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 146, in <module>
k1,k2=decompose(f)
File "D:\Users\DAFFE\AppData\Local\Programs\Python\Python36\Doc\decomposition", line 59, in decompose
racine_delta=delta ** 0.5
OverflowError: int too large to convert to float
[Finished in 1.4s]

[tyrtamos]

Bonjour

Bien sûr, calculer la racine carrée d'un nombre qui dépasse la limite des float ne marche pas avec le module "math".
Le nombre entier qui pose problème ayant 487 chiffres devrait avoir, après conversion en flottant, un exposant de +486, qui dépasse nettement la limite des float (-1.7976931348623157e+308 <= f <= 1.7976931348623157e+308).

La meilleure solution que j'utilise repose sur l'algorithme de Héron d'Alexandrie (il y a 2000 ans!) qui permet de calculer la racine entière d'un nombre entier:

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
def rac2ent(x):
    """Retourne la racine carrée entière de x (nombre entier)
       (Algorithme de Héron d'Alexandrie)
    """
    if not isinstance(x, int):
        x = int(x)
    if x<0:
        raise ValueError("Erreur: racine carrée d'un nombre négatif")
    if x==0:
        return 0
    rn = 1<<(x.bit_length()>>1) # calcule une racine approchée
    delta = x # participe aux conditions d'arrêt
    while True:
        rnp1 = (rn + x//rn)>>1
        if delta<=1 and rnp1>=rn:
            return rn # on a fini
        else:
            delta = abs(rnp1-rn) # calcule pour la boucle suivante
            rn = rnp1

Sur votre exemple:

Code :

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

1
2
3
4
5
x = 4026587744844483487536318615131830859270168820589264937687931746069624082190901751073970800735693961268773532158456941497347383268550394184237379432857564428082918697714124782611156420627755895559074161507012059201937483627100670423971972472547282768135772469857150537429931278057182940716774200363536136141887673102130914062979710654116235678493238795584989353758044570014034679663088386688017502671153712917960234419471976554033363387117536910299216717624957837239475202332338138290772
 
y = rac2ent(x)
print(y)
2006635927328244436547600546625561114507421165965850826885323212683097499597449582760109883823796343349425307250720893104227745507802527313593381890761296047403995618928652076195096200737656914435583837763446206659111275982742105557398398657880

Il faut cependant avoir conscience que le résultat n'est exact que pour un carré parfait puisqu'il n'y a pas de décimale. C'est à dire que cette racine élevée au carré ne retombera pas, en général, sur le nombre de départ. En fait, l'écart maxi sera de (y+1)**2-y**2.

A noter qu'en généralisant l'algorithme de Héron d'Alexandrie, on peut calculer la racine entière kième d'un nombre entier.

[Edit] On peut aussi utiliser le module Python "decimal" (https://docs.python.org/fr/3.10/libr...module-decimal), ou même utiliser un module externe comme gmpy2 (https://pypi.org/project/gmpy2/), mais cela nécessite de réorganiser complètement les calculs.