Geçtiğimiz yıl Lemire, iki sayının en büyük ortak bölenini hesaplamak için optimize edilmiş bir Öklid algoritması varyasyonu olan ikili Öklid algoritması veya Stein algoritması hakkında yazmıştı. Bu çalışma, modüler çarpımsal tersini hesaplamak için sıklıkla kullanılan Genişletilmiş Öklid algoritmasının da benzer şekilde optimize edilebileceği fikrini ortaya koydu. Ancak, Genişletilmiş Öklid algoritmasının ikili versiyonunun (Genişletilmiş Stein algoritması) genel amaçlı yazmaçlarda yüksek hızda uygulanmasının zor olduğu düşünülüyordu.
Bu makale, Genişletilmiş Öklid algoritmasının da benzer bir şekilde optimize edilebileceğini ve bu konudaki temel fikirlerin 2020 tarihli bir makalede zaten açıklanmış olduğunu vurguluyor. Yazar, bu makalenin sabit zamanlı değerlendirme ve uzun aritmetiğe odaklanması nedeniyle gözden kaçmış olabileceğini belirtiyor. Kendi Rust tabanlı modüler aritmetik kütüphanesinde sunduğu Genişletilmiş Stein algoritması uygulamasıyla, standart Öklid algoritmasına kıyasla önemli performans artışları elde ettiğini gösteriyor.
Yazar, benchmark sonuçlarının derleyici, sürüm, optimizasyon bayrakları ve mikro mimari gibi faktörlerden etkilendiğini belirtse de, sunduğu ham veriler optimizasyonun etkinliğini açıkça ortaya koyuyor. 8 bitten 64 bite kadar farklı bit boyutlarında ve çeşitli işlemci mimarilerinde (Haswell, Alder Lake, Zen 5) yapılan testlerde, Genişletilmiş Stein algoritmasının standart Öklid algoritmasından %20 ila %56 oranında daha hızlı çalıştığı gözlemlenmiştir. Bu çalışma, modüler ters alma işlemlerinde pratik ve daha hızlı çözümler sunarak kriptografi ve diğer sayı teorisi tabanlı uygulamalar için önemli bir gelişme vadediyor.
Modüler ters alma işlemlerinin hızlandırılması, kriptografi ve sayı teorisi tabanlı uygulamaların performansını önemli ölçüde artırabilir.