Analysis and implementation of binary polynomial multiplication

N. Koblitz ve V. Miller ilk olarak 1985 yılında eliptik eğri kriptografisi kavramını önerdiler. Eliptik eğri kriptografi, aynı güvenlik seviyesi için daha küçük anahtar boyutu kullanarak mevcut açık anahtar şifreleme sistemlerine göre avantaj sağladığı için açık anahtarlı şifreleme sistemleri arasında hızla popülerlik kazanmaktadır. Bu sistem, sonlu cisimlerde eliptik eğrilerin matematiksel özelliklerinden yararlanır. Eliptik eğri şifreleme sistemleri, eliptik eğriler üzerindeki noktalar üzerinde işlem gerçekleştirir. Eliptik eğriler, asal cisimler üzerinde temsil edilebilir ve ayrıca ikili cisimler üzerinde de temsil edilebilir. İkili cisim gösteriminde, sonlu cisim elemanları ikili cisimler üzerindeki polinomlardır. Polinom çarpımı, ikili cisim eliptik eğri kriptografik uygulamasında önemli bir işlemdir ve bu nedenle kriptografide bir ilgi alanıdır. Bu tezde, ikili cisimler üzerinde bazı polinom çarpma algoritmalarını analiz ediyoruz. 2-yollu algoritmalar için okul kitabı, Karatsuba ve rafine Karatsuba ve 3-yollu algoritmalar için okul kitabı, Karatsuba ve CNH 3-yollu bölünmüş algoritmaları inceliyoruz. Bir polinom çarpımı için en küçük hesaplama birimi olarak 64 bit'e 64 bit çarpmayı tanımlıyoruz ve bunu da kayan pencere yöntemiyle inceliyoruz. Bir zaman belleği değiş tokuşu yaklaşımı kullanarak en uygun pencere boyutunun sekiz olduğunu gözlemledik.