Factorielle allégée
dans Arithmétique
Bonjour,
la factorielle allégée
On note $(n!)_2$ la factorielle de n alléger de 2, qui est le produit des nombres entre 1 et n, à l'exception des nombres pairs.
Calculer :$(2^{77}!)_2 \mod 2^{101}$
PS : l'usage de la calculatrice est recommandée.
Bonne journée.
la factorielle allégée
On note $(n!)_2$ la factorielle de n alléger de 2, qui est le produit des nombres entre 1 et n, à l'exception des nombres pairs.
Calculer :$(2^{77}!)_2 \mod 2^{101}$
PS : l'usage de la calculatrice est recommandée.
Bonne journée.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$1045593516627615941359991749983$
De toutes les façons ce qui compte plus que le résultat c'est la méthode pour y arriver, donc si tu pouvais décrire ton algorithme en quelques mots cela serait mieux.
J'ai mal lu la factorielle. :-D
Merci.
En me basant sur ma conjecture, ça donne alors la valeur que j'ai postée.
Avant de donner ma solution (qui est simple), j'attends que ceux qui prétendent que cette exercice est classique, donne la solution classique.
A noter que par cette méthode on peut calculer des choses plus biscornues comme :
$(2^{77}!)_{2,3} \mod 2^{101}$ ou encore $\sum \limits_{i\in [0,2^k]} f^i(0) \mod 2^{101}$ avec $f$ un polynôme quelconque, avec $f^2(x)=f(f(x))$.
La seule limite semble être notre imagination ( : j'exagère un peu)
Gros classique
Merci.
J'attends d'avoir un lien vers ce classique ou qu'on explicite clairement le procédé et alors je donnerais la solution que je crois connaître.
Bonne journée.
C'est bien ce que je me disais...
Mais laissons un jour à ceux qui prétendent que cette énoncé est un classique, pour produire la réponse classique...
Passer ce délai je publierai, la solution que je crois connaître.
Bonne journée.
Je t'ai envoyé la réponse par MP.
Bonne journée.
On pose $P_{n}(X)=X(X+1)...(X+n-1)$ on a pour tout $k\in \Z$, $n!|P_n(k)$, et $104! \mod 2^{101}=0$.
Alors pour tout $k \in\Z_{2^{101}}$ $P_{104}(k) \mod 2^{101}=0$.
On travaille dans l'anneau $\Z_{2^{101}}$, alors on pose :
$R_0(X)=2X+1$
$R_{k+1}(X)=R_k(X)\times R_k(X+2^{k}) \mod P_{104}(X)$
On calcule $R_{76}(X) \mod P_{104}(X)$ et $R_{76}(0)=(2^{77})_2 \mod 2^{101}$.
Si vous avez des questions n'hésitaient pas.
Bonne journée.
Conséquence directe de Proposition 11.6.15 de Henri Cohen Number theory Vol.2
Signé: le troll
Quelqu'un peut-il nous dire ce qu'énoncerait cette proposition ?
Merci.
Non, personne ?
Même pas Joaopa ?
Bonne journée.
book
Il n'y a pas la p 374, partie 11.6.1.
Mais il parle de la fonction gamma sur les nombres p-adics donc approprie cela n'a qu'un rapport lointain avec la question initiale (calcul de la factorielle allégé).
Bonne journée.
En laissant de côté cette polémique avec Jaoapa, êtes vous d'accord pour qualifier de simple la solution proposée ?
PS : du coup c'est moi qui ait besoin de vos commentaires pour faire avancer mes recherches.
Bonne journée.
à noter qu'ainsi on peut construire un protocole d'échange de clef secrète.
Bonne soirée.
Oui, mais alors il ne serait pas sûr.
Bonne journée.
Un nouveau résultat sur la factorielle allégée : http://www.les-mathematiques.net/phorum/read.php?43,1198849,1349360#msg-1349360
Bonne journée.