Accelerated modular inverse algorithm for multidigit integers

Abstract

Bu tez, yeni model Intel işlemciler üzerinde bulunan AVX2 yönergeleri kullanılarak sağdan sola çok basamaklı küçültme yöntemiyle uygulanan modüler çarpımsal ters alma hesaplamasını SIMD paralel şekilde geliştirilmesini amaçlamaktadır. Euclid in genişletilmiş GCD metodu hem GCD yi hem de modüler ters almayı hesaplayan iyi bilinen bir yöntemdir. Bu yöntemle yazılan binary XGCD algoritmaları, çarpma operasyonu yerine kaydırma operasyonu kullandığı için bilgisayar mimarisinde hızlı algoritmalardır. Binary XGCD algoritmasının genelleştirilmiş hali, ilk kez Lehmer tarafından yazılmıştır. Bu algoritma, sayıları bit seyivesi yerine soldan sağa basamak seviyesinde küçültür, bu da algoritmayı büyük sayılar için hızlı bir yöntem haline getirir. Jebelean ve Weber tarafından sunulan genelleştirilmiş GCD algoritması da aynı işlemi tersten sağdan sola gerçekleştirmektedir. Bu method ise zaman içerisinde farklı araştırmacılar tarafından geliştirilmiş ve sonunda daha etkili hale getirilmiştir. Tüm bu algoritmalar, Euclid in invaryant denklemlerini birbirinden bağımsız ama benzer şekilde ve aynı operasyonlarla işlemektedir, bu da SIMD paralelleştirme için oldukça uygundur. Bu tezde, bu algoritmanın modular çarpımsal ters alma versiyonu geliştirildi. Bu algoritmanın ana döngüsü başarılı bir şekilde SIMD paralel hale getirildi ve alt fonksiyonlar kısmen paralelleştirildi. %Bu yaklaşımın gelecek mimarilerde daha hızlı sonuçlara ulaşacağı öngörülmektedir.

In this thesis, a multi-digit modular multiplicative inverse algorithm has been aimed to SIMD parallelized by utilizing AVX2 instructions which are commonly encountered on new generation Intel processors. Euclid's extended GCD approach is an well known method which also computes modular inverse and GCD together. Binary XGCD algorithms based upon this technique are quite fast in computer architecture since they only use shifting operations instead of multiplication. Generalized version of binary XGCD algorithm was firstly introduced by Lehmer. It reduces the numbers in digit level instead of bits, from left to right which makes the algorithm fast for large numbers. The accelerated GCD algorithm proposed by Jebelean and Weber also realized the same operation in reverse direction; from right to left. Their method has been improved by some other researchers, and eventually became more efficient. In all of these algorithms process Euclid's invariant equations the distinct data in similar way and by same operation, naturally convenient for SIMD parallelization. In this thesis, the modular multiplicative inverse version of this algorithm is developed. The fundamental part of this algorithm has been SIMD parallelized successfully and the sub-functions have been parallelized partially.