Hoe kun je modulo rekenen met polynomen?

Voor mijn profielwerkstuk heb ik als onderwerp encryptie en ik ben nu AES aan het behandelen. Binaire waarden worden regelmatig als polynomen geschreven (tot zo ver snap ik het nog), maar nu wordt de volgende berekening gedaan:

X^13 + X^11 + X^9 + X^8 + X^6 + X^5 + X^4 + X^3 + 1

mod (X^8 + X^4 + X^3 + x + 1) = X^7 + X^6 + 1

Kan iemand mij uitleggen hoe het antwoord tot stand komt?

Weet jij het antwoord?

/2500

Het beste antwoord

Modulo rekenen is zoiets als delen met rest. Dat geldt voor getallen, maar polynomen kun je ook door elkaar delen, en ook die deling kan een rest hebben. Als we bij getallen delen met rest dan trekken we een geheel veelvoud van de deler af van het deeltal, net zolang totdat de rest kleiner is geworden dan de deler. Dat doen we nu ook met polynomen. We stoppen als de graad van de rest kleiner is dan de graad van de deler. In jouw voorbeeld willen we eerst van de x^13 af. We vermenigvuldigen de deler met x^5 en trekken die van het deeltal af. Het resultaat is een 11e-graads polynoom. Nu vermenigvuldigen we de deler met x^3 en trekken weer af. Het resultaat is -x^7-x^6+1. Dit is een 7e-graads polynoom en die van de deler is 8. We kunnen de graad van de rest dus niet nog kleiner maken. Mijn uitkomst is trouwens niet precies wat er in jouw voorbeeld wordt gegeven. We kunnen de uitkomst controleren door voor x een getal in te vullen. Als we X=2 kiezen worden de polynomen eigenlijk binaire getallen. Decimaal wordt het dan 11129 mod 283 = -191. En dat klopt want 11129-(40*283) = -191.

Stel zelf een vraag

Ben je op zoek naar het antwoord die ene vraag die je misschien al tijden achtervolgt?

/100