Hjelp ved bruk av Euklids algoritme?

[luringen]

Ok. Nydelig. Men da kommer jeg bare til problemet med å løse det siste i oppgaven.

[tex]M=C^d(modN)[/tex]
N=247
C=155
og d fant vi ut var lik=59

Problemet så blir å regne ut:

[tex]M=155^{59}(mod247)[/tex]

Regnearket klarer ikke å opperere med så store tall. Den sier at det blir 0 samme hva. Bruker forresten Googles regneark. Vet også at det finnes en snarvei for å regne eksponentialfunksjoner i modulær matematikk, men får det ikke helt til...

Setter stor pris om det er hjelp å få med det også

[luringen]

155^59=1696563784104931393981670964548250698156775439985739937013036903705334724751300382238178125759997527666200767271220684051513671875

Ihvertfall.

[luringen]

Ok da har jeg fått regnet det ut med to forskjellige programmer, og svaret ble 90, som var det jeg håpet på, pga det var verdien jeg startet med før jeg krypterte den med RSA. Takk for all hjelp, nå er alt i boks

[daofeishi]

Trikset her er at du kan bytte ut et tall med dens ekvivalent modulo N.

[tex]M \equiv 155^{59} \equiv 155\cdot(155^2)^{29} \ \pmod {247}[/tex]

[tex]155^2 \equiv 66 \ \pmod{247}[/tex]

Derfor:

[tex]M \equiv 155\cdot 66^{29} \equiv 155\cdot 66 \cdot(66^2)^{14} \equiv 103 \cdot (66^2)^{14} \equiv 103 \cdot (157)^{14} \equiv 103 \cdot (157^2)^7 \equiv 103 \cdot 196^7 \equiv ... \equiv 129 \ \pmod{247}[/tex]