Geçtiğimiz yıl, Lemire, iki sayının en büyük ortak bölenini (GCD) hesaplamak için ikili Öklid algoritması olarak da bilinen Stein algoritmasının optimize edilmiş bir varyasyonunu tanıttı. Bu algoritma, libc++ tarafından kullanılan sınıfının en iyisi bir uygulama olarak öne çıkıyor. Ancak Lemire, modüler çarpımsal tersini hesaplamak için kullanılan genişletilmiş Öklid algoritmasının ikili versiyonunun daha karmaşık olduğunu ve genel amaçlı registerlara sığan tam sayılarla çalışırken yüksek hızda uygulanamadığını belirtmişti. Bu durum, algoritmanın daha fazla optimize edilmesi gerektiği yönünde bir beklenti yaratmıştı.
Bu makale, genişletilmiş Öklid algoritmasının benzer şekilde optimize edilebileceğini ve bu konudaki temel fikirlerin 2020 tarihli bir makalede zaten tanımlandığını vurguluyor. Yazar, bu makalenin genellikle sabit zamanlı değerlendirme ve uzun aritmetik üzerine odaklandığı için gözden kaçtığını düşünüyor. Yazar, bu yazıyla "genişletilmiş Stein algoritmasına" hak ettiği değeri vermeyi amaçlıyor. Kendi Rust tabanlı modüler aritmetik kütüphanesinin bir parçası olarak sunduğu implementasyonun, klasik Öklid algoritmasına kıyasla önemli performans iyileştirmeleri sağladığını gösteriyor.
Yazar, kesin performans iddialarında bulunmaktan kaçınsa da, sunduğu ham veriler, algoritmanın 8 bitten 64 bite kadar farklı tam sayı boyutlarında %20 ila %56 arasında daha hızlı çalıştığını ortaya koyuyor. Bu iyileşmeler, özellikle modüler ters hesaplamalarının yoğun olduğu kriptografi ve benzeri alanlarda büyük önem taşıyor. Makale, algoritmanın çalışma prensiplerini, sınırlamalarını, Pornin'in makalesine kıyasla yapılan optimizasyonları ve gelecekteki potansiyel iyileştirmeleri detaylandırıyor.
Modüler aritmetik işlemlerinde kritik bir yere sahip olan modüler ters alma algoritmasının performansı, yeni optimizasyonlarla önemli ölçüde artırıldı.