Accelerated modular inverse algorithm for multidigit integers
Çok basamaklı sayılar için hızlandırılmış modüler ters alma algoritması
- Tez No: 573944
- Danışmanlar: YRD. DOÇ. DR. HÜSEYİN HIŞIL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Yaşar Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 60
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Hardware implementation of the post-quantum cryptography algorithm falcon
Kuantum sonrası kriptografi algoritması falcon'un donanım gerçeklemesi
YASİN YILMAZ
Yüksek Lisans
İngilizce
2025
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
- PusOS: An operating system approach in supervisor mode forfog computing
PusOS: Sis bilişim için süpervizör modunda bir işletim sistemi yaklaşımı
MUHAMMED NUMAN İNCE
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAkdeniz ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MELİH GÜNAY
- Weight reduction on the semi trailer chassis by using ultra high strength steel (UHSS) instead of metal material
Yarı römork şasisinde metal malzeme yerine ultra yüksek mukavemetli çelik (UHSS) kullanarak ağırlık azaltımı
TANVER TALAS
Yüksek Lisans
İngilizce
2024
Otomotiv MühendisliğiÇukurova ÜniversitesiOtomotiv Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA ÖZCANLI
- Sensor properties of phthalocyanine based hybrid materials containing metal organic framework structures against organic volatile compounds
Ftalosiyanin temelli metal organik kafes yaplar içeren hibrit malzemelerin organik uçucu bileşiklere karşı sensör özellikleri
MELİKE ATAŞ
Yüksek Lisans
Türkçe
2025
KimyaGebze Teknik ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. AYŞE GÜL GÜREK
DOÇ. DR. İLKE GÜROL
- Hierarchical NTT architectures on FPGA
FPGA üzerinde hiyerarşik STD yapıları
EMRE KOÇER
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAY SAVAŞ