Bonjour,
Pour mes TPE, je dois calculer d tel que 5d1 [4992]. Je ne sais pas du tout comment faire...
Aussi, je dois calculer 7551997 mais ma calculatrice ou le tableur de l'ordi n'est pas assez puissant. Comment puis-je trouver le résultat, du coup ?
Merci d'avance pour vos réponses.
Va faire un petit tour sur mon tpe sur la cryptographie, tu y trouvera la réponse à la première question dans les démonstrations à la fin de la partie sur RSA, et la réponse à la première dans la partie sur les nombres premiers, section test de Fermat.
Eric (l'adresse est dans ma signature)
5d = 1 [4992]Envoyé par Antikhippe
Bonjour,
Pour mes TPE, je dois calculer d tel que 5d
Aussi, je dois calculer 7551997 mais ma calculatrice ou le tableur de l'ordi n'est pas assez puissant. Comment puis-je trouver le résultat, du coup ?
Merci d'avance pour vos réponses.
ssi 4492 divise 5d-1
ssi 5d-1 = 4492k (k entier relatif)
ssi 5d - 4492k = 1
5 et 4492 sont premiers entre eux : relation de Bézout, donc il existe des solutions pour d et k.
On applique l'algorithme d'euclide pour trouver un couple solution
4492 = 898 * 5 + 2
5 = 2 * 2 + 1
donc 2 = 4492 - 898*5
donc 5 - (4492 - 898*5) * 2 = 1
donc 5 - 2*4492 + 898*5*2 = 1
donc 5*(1+898*2) - 2 * 4492 = 1
donc 1797 * 5 - 4492 * 2 = 1
donc 5d - 4492k = 1
ssi 5d - 4492k = 1797 * 5 - 4492 * 2 = 1
ssi 5(d-1797) = 4492(k-2)
5 et 4492 sont premiers entre eux, donc d'après le Lemme de Gauss :
5(d-1797) = 4492(k-2)
ssi 4492 divise d-1797
ssi d-1797 = 4492k' (k' entier relatif)
ssi d = 4492k' + 1797
Donc d = 1 [4492]
ssi d = 4492k' + 1797 pour tout k' entier relatif
Dernière modification par g_h ; 02/01/2005 à 18h35.
Et pour 755^1997 :
(mais jvois pas ce que tu vas en faire ! lol)
755^1997 = 181996234901766537383490800567 742353725793878614820191067922 260441760231652868\
609331584924932863307180170728 631395121992383369175936889726 732560621706666743\
864727514345318304384790557362 324801290440941300934670623007 731287724334737551\
374635191190078202367578584429 841649766253445049223500076259 756934000925811098\
633526138916587377531420501674 732057580565077064624150109006 853872773403382861\
237323209068604423992185568283 534612568029603808421512766210 442700904029509542\
438084275579672541376164633761 578281621719470117848026299547 527484795133300072\
162349072113979709573927903054 159178113591791369450389264807 854346007713879692\
952694973293775954897173724350 453229362480922347030400547650 032415336837308239\
759603466441955002625305355705 114120032739312429609037779003 464519870008455370\
503371790252789615266205190288 310716546886214471266013857069 463254224446510220\
180364980728002480130317654004 849612977669631113323911986436 563024379956462381\
425005281191226779939334206465 490772154742644282378150106568 448105043056690154\
250756301958931252604003519063 013140539159721147865717512064 787810871802454489\
545378242078099862368530436196 908938848425079975289421015193 398635312616972697\
527085645488312469405582151198 091809636630360875454188059100 752052036464640640\
447399903959795863980106678391 307563962220244567224224892724 878602776169424442\
203404430734831722123739263941 699876983571614499206496602412 071336833705760572\
844641304958970915227782891562 595620188678377531250209035103 310947192426743943\
044374788392618057660061502813 416160456500472756336071632494 602890537282274114\
622180512667234641089765821127 113650153355255342241883359915 312784464436511688\
325582347165178321988697301371 403082961448479776900032228255 045304971923052472\
930785504985801359342902574780 822858341909728635767994819302 828241629001516266\
184468452501535892768618604834 675573835615958799837221984100 225406753290908570\
480624591872715785703307061955 459578694501640415269502459784 197035534621849592\
721413568159351217409168042486 595461882996801384377636064885 411626141543412299\
287413266688244037503480096304 346375582874793724164614370207 515910716728885010\
462303089070610797079797736615 431568755182408721586092157316 810633833834204115\
495107598863800047220109984386 184240792796485734004938669240 205032293019771388\
022853809791934447508102843118 967653389648097974569459067275 536409508546941181\
398802916698029201034551748719 000651220744629211564131813842 911257224774045790\
004368073245579664142062038159 959975747306417577311433703085 180044064825402677\
269750366587888741779351537573 405519475783261887243914984379 511872367477053571\
891349617979686571068859142492 616475645166335376358493853520 902062719099269140\
319557391082185499102805872296 314475793689537752157194758255 598213470241505943\
559639891356347366820842680542 827936591246801295315939203517 533312391692322429\
260728890539094254935436280982 104611584727010808751940189243 902400362814773551\
291442653202928811753872947478 889325757919613358749280509736 597327041167545875\
913676198366394488786350636060 631357768667202071052187786777 802951377871750129\
460831515596023231334416736389 165342008338297394876053616362 250545040227861961\
727842419547108715420868517834 665571605039243560502954997967 089103394161294025\
940972397069875225919635746528 796061057423324318930968632493 818890015113473205\
919498726912819524552890971049 668236031498810115495022702894 089776869588754963\
111788384781701211910894502296 615338579319554704845242382018 104509688807156916\
489825015839941862902301079461 371029905715548622363236100436 120112996231964330\
995640448169833632725718586320 434964048640513655354051959825 341890929263013003\
157639626654932574834649063980 829483298724797896936582760780 942405366825068310\
561076537395081243832821361495 629353440711417442414198124870 158159943271732199\
680212422372939924398836115502 567728780805932687949714963686 570312109275623763\
548638851410583725757847811624 318532823933989948599561303130 242925788287205824\
528402625225098022689474699267 738673366401034777470050656222 065093523577725565\
871442702320967530298477173281 063487033027438658797686864185 827124599942281447\
938632416657504946624160848874 599658147482908635749797403947 476595793618282136\
180713931802984377952169919449 819639136883807172455429232818 615664581508454714\
542731486570718664931246656549 716081905260392337190461313710 317367804925492917\
955467201505520151565841723457 544600145453558786547842468796 406981428483370968\
692336977500053249686038650605 890737516281650462044495039606 714409983744984195\
464274725915030472955425295117 464831310298945663555507143494 010604640391844319\
394427132094102531895504320011 875241209286602129919844796188 487606182538086792\
868367128076262945120533746676 264074699060891197924099617572 169541104182901369\
186203738807082416087282626025 052713227055332367566035609254 593810658152088156\
647115321709410025889775581440 110759571249281211642147702179 536155045845405293\
885261249712690199005089251785 419435151665295755284100839469 184670180501698269\
289910511069152123497614502540 124151705371591042855922961223 691527557919372025\
520006826376017906574612152300 999372466445738445771710815116 496024973081459833\
400494854003343800467538085378 687846391780716815449004520714 834705811761598543\
413876185515648123243980400415 945803433522969611718474211465 991056505181250788\
051043215122545141382503577154 686787869527261131647024177628 802013573908856634\
908588617778125044968642244299 602063894924167628014235475785 733486160611125299\
107166275451458467130577857958 376875969585449873503375708619 919716695671739341\
432460041246245681217921599754 689862964245937860408541250050 810065219290919043\
739467198798162970684696714529 479249399641871838243144882989 076784087246620125\
057129183174799526511344240760 010133982247547229417816178293 870602304849121945\
699566145720864340784572732445 667497813701629638671875
Bouh, tu m'as précédé! Il ne me manquait plus que quelques multiplications!
lol ! Oui, je suis assez fort en calcul mental comme tu peux le voir
Au fait, dans mon premier message à la fin, j'ai écrit
d = 1 [4492]
ssi d = 4492k' + 1797 pour tout k' entier relatif
Je voulais bien sur écrire
5d = 1 [4492] <= il manquait le 5
ssi d = 4492k' + 1797 pour tout k' entier relatif
Ouah que je suis bête, j'ai pris 4492 et pas 4992 !
Reprenons à 0 alors :
5d = 1 [4992]
ssi 5d - 4992k = 1
4992 = 5 * 998 + 2
5 = 2*2 + 1
d'où 1 = 5 - 2*2
donc 1 = 5 - 2*(4992-5*998)
donc 1 = 5 - 2*4992 + 5*1996
donc 1 = 5*1997 - 2*4992
donc :
5d = 1 [4992]
ssi 5d - 4992k = 5*1997 - 2*4992
ssi 5(d-1997) = 4992(k-2)
Et d'après Gauss :
ssi 4992 divise d-1997
ssi d = 4992k' + 1997 pour tout k' entier relatif
Donc 5d = 1 [4992]
ssi d = 4992k' + 1997 pour tout k' entier relatif
Voilà, désolé pour le dérangement occasionné... !
Surtout pas !!! Merci énormément pour tout ce que tu as fait et merci aussi à Eric78 pour son lien...
J'ai juste une petite question, g_h : comment tu as fait pour calculer
7551997 ??? C'est pour le RSA, au passage...
De rien
Pour calculer 755^1997 j'ai utilisé le logiciel Mathematica.
Sinon, maintenant que j'y pense tu peux aussi le calculer sur http://www.quickmath.com
Tu vas dans le menu Expand (par exemple) tu tapes 755^1997, tu cliques sur Expand, et voilà !
Heu, c'est bien joli mathématica, mais cela masque completement le problème qui peut être interressant, surtout dans le cas de RSA: la c'était encore gentil avec un exposant de 4 chiffres, mais dans la réalité, les exposants font... plus de 100 chiffres. Si l'on procède en faisant des multiplications basiques, cela prend juste quelque millions d'annéesPour faire cela dans un temps raisonnable, il faut effectuer une exponentiation rapide qui -encore une fois- est expliqué dans mon TPE.
Oui, mais je manipule le RSA en miniature pour ne pas barber les profs avec de grands calculs avec de grands chiffres !
Au fait, t'as eu combien aux TPE, parce que ton site est vraiment très bien fait...
Ouep, ça sent la bonne note !
(tiens, moi aussi je fais un TPE sur la crypto cette année... oral jeudi)
C'est pour ça que t'es calé sur le sujet !
Moi, je passe demain !!!
Ha non, jfais ça en spé maths !
Pour mon TPE je fais un exposé sur la stéganographie, rien de bien compliqué !
Bon courage
T'as fait un site ? Y a beaucoup de maths avec la stéganographie ? Bon courage à toi aussi !Ha non, jfais ça en spé maths !
Pour mon TPE je fais un exposé sur la stéganographie, rien de bien compliqué !
Bon courage
C'est quoi la différence entre "Expression" et "Result" ???De rien
Sinon, maintenant que j'y pense tu peux aussi le calculer sur http://www.quickmath.com
Tu vas dans le menu Expand (par exemple) tu tapes 755^1997, tu cliques sur Expand, et voilà !
C'est bon, j'ai compris...
En revanche, j'aimerais calculer le nombre B tel que B
Je le fais faire par quickmath, mais il me dit qu'il ne peut pas trouver le résultat parce que le "modulo" (qui est ici 5141) n'est pas un nombre premier.
http://www.hostsrv.com/webmab/app1/M...advanced#reply
Comment puis-je régler le problème ? Un module n'est pas obligatoirement un nombre premier !!!
En partant du fait que tu es sensé pouvoir calculer 5141², c'est assez facile mais long :
Tu calcules à quoi est congru 2321²
puis 2321^4 (à partir du résultat précédent ! tu l'éleves au carré et tu te ramènes modulo 5141, et tu procèdes comme ça pour la suite)
puis 2321^8
puis 2321^16
32, 64, 128, 256, 512, 1024
Tu te débrouilles pour approcher 1997 avec ces puissances de 2
car 1997 = 1024 + 512 + 256 + 128 + 64 + 8 + 4 + 1
En multipliant les congruences utiles et en les réduisant modulo 5141 à chaque calcul intermédiaire ça te fait des calculs faisables (longs, c'est vrai)
Bref, en trichant (j'ai pas trop envie de faire le calcul...), on trouve
5141((2321^1997)/5141 - Floor[(2321^1997)/5141]) = 10
Donc 2321^1997 = 10 [5141]
Donc en fait tu cherches bêtement à résoudre
B=10 [5141]
là c'est facile, ssi B = 5141k + 10, pour tout k entier relatif
Sinon, non, j'ai pas fait de site, et ya pas du tout de maths pour la stéganographie (à part pour multiplier des pixels)
Dernière modification par g_h ; 03/01/2005 à 16h53.
comment enter pi, e..??De rien
Pour calculer 755^1997 j'ai utilisé le logiciel Mathematica.
Sinon, maintenant que j'y pense tu peux aussi le calculer sur http://www.quickmath.com
Tu vas dans le menu Expand (par exemple) tu tapes 755^1997, tu cliques sur Expand, et voilà !
je fais pi au carré puis expand...
ça me répond pi au carré et non pas la valeur numérique !!
idem pour les log, sin ... ???
dans mathematiqua comment faire apparaitre et utiliser les valeurs nuneriques de e, pi, sin, log...???
merci
Utilise la fonction N[.]
