Calcul rapide de l'indicatrice d'Euler?

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

Calcul rapide de l'indicatrice d'Euler?

Messagepar Tyrtamos » Lundi 21 Janvier 2013, 12:49

Bonjour,

Pour améliorer la qualité mon générateur de nombres pseudo-aléatoires (Blum-Blum-Shub), et en particulier avoir la période la plus longue possible, j'aimerais calculer la condition sur les nombres premiers p1,p2 qui nécessite le calcul de l'indicatrice d'Euler phi: PGCD(phi(p1-1), phi(p2-1)) mini.

Rappelons que phi(p) = nombre de nombres i tels que 0<i<p et i premier avec p.

Je sais calculer phi avec le PGCD (merci Euclide), mais les nombres entiers avec lesquels je travaille sont très grands (disons: au moins 20 chiffres), et le calcul est donc trop lent (je n'imagine même pas essayer avec des nombres de 300 chiffres comme on peut en utiliser en cryptographie).

Ma question: Quelqu'un connait-il un moyen rapide de calculer phi?

Merci d'avance!
Tyrtamos
Utilisateur
 
Messages: 5
Inscription: Lundi 04 Février 2008, 18:21
Statut actuel: Actif et salarié

Publicité

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar rebouxo » Lundi 21 Janvier 2013, 15:01

Bon, ben mis à part une boucle pour compter les nombres premiers avec $n$, il ne semble pas y avoir d'algo plus rapide. La boucle devrait se faire rapidement, car de mémoire l'algo d'Euclide est très rapide. C'est quoi pour toi pas rapide ?

Edit : M'apprendra à parler sans tester. C'est pas rapide. Ne serait-il pas utile d'avoir un peu de mémoire, pour éviter de recalculer certains pgcd ? Pas sur que cela soit une bonne idée. J'ai vu que Demazure avait écrit sur ce problème. Si tes nombres ne dépasse pas 20 chiffres, cela vaut peut-être le coup de les décomposer en facteurs premiers.
Olivier
PS : j'aime beaucoup le nom de ton générateur pseudo aléatoire. On dirait le nom d'un cabinet d'avocat new-yorkais. :D
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6785
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar Tyrtamos » Lundi 21 Janvier 2013, 17:04

Merci pour la réponse!

Pour le nom du générateur, je n'y suis pour rien (https://fr.wikipedia.org/wiki/Blum_Blum_Shub) mais il me plait aussi :D . C'est en tout cas un très bon générateur, reconnu en crypto. Il est de plus assez facile à programmer.

Pour le temps de calcul avec le PGCD: le phi d'un nombre de 9 chiffres me prend environ 85 secondes. Si j'extrapole le rythme d'augmentation du temps avec la taille du nombre, pour calculer le phi d'un nombre de 20 chiffres, il me faudra environ... 700000 ans :shock:

Par contre, je sais factoriser un nombre de 24 chiffres en quelques secondes (algorithme de Pollard-Rho): mais une fois que j'ai la liste: j'en fais quoi pour avoir phi?
Tyrtamos
Utilisateur
 
Messages: 5
Inscription: Lundi 04 Février 2008, 18:21
Statut actuel: Actif et salarié

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar Framboise » Lundi 21 Janvier 2013, 18:38

Bonjour,

Pour la factorization de grands nombres, voir:
http://www.alpertron.com.ar/ECM.HTM
Cliquer pour activer le plug-in Java.
Des nombres de 100 chiffres et + sont efficacement traités.
Mais cela ne donne pas phi pour autant.

Voir Pari de Cohen:
http://en.wikipedia.org/wiki/PARI/GP
Un programme exceptionnel et de Bordeaux ! Comme quoi la France fait parfois de bonnes choses.

Voir également les livres de Cohen sur la théorie des nombres.
http://www.amazon.com/s?ie=UTF8&keywords=0387499229&page=1&rh=n%3A283155%2Ck%3A0387499229
http://www.amazon.com/s?ie=UTF8&keywords=0387498931&page=1&rh=n%3A283155%2Ck%3A0387498931
Il est question de la fonction totient ( = phi ) page 141 pour le premier et 156 pour le 2eme. Je ne vois pas de moyen de l'exploiter dans le cas présent.


Voir UBASIC
http://en.wikipedia.org/wiki/UBASIC
dans les examples annexes.
Je n'ai pas en mémoire un ex. calculant phi, mais il faut voir ainsi que dans les divers contributeurs extérieurs ( si l'on peut encore les trouver ).
UBASIC est stupéfiant d'efficacité.
Il faudra peut être un émulateur DOS pour Windows dans les versions récentes de Windows.
http://www.simtel.net/category/view/id/299
Dernière édition par Framboise le Lundi 21 Janvier 2013, 19:43, édité 2 fois.
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar Tyrtamos » Lundi 21 Janvier 2013, 19:02

