Faugères F4 ve F5 algoritmaları - Faugères F4 and F5 algorithms - Wikipedia

İçinde bilgisayar cebiri, Faugère F4 algoritması, tarafından Jean-Charles Faugère, hesaplar Gröbner temeli bir ideal çok değişkenli polinom halkası. Algoritma, aynı matematiksel ilkeleri kullanır. Buchberger algoritması, ancak birçok normal formu tek seferde genel olarak oluşturarak hesaplar seyrek matris ve indirgemeleri paralel olarak yapmak için hızlı doğrusal cebir kullanmak.

Faugère F5 algoritması ilk önce idealin bir çift jeneratör polinomunun Gröbner temelini hesaplar. Daha sonra, bu temeli, bir sonraki daha büyük temel için jeneratörlerin başlangıç ​​matrislerinin boyutunu azaltmak için kullanır:

Eğer Gönceki zaten hesaplanmış bir Gröbner temelidir (f2, …, fm) ve Gröbner temelini hesaplamak istiyoruz (f1) + Gönceki o zaman satırları olan matrisler oluşturacağız m f1 öyle ki m bir öğesinin baş terimiyle bölünemeyen bir tek terimlidir Gönceki.

Bu strateji, algoritmanın Faugère'nin dediği şeye dayalı olarak iki yeni kriter uygulamasına izin verir. imzalar polinomlar. Bu kriterler sayesinde algoritma, Gröbner bazlarını büyük bir ilgi çekici polinom sistemi sınıfı için hesaplayabilir. düzenli diziler, tek bir polinomu sıfıra kadar basitleştirmeden - Gröbner tabanlarını hesaplayan algoritmalarda en çok zaman alan işlem. Aynı zamanda çok sayıda düzenli olmayan sekans için de çok etkilidir.

Uygulamalar

Faugère F4 algoritması uygulandı


Faugère F5 algoritmasının çalışma sürümleri,[kaynak belirtilmeli ]

Başvurular

Önceden çözülemeyen "döngüsel 10" problemi F5 ile çözüldü,[kaynak belirtilmeli ] kriptografi ile ilgili birkaç sistem olduğu gibi; Örneğin HFE ve C*.[kaynak belirtilmeli ]

Referanslar

  1. ^ Eder, Hıristiyan (2008). "F5 Algoritmasının Kriterleri Üzerine". arXiv:0804.2033 [math.AC ].
  2. ^ https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms

Dış bağlantılar