Algorytm Evdokimova

W obliczeniowej teorii liczb algorytm Evdokimova , nazwany na cześć Siergieja Evdokimova , jest asymptotycznie najszybszym znanym algorytmem faktoryzacji wielomianów (do 2019 r. ^{[ potrzebne źródło ]} ). Może rozłożyć na czynniki wielomian z jedną zmienną $stopnia$ $nad$ podanym polem liczności . Zakładając uogólnioną hipotezę Riemanna, algorytm działa w czasie deterministycznym ${\ Displaystyle (n ^ {\ log n} \ log q) ^ {{\ mathcal {O}} (1 )}}$ (patrz notacja Big O ). Jest to ulepszenie zarówno algorytmu Berlekampa, $jak$ i algorytmu Rónyai w tym sensie, że pierwszy algorytm jest wielomianem dla małej charakterystyki pola, podczas gdy drugi jest wielomianem dla ; jednak oba z nich są wykładnicze, jeśli nie ma żadnych ograniczeń.

Faktoryzacja wielomianu $}$ polu podłoża jest zredukowana do przypadku, gdy nie ma wielokrotnych $pierwiastków$ i jest całkowicie podzielony na $\ displaystyle k}$ $displaystyle k$ (tj. ${\ displaystyle f}$ ma $displaystyle$ korzenie w $k}$ ). Aby znaleźć pierwiastek z $w$ $($ $zajmuje$ wielomianami nie tylko nad polem podstawowym, ale nad całkowicie podzieloną półprostą algebrą przykład takiej algebry podaje ${\ Displaystyle k [X] / (f) = k [A]}$ , gdzie ${\ Displaystyle A =X{\bmod {f}}}$ ). Głównym problemem jest tutaj efektywne znalezienie niezerowego dzielnika zera w algebrze. GRH jest używany tylko do zakorzeniania się w polach skończonych w czasie wielomianowym. W ten sposób algorytm Evdokimova w rzeczywistości rozwiązuje równanie wielomianowe na polu skończonym „pierwiastkami” w czasie quasi-wielomianowym, patrz Złożoność czasowa .

Analiza algorytmu Evdokimova jest ściśle związana z niektórymi problemami teorii schematów asocjacyjnych . Za pomocą tego podejścia udowodniono, że jeśli $pierwszą$ $s}$ i $ma$ „duży” $displaystyle$ r $r}$ , to modyfikacja algorytmu Evdokimova znajduje nietrywialny czynnik wielomianu $poli$ deterministycznym $\ Displaystyle \ operatorname {poli} (n ^ {r}, \log q)}$ czas, zakładając GRH i że ${\ Displaystyle s = \ Omega \ lewo ({\ sqrt {n/2 ^ {r}}} \, \ prawej)}$ .

Dalsza lektura

Szparliński, I. (1999). Pola skończone: teoria i obliczenia . Miejsce spotkania teorii liczb, informatyki, teorii kodowania i kryptografii . Matematyka i jej zastosowania . Tom. 477. Springer Verlag.