Ça y est, j'ai trouvé!

J'ai utilisé la formule du chapitre "Calcul" de https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler.

Exemple:

n = 1000 ==> factorisation de n: 2*2*2*5*5*5. Donc (2**3)*(5**3)

phi = ((2-1)*(2**(3-1)))*((5-1)*(5**(3-1)))

Cela donne 400, comme le calcul avec le PGCD.

Par contre, le temps de calcul est quasiment celui de la factorisation, ce qui rend acceptable le traitement de nombres de 20 chiffres, voire un peu plus.

Merci rebouxo: c'était une très bonne idée!

Je laisse la question ouverte quelques temps au cas ou il y aurait d'autres idées. [je vais regarder la dernière réponse de Framboise]
Tyrtamos
Utilisateur
 
Messages: 5
Inscription: Lundi 04 Février 2008, 18:21
Statut actuel: Actif et salarié

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar rebouxo » Lundi 21 Janvier 2013, 23:46

Tyrtamos a écrit:Merci rebouxo: c'était une très bonne idée!


Bon, c'était ma bonne idée de 2013. Là, elle va être longue l'année. :D

Content de t'avoir aidé.

Olivier
A line is a point that went for a walk. Paul Klee
Par solidarité, pas de MP
rebouxo
Modérateur
 
Messages: 6785
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar Framboise » Lundi 21 Janvier 2013, 23:50

J'ai examiné plus en détail le cas UBASIC et ses exemples.
Je n'ai rien trouvé spécifiquement phi - totient.
Il y a quelques méthodes pro de factorization en facteurs premiers avec leurs sources que l'on peut visualiser et enregistrer en clair.
J'ai quelques autres idées en tête ( mais je ne sais plus dans quels livres pour le moment ) pour trouver des méthodes raccourcies avec un peu de chance ( en supposant que cela soit possible, j'ai des doutes ).

Faire une recherche Google avec : calculate totient

De nombreuses pages ( p 179 -> 292 ) sur la fonction Euler's totient dans:
http://www.amazon.com/Handbook-Number-Theory-II-v/dp/1402025467/ref=sr_1_1?ie=UTF8&qid=1358810471&sr=8-1&keywords=1402025467
mais je ne vois rien d'utilisable ici.
J'ai le virus des sciences, ça se soigne ?
Framboise
Téra-utilisateur
 
Messages: 1152
Inscription: Lundi 21 Mai 2007, 12:57
Localisation: Dordogne
Statut actuel: Post-bac | Doctorat

Re: Calcul rapide de l'indicatrice d'Euler?

Messagepar Tyrtamos » Mardi 22 Janvier 2013, 10:40

Bonjour,

Merci Framboise pour tes infos.

Avec ton 1er lien, j'ai pu voir que la factorisation par les courbes elliptiques était beaucoup plus rapide que la mienne (Pollard Rho).

Comme je programme sous Python, j'ai cherché un tel programme, et j'ai trouvé "pyecm" ici: http://pyecm.sourceforge.net/

En plus, pyecm prend en compte "gmpy" (gmp pour Python: https://code.google.com/p/gmpy/), ce qui accélère encore le calcul.

Résultat: la factorisation de nombres de 50 chiffres devient possible. Les temps sont cependant très variables: de 1/100 seconde à 2 minutes.

Un exemple parmi d'autres:

Code: Tout sélectionner
n: 72246402817940044518146621452190243406468182966594
facteurs: [2, 53, 275897, 2470377850810609610126811114846258369406117L]
phi= 35441503111416685347768427325764411552454828556672
temps: 0.470812526658


J'ai essayé avec des nombres plus grands, et ça se gâte un peu. Avec un nombre de 100 chiffres, le calcul peut durer plusieurs heures. Mais on trouve tout de même le bon résultat!

Exemple:

Code: Tout sélectionner
n: 4889955028678998228128809491538085572595354855300108148273587724116803436124655102599750654713732760
facteurs: [2, 2, 2, 3, 5, 6597077, 4237095154340510920759138421L, 1457819813970549253487394852302171194737418073501215543289792069L]
phi: 1303987809986252231195971347010584277335270571233197894972213295247954918867616467079226131914065920


Bon. Avec ça, je crois que j'arrive au bout de ma recherche, je ne trouverais pas mieux. Et heureusement: si j'arrivais à factoriser facilement des nombres de 600 chiffres, je casserais facilement le cryptage RSA, ce qui serait une catastrophe mondiale pour la sécurité des données...! Mais on en est encore très loin!

Merci à tous les 2!
Tyrtamos
Utilisateur
 
Messages: 5
Inscription: Lundi 04 Février 2008, 18:21
Statut actuel: Actif et salarié


Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Bing [Bot] et 1 invité