Kinesisk restsætning

Her er nogle eksempler:

Den kan give mere effektive beregninger a^n mod m.

Fermats lille sætning kan udvides til a^phi(n) mod n = 1 hvis a er invertibel i restklassen modulo n. Den kinetiske restsætning kan bruges til bevis for dette.

Den kan bruges til at sætte en grænse for hvor mange primtal, der skal testes for i Rabin Miller testen. (se svar på primtal, fra tidligere)

#1 Tak. Er Rabin Miller testen ikke meget svær?

nej, tværtimod

#3 Den er ikke nævnt i min bog?

Jeg har den selv i nogle noter, som ikke er sådan lige til at få fat i.
Desuden har jeg set den omtalt i en bog for gymnasiet om offentlige hemmelige koder; men jeg kan desværre hverken huske forfatter eller titel. Du kan da prøve om en bibliotekar ikke kan finde den frem.

Den er ellers baseret på:

1) Fermats lille sætning
2) x^2 mod p = 1 <-> x = 1 mod p eller x = -1 mod p
3) a^n = a^[2*(n/2)] = [a^(n/2)^2

anvender du skiftevis 3) og 2) på 1) får du

a^(p-1) = 1 mod p <-> [a^(p-1)/2]^2 = 1 mod p <->
a^(p-1)/2 = 1 mod p eller a^(p-1)/2 = -1 mod p

hvis (p-1)/2 er lige kan du fortsætte brugen af 2) og 3).

2) kan vises således x^2 = 1 mod p <-> x^2-1 = 0 mod p

<-> (x-1)*(x+1) = 0 mod p <-> x-1 = 0 mod p eller x+1 = 0 mod p.

NB sidste <-> gælder kun hvis p er et primtal.

PS flere af de steder hvor der står = burder der stå ævivalent tegn; men jeg ved ikke hvordan jeg skal skrive det.