Forum de mathématiques - Bibm@th.net

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Periode [Résolu]

Bonjour á tous,

Je suis confronté á un problème,
Je voudrais determiner le nombre de termes qui composent la periodicitée de la fonction f(x)=2^r (mod N) avec r=r+1

Exemple:

2^r (mod 21) = {1,2,4,8,16,11}
Avec 6 termes.

Comment trouver directement 6, uniquement á partir de la fonction?

Merci beaucoup

++

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Periode [Résolu]

Bonjour,

  D'abord, je n'ai pas compris dans ton message "avec r=r+1".
Ensuite, je peux te dire que c'est un problème compliqué....et je ne suis même pas sûr que l'on sache le faire.
Ce que je sais :
*on commence par calculer le nombre d'entiers compris entre 1 et N qui sont premiers avec N.
C'est ce qu'on appelle l'indicateur d'Euler. Dans ton cas, il vaut 2x6=12.

*On sait que la période de ta fonction (on appelle cela l'ordre de 2 dans le groupe (Z/21Z)^* quand on sait plus de choses...) va diviser cet entier (c'est le théorème de Lagrange.

Donc ici, on est sûr que la période est 1,2,3,4,6 ou 12.

Fred.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Periode [Résolu]

Bonjour jeune homme,

Il y a retour à la case départ lorsque 2^r = k*n+1, autrement dit lorsque 2^r = 1 (mod n).
2^r doit être un multiple de n, plus 1.
Le r minimum est atteint pour 2^r = n+1, doit pour r ln 2 = ln(n+1)  ou encore pour r = ln(n+1)/ln(2)...
Je n'ai pas encore trouvé pour l'instant de périodicité pour la périodicité, ni d'autre méthode que la force brute pour déterminer ta périodicité, si ce n'est que pour certains n premiers la période est n-1 :
  3 -->  2
11 --> 10
13 --> 12
19 --> 18
29 --> 28
37 --> 36
53 --> 52
59 --> 58
61 --> 60
67 --> 66

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from math import log

maxi=1003                   # limite de la boucle = maxi - 2

for n in range(3,maxi,2):   # boucle de nombres impairs de 3 à maxi-2
    r=int(log(n+1)/log(2))
    while 2**r%n!=1:
        r+=1
    print "Pour n =",n,"la période est r =",r

Pour n = 3 la période est r = 2
Pour n = 5 la période est r = 4
Pour n = 7 la période est r = 3
Pour n = 9 la période est r = 6
Pour n = 11 la période est r = 10
Pour n = 13 la période est r = 12
Pour n = 15 la période est r = 4
Pour n = 17 la période est r = 8
Pour n = 19 la période est r = 18
Pour n = 21 la période est r = 6
Pour n = 23 la période est r = 11
Pour n = 25 la période est r = 20
Pour n = 27 la période est r = 18
Pour n = 29 la période est r = 28
Pour n = 31 la période est r = 5
Pour n = 33 la période est r = 10
Pour n = 35 la période est r = 12
Pour n = 37 la période est r = 36
Pour n = 39 la période est r = 12
Pour n = 41 la période est r = 20
Pour n = 43 la période est r = 14
Pour n = 45 la période est r = 12
Pour n = 47 la période est r = 23
Pour n = 49 la période est r = 21
Pour n = 51 la période est r = 8
Pour n = 53 la période est r = 52
Pour n = 55 la période est r = 20
Pour n = 57 la période est r = 18
Pour n = 59 la période est r = 58
Pour n = 61 la période est r = 60
Pour n = 63 la période est r = 6
Pour n = 65 la période est r = 12
Pour n = 67 la période est r = 66

@+

[EDIT] Grillé par Fred dont je vais examiner soigneusement la réponse...

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Periode [Résolu]

Hey!

Fred, je pige pas pourquoi tu dis qu'on est  sur que la periode es de 1,2,3,4,6 ou 12. Ces nombres ne divisent pas 21 pourtant..

Yoshi, Si je comprend bien la signification de r minimum, il ya un moyen beaucoup plus simple que ln(n+1)/ln(2)  de le trouver.. log en base 2 de n. Si le r minimum c'est pas ça, reexplique moi!

++

Ps. Merci pour le code, c'est exactement ce qu'il me fallait.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Periode [Résolu]

Salut,

  Je n'ai jamais dit que ces nombres divisaient 21, j'ai simplement dit qu'ils divisaient 12.
Car 12 est l'indicateur d'Euler de 21, c'est-à-dire le nombre d'entiers premiers avec 21 et qui sont plus petits que 21.
Je me suis un peu renseigné sur ton problème, et effectivement la réponse est qu'on ne sait pas. Une célèbre conjecture en mathématiques, la conjecture d'Artin, qui date du début du XXiè siècle, dit que pour une infinité de nombres premiers p, la "période" comme tu l'appelles de 2 sera p-1. Mais on ne sait toujours pas si cette conjecture est vraie.

Fred.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Periode [Résolu]

Bonjour,

Le problème est que j'ignore s'il existe, en Python, d'autres log que le népérien classique et que leur documentation est une vraie jungle... !!!

[EDIT] J'ai trouvé (google) : remplacer log(n+1)/log(2) par log(n+1,2). Pas de quoi fouetter un chat ! Bon, c'est peut-être plus facile à lire, parce qu'en temps de calcul ça doit être kif-kif...

@ Fred : je vois que j'ai rejoint la conjecture d'Artin.
Pour l'infirmer, il faudrait donc prouver qu'il n'existe qu'un nombre fini de nombres premiers p dont la période est p-1 ?
Alors là, bonjour...

@+

Dernière modification par yoshi (28-11-2008 16:48:16)

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Periode [Résolu]

Hello,

Yoshi, je n'ai pas compris la 2eme ligne de code (while 2**r%n!==1:)
pourquoi n!...?

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 404

Re : Periode [Résolu]

RE,

while 2**r%n!=1:
Signifie : tant que le reste de 2^r dans la division par n est différent de 1.
!=    --> différent de

@+

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Periode [Résolu]

Re,

Ha ok! Honte á moi!, j'ai cru n factorielle..

++