[WI] Modulorekenen

[Hanneke]

Hoi, ik probeer drie rekenregels met modulo te berekenen, maar weet niet zeker of ik het goed doe. Ik ga uit van p mod q = p - nq

Eerste is p mod x + q mod x = (p+q) mod x:


Tweede is: p mod x * q mod x = p*q mod x:


Ben ik minder zeker van omdat de in de n dan ook p en q staat, maar op zich maakt dat niet uit, denk ik, omdat p en q wel gehele getallen zijn.

De derde die ik wilde doen is p^(q mod x) = (p^q) mod x. Deze weet ik niet zo goed hoe ik dat moet aanpakken omdat p^(q-nx) volgens mij niet makkelijk te herschrijven is.

[Hanneke]

Up

[ILUsion]

Hanneke schreef:

Up

Uppen mag helemaal niet

Ik heb je eerste twee berekeningen even nagekeken en hij komt wel goed uit, maar je hebt een tekenfout gemaakt. Niet dat dat iets uitmaakt in totaal, omdat je toch uiteindelijk dat stuk via je modulo wegwerkt op het einde.

Ik zou daar zelf ook al eerder geneigd zijn om p mod x te vervangen door p + nx in plaats van die p - nx (zo is je n positief in de meeste gevallen en heb je minder kans op tekenfouten).

Die laatste is wat moeilijker, het verste dat ik daarmee kom is het volgende (voor de modulo-operator gebruik ik een percentteken, dat wordt in programmeertalen meestal gedaan)


En als je van dat laatste weer de modulo neemt, krijg je

Dat zou willen zeggen dat het klopt als je die laatste factor op 1 kan brengen, maar ik weet niet of dat zomaar kan in een algemeen geval, en aan de hand van een voorbeeld kan je aantonen dat dat niet kan:
neem p = 5, q = 3, x = 2 en je krijgt:

[Hanneke]

ILUsion schreef:

Uppen mag helemaal niet

Ja, nou, ik moet toch morgen m'n pws gaan inleveren. En het helpt wel.

ILUsion schreef:

Die laatste is wat moeilijker, het verste dat ik daarmee kom is het volgende (voor de modulo-operator gebruik ik een percentteken, dat wordt in programmeertalen meestal gedaan)


En als je van dat laatste weer de modulo neemt, krijg je

Dat zou willen zeggen dat het klopt als je die laatste factor op 1 kan brengen, maar ik weet niet of dat zomaar kan in een algemeen geval, en aan de hand van een voorbeeld kan je aantonen dat dat niet kan:
neem p = 5, q = 3, x = 2 en je krijgt:

Maar 5 mod 2 is ook 1 Maar ik ga even kijken of ik hiermee verder kom!

Edit: het komt inderdaad niet altijd uit, hmm.
Bij RSA is één van de variabelen e, e is een eenheid in modulo (p-1)(q-1), oftewel ggd((p-1)(q-1),e) = 1. Verder is er f, ef = 1 mod (p-1)(q-1), daardoor geldt dat a^ef = a.
Dat werkt toch alleen als die p^(q mod x) = (p^q) mod x klopt?

[ILUsion]

5%2 = 1, maar dat staat ook nergens tegengesproken, tenzij je ergens ook weer een modulo van moet nemen.

Maar zoals ik al zei: die laatste eigenschap geldt enkel als je die tweede factor op 1 kan brengen. Ik weet iets te weinig van RSA af om je daar zo snel op te helpen (want ik weet niet waar al die variabelen gebruikt worden), maar zo op het eerste zicht kan ik uit je formules enkel beredeneren dat e en f vrij triviale getallen moeten worden (0 of 1) als je stelt dat ef = 1%(p-1)(q-1), dus daarvan zie ik niet direct het nut voor encryptie.

Mijn eigen denkwijze startte trouwens met de realisatie dat e < (p-1)(q-1), misschien dat die denkpiste je ergens brengt?

[Hanneke]

Ik ben er min of meer uit, geloof ik. Dankje.