Bonjour.
J'aurai souhaité savoir si il existait une méthode (un algorithme) rapide pour tester la divisibilité de N=(2^n-1) par un nombre D (savoir si ((2^n-1)%D == 0)), (avec n et D des entiers 64 bits) dans l'idéal sans calculer explicitement N, mais en connaissant juste n (car N peut être très grand ici). Je ne sais pas si ça peut aider, mais en base 2, N s'écrit comme une suite de n "1".
Merci beaucoup
Il suffit de calculer 2n modulo D, puis de soustraire 1.
Les calculs de puissances sont classiques : par des élévations au carrés successives, on calcule rapidement 22, 24, 28, 216, ... modulo D.
L'écriture de n en base 2, fournit les puissances à utilise pour calculer 2n.
Par exemple : n=38 et D=7.
L'écriture de n en base 2 (100110) signifie que : n=32+4+2, donc que : 2n=232+4+2=232.24.22.
On calcule les puissances de 2 modulo 7 :
21=2
22=4
24=42=16=2
28=2=4
216=42=16=2
232=22=4
Et on confronte ces puissances aux chiffres de l'écriture de n en base 2.
Pour conclure que, modulo 7 : 2n=4.2.4=8.4=1.4=4 et 2n-1=3.
En fait tout est dans le "n entier 64 bits". Je cherche si il n'existe pas une astuce sans passer par le calcul effectif de 2^n. Si n vaut 100 milliard, 2^n ne passe bien entendu pas en mémoire... Du coup y aurait-il une méthode pour tester la divisibilité en connaissant juste n et D et sans passer par le calcul de 2^n ?
On ne calcule pas 2n, mais 2n modulo D : les calculs ne «gonflent» pas.
Du plus, si n s'écrit avec k chiffres en base 2, on ne calcule que k puissance de 2 modulo D.
Bonjour.
L'approche a l'air très intéressante mais je n'arrive pas très bien à saisir exactement l'agorithme que tu exposes; J'ai bien compris que la transition liée à ton dernier chiffre égal était un modulo 7, mais je ne saisis pas très bien d'où sort des fois ton premier signe égal :Il suffit de calculer 2n modulo D, puis de soustraire 1.
Les calculs de puissances sont classiques : par des élévations au carrés successives, on calcule rapidement 22, 24, 28, 216, ... modulo D.
L'écriture de n en base 2, fournit les puissances à utilise pour calculer 2n.
Par exemple : n=38 et D=7.
L'écriture de n en base 2 (100110) signifie que : n=32+4+2, donc que : 2n=232+4+2=232.24.22.
On calcule les puissances de 2 modulo 7 :
21=2
22=4
24=42=16=2
28=2=4
216=42=16=2
232=22=4
Merci beaucoup si tu (ou quelqu'un d'autre qui a bien saisi) prends le temps de réexpliquer ce passage28=2 ?
216=42 ?
232=22 ?
