précision math module

Bonjour,
si j'écris :

Code:

---

1 2 3 4

from math import * a = 71641520761751435455133616475667090434063332228247871795429L b = long(sqrt(a)) print (a-b*b)

---

je suis assez déçu du résultat...
est il possible d'obtenir un calcul avec une précision à l'unité près ? Quelle est la précision en base des fonctions du module math ?
François :roll:

Bonjour,

Le module math calcule avec des flottants double précision (ceux du 'C').

Dans ton cas, tu peux obtenir une bonne précision avec le module "decimal":

Code:

---

1 2 3 4 5

import decimal decimal.getcontext().prec = 100 # on fixe 100 chiffres significatifs (28 par defaut) n = decimal.Decimal(71641520761751435455133616475667090434063332228247871795429L) r = n.sqrt()

---

Ce qui donne comme résultat:

Code:

---

1 2 3

r = 267659337146589069735395147283.3890881947405002610436510067721334911227900345873080152600596909928664 abs(n-r*r) = 2E-41

---

Ça ira comme précision?

Il existe aussi sur le web des algorithmes pour calculer la racine entière d'un nombre entier, et il est même amusant d'en inventer d'autres :D.

Tyrtamos

Merci tyrtamos :king:,
je ne connaissais pas ce module. C'est exactement ce que je cherchais. Je vais me documenter dessus. Et pour la manipulation de grands entiers, il y a un module qui permet de fixer la précision voulue ?
n c'était le RSA-59.

François :D

En ce qui concerne le module decimal, il est puissant sans être pratique à utiliser. Il est surtout utile quand on ne veut pas avoir d'incertitude sur les derniers chiffres comme on peut en avoir avec les flottants (0.1 => 0.10000000000000001), par exemple dans les domaines financiers.

Pour ce qui concerne les nombres entiers longs, il n'y a besoin d'aucun module supplémentaire, et le nombre de chiffres significatifs n'est limité que par la mémoire de l'ordinateur.

Par exemple, factorielle de 10000 est calculé en moins d'une seconde, et donne un résultat composé de 35660 chiffres...

Si ce genre de pb t'intéresse, tu peux regarder quelques applications arithmétiques sur mon site: http://python.jpvweb.com/mesrecettes..._arithmetiques.

Tu peux même les faire fonctionner dans ma calculatrice "Calculext": http://python.jpvweb.com/mesrecettespython/calculext, ou même essayer sur la version en ligne sur le web (mais temps de calcul limité à 8 secondes): http://calculext.jpvweb.com/.

Tyrtamos

Ok,

très bien ta calculatrice et ton site. Je l'ai adoptée après test. Parfaite pour ce que je veux faire sur le coin de mon bureau :mrgreen: Par contre, je pensais en la testant que le test premier ou non serait un test proba. Après lecture sur ton site, je crois qu'elle cherche un facteur en fait pour donner une réponse correcte à 100%. Je regarderai peut être pour ajouter un truc style Rabbin Miller pour avoir une réponse rapide. Maintenant, je n'ai plus d'excuse pour tester ma méthode de factorisation. Je vais me faire les dents sur le RSA-59 pour commencer:bug: En fait, je n'ai pas besoin de beaucoup de calcul mais d'une précision quasi parfaite sur des flottants (ouais, je sais c'est curieux pour un problème de factorisation d'entiers :aie:)
Merci encore,
François ;)

Bonjour et meilleurs voeux!

Si tu es toujours intéressé par un test de Miller Rabin, je viens d'en terminer un. Il est ici:

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

Effectivement, il est très efficace: 15 secondes pour tester si un nombre de 600 chiffres est premier...

Je vais maintenant m'attaquer aux méthodes de factorisation.

Tyrtamos

Hello,

Très intéressant cette étude du test de Miller-Rabin (avec un b et pas 2 comme je l'ai écrit un peu vite :roll:) Tu comptes l'inclure dans un module pour la calculext ?

François

Oui, bien sûr. Je vais la présenter sous forme d'une fonction unique:

- si n<=1024 : on exploite simplement la liste des nb premiers connus

- si n<=100 millions : on applique la méthode par divisions

- si > 100 millions : on applique la méthode probabiliste Miller-Rabin

As-tu déjà travaillé sur les méthodes de factorisation? J'ai fait la méthode de fermat, mais elle ne suffit pas pour les grands nombres. As-tu quelque chose pour la méthode GNFS?

Tyrtamos

oui, mais c'était il y a une dizaine d'années...Je m'étais penché à l'époque sur le QS et la raréfaction des nb premiers ainsi que sur leur interprétation géométrique. Je suis tombé l'autre jour par hasard sur le RSA-59 de l'ex concours et du coup je me suis vaguement repenché dessus via internet 8-)
je ne connais pas le GNFS car à l'époque je m'étais concentré sur les nombre type RSA ("proches" donc ) et il me semble de mémoire que le GNFS n'est pas trop adapté à ce type de factorisation. Je devrais ressortir tous mes livres sur le sujet pour dépoussiérer mes neurones :mouarf:

François

pour information :
RSA-59 =
357440504101388365610785389017 *
200429218120815554269743635437

j'ai regardé. Contrairement à mes souvenirs le ggnfs est bien adapté pour les RSA facteurs. Un très bon exemple détaillé est à : http://is.muni.cz/th/73040/fi_m/diplomka.txt
C'est en Tchèque 8O mais les calculs sont détaillés à la fin.
Il a factorisé le RSA-59 et le RSA-79 en exemple. Il ne reste plus qu'à le faire en python :yaisse2:

Bonjour,

Merci pour le lien, mais effectivement, je n'y comprend pas grand chose en tchèque.

Je viens de m'amuser à développer une factorisation par l'algorithme de shor, celui qui est utilisé dans l'ordinateur quantique, et qui fait très peur à RSA. Mais avec un PC d'amateur, ce n'est pas encore comme ça que je vais craquer le RSA-2048 :D . Mon code est ici:

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

Tyrtamos