Discussion :

[rambc]

Algorithme non fiable à 100%...

C'est ce que l'on appelle un algorithme probabiliste.

C'est précisé ailleurs qu'il est inopérant dans le cas de clés RSA...
Le petit curieux qui a fait la demande d'un tel code, en C++ de préférence, voulait casser le "log discret" avec...

Moi, les casseurs de RSA via la factorisation, cela m'ai fait toujours marré. C'est un peu comme fut un temps ceux qui cherchaient un mouvement perpétuel ou la solution à la quadrature du cercle. Quelques fois il peut être bon de lire un peu de litérature sur le sujet...
Il existe des techniques pour casser les chiffrements de données : elles sont un peu plus subtiles qu'une simple factorisation, et bien entendu elles ne fonctionnent pas à 100%.

[yoshik]

Hélas,

Code :

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

1
2
3
4
5
6
7
8
9
10
11
>>> import os, sys
>>> sys.path.append(os.path.normpath("C:/Python26/libs/site-packages"))
>>> import psyco
 
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    import psyco
  File "C:\Python26\lib\site-packages\psyco\__init__.py", line 46, in <module>
    raise ImportError, str(e) + extramsg
ImportError: DLL load failed: Le module spécifié est introuvable. (check that the compiled extension 'C:\Python26\lib\site-packages\psyco\_psyco.pyd' is for the correct Python version; this is Python 2.6)
>>>

@+

Bon Au temps pour moi ce n'est pas libs mais Lib, mais windows ne gère pas la casse...
ET d'ailleurs

Code :

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

1
2
3
>>> s>>> import os, sys
>>> sys.path.append(os.path.normpath("C:/Python26/Lib/site-packages"))
>>> import psyco

renvoie le même message d'erreur
J'ai chargé le _init_py, l'ai rebaptisé et j'ai ce message :

Code :

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

1
2
3
4
Traceback (most recent call last):
  File "C:\Python26\psyco_error.py", line 8, in <module>
    file, filename, (suffix, mode, type) = imp.find_module('_psyco', __path__)
NameError: name '__path__' is not defined

[tyrtamos]

Factoriser pour un test de primalité c'est pas le plus efficace. Il est plus "facile" de tester la primalité directement.

Je me suis probablement mal exprimé. Partant de l'algorithme dont on parle, je me disais qu'en relançant le calcul récursivement sur les résultats obtenus, on devait pouvoir calculer les listes complètes de facteurs premier comme:

100238592813 = [3, 79, 701, 603349]

Mais pour relancer le calcul récursivement, il faut pouvoir arrêter si le résultat est premier, et seulement dans ce cas, sinon ça va boucler ou la décomposition sera incomplète. Cela condamne un peu l'algorithme de Pollard pour cette utilisation.

Il existe un algorithme récent efficace et déterministe : Test de primalité AKS. Pour la théorie, voir ce document. Une piste pour l'implémentation : les grandes étapes.

Merci, je ne le connaissais pas. Je vais creuser un peu. J'ai déjà pas mal travaillé avec Miller-Rabin, et bien qu'il soit probabiliste, il est très efficace, en particulier sur des nombres de plusieurs centaines de chiffres. Voir mes petites expériences ici:

http://python.jpvweb.com/mesrecettespython/est_premier

PS Bis : dans quel cadre vas-tu faire des tests de primalité ?

Au delà de la pure curiosité, j'ai fait une calculatrice scientifique (la Calculext) qui a une version installable (http://python.jpvweb.com/mesrecettespython/calculext) et une version mise à disposition sur le web (http://calculext.jpvweb.com/). Dans le cadre de l'évolution de cette calculatrice, je cherche en permanence à trouver des fonctions nouvelles ou plus efficaces.

Pouir ce qui concerne la factorisation ou les tests de primalité, je n'ai pour l'instant que les méthodes par division, à part le test de Miller-Rabin que j'intégrerai dans la prochaine version.

D'où mon intérêt pour ces questions (et merci de ton offre d'assistance).

Tyrtamos

[rambc]

... et une version mise à disposition sur le web (http://calculext.jpvweb.com/).

Comment fais-tu pour utiliser des scripts Python dans ton site ?

[tyrtamos]

Comment fais-tu pour utiliser des scripts Python dans ton site ?

C'est très simple: j'ai choisi mon hébergeur pour que ce soit possible

Je suis chez infomaniak (http://www.infomaniak.fr/), hébergeur suisse qui est un peu cher pour un amateur (120Euros/an) mais qui est le top pour la qualité de service. Et il permet les script Python en CGI. La seule limite est que chaque exécution ne peut dépasser 10 secondes (au delà, il coupe). Mais ce n'est pas un gros inconvénient parce que, bien que ce soit de l'hébergement mutualisé, les machines sont puissantes et pas surchargées (juste contrepartie du prix élevé).

Tyrtamos

[rambc]

Je suis chez infomaniak (http://www.infomaniak.fr/), hébergeur suisse qui est un peu cher pour un amateur (120Euros/an) mais qui est le top pour la qualité de service.

Trop cher pour moi. Dommage.

[tyrtamos]

Il y a d'autres hébergeurs qui acceptent Python. Cherche dans google avec "hébergeur python cgi"

Tyrtamos

[tyrtamos]

Bonjour,

Puisque j'en avais besoin, j'ai creusé un peu l'algorithme de Pollard Rho pour la décomposition en facteurs. Pour ceux qui sont intéressés:

http://python.jpvweb.com/mesrecettes...ion_pollardrho

Finalement, une décomposition en facteurs premiers de nombres de 24 chiffres en 0.13 secondes de temps moyen, ce n'est pas mal. Même si sur certains nombres, ça se gâte un peu (16 sec.).

Tyrtamos