Effektiv aritmetik i ändliga kroppar av liten udda karaktäristik

Abstrakt:

Vi studerar problemet att göra effektiva beräkningar (på binär hårdvara) i GF(p^n), där p är ett litet primtal skiljt från 2. Vissa primtal (t.ex. 3 och 5) av denna typ är av speciellt intresse i en del nya kryptosystem baserade på elliptiska kurvor. Utöver detta är problemet naturligtvis intressant ur ett rent teoretiskt perspektiv.

Huvudidén är att operera på flera element i GF(p) parallellt genom att stoppa dem i samma maskinord. Motsvarande knep i GF(2^n) är både välkänt och tacksamt, eftersom addition här motsvaras av XOR.

Vi ger övre gränser (samt ev. något handviftande argument om undre gränser) för hur mycket utrymme som behövs för varje GF(p)-element för att vi ska kunna operera på dem parallellt (d.v.s. väsentligen hur många vi kan klämma in i ett maskinord), och presenterar några prestandajämförelser från en faktisk implementation.