Square and multiply < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:55 So 19.08.2012 | | Autor: | Blake512 |
| Aufgabe | | Explain why Fermat's little theorem doesn't hold for the square & multiply method. |
Also laut Fermat's little theorem gilt folgendes:
[mm] a^p \equiv [/mm] a (mod p)
und
[mm] a^{p-1} \equiv [/mm] 1 (mod p)
Wie bringe ich diese Gesetze nun in Zusammenhang mit der Square & multiply Methode? 1. Werden nicht nur Primzahlen als Exponent verwendet und 2. ist der Exponent nicht zwingend gleich dem Modulus.
Beispiel:
[mm] 6^{73} [/mm] mod 100 = ?
73 = 1 + [mm] 2^3 [/mm] + [mm] 2^6
[/mm]
[mm] 6^2 [/mm] = 36, [mm] 6^{2^2} [/mm] = [mm] 36^2 \equiv [/mm] −4, [mm] 6^{2^3} \equiv −4^2 \equiv [/mm] 16, [mm] 6^{2^4} \equiv 16^2 \equiv [/mm] 256 [mm] \equiv [/mm] 56, [mm] 6^{2^5} \equiv 56^2 \equiv [/mm] 36, [mm] 6^{2^6} \equiv [/mm] −4.
[mm] 6^{73} \equiv [/mm] 6 * [mm] 6^{2^3} [/mm] * [mm] 6^{2^6} \equiv [/mm] 6 * 16 * (−4) [mm] \equiv [/mm] 16
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:26 Mo 20.08.2012 | | Autor: | felixf |
Moin!
> Explain why Fermat's little theorem doesn't hold for the
> square & multiply method.
Das ist eine ziemlich komische Frage. Man kann Fermat's little theorem sehr wohl verwenden, um die Square-and-Multiply-Methode bei gross genugen Exponenten zu beschleunigen: will man [mm] $a^n \pmod{m}$ [/mm] bestimmen, mit $m$ prim, so kann man erst $n = (m - 1) [mm] \cdot [/mm] q + r$ schreiben mit $q, r [mm] \in \IZ$, [/mm] $0 [mm] \le [/mm] r < m - 1$ (Division mit Rest) und [mm] $a^n \equiv a^r \pmod{m}$ [/mm] verwenden (hier sollte $a [mm] \not\equiv [/mm] 0 [mm] \pmod{m}$ [/mm] sein, bzw. in dem Fall $m - 1 [mm] \nmid [/mm] n$ gelten, damit das Ergebnis 0 ist und nicht faelschlicherweise 1 :) ).
Falls $q = 0$ ist (d.h. $n < m - 1$), bringt das nichts. Ist aber $q > 0$ (also $n [mm] \ge [/mm] m - 1$), bringt es sehr wohl etwas.
> Also laut Fermat's little theorem gilt folgendes:
>
> [mm]a^p \equiv[/mm] a (mod p)
>
> und
>
> [mm]a^{p-1} \equiv[/mm] 1 (mod p)
Das zweitere gilt nur, falls $a [mm] \not\equiv [/mm] 0 [mm] \pmod{p}$ [/mm] gilt, also falls $a$ nicht durch $p$ teilbar ist.
> Wie bringe ich diese Gesetze nun in Zusammenhang mit der
> Square & multiply Methode? 1. Werden nicht nur Primzahlen
> als Exponent verwendet und 2. ist der Exponent nicht
> zwingend gleich dem Modulus.
Ich weiss nicht, was der Aufgabensteller mit der Frage bezweckt. Vielleicht will er, dass du 1. und/oder 2. erwaehnst. Ich finde die Formulierung zumindest nicht sonderlich hilfreich...
LG Felix
|
|
|
|
