Jaka jest najgorsza złożoność sita z polem liczbowym?

Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność $N\in\Bbb N$ $N$ do współczynnika. $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ $N$

Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji.

(1) Jaka jest najgorsza złożoność sita z polem liczbowym?

(2) Czy można tu również usunąć losowość, aby uzyskać deterministyczny algorytm subwykładniczy?

reference-request derandomization factoring average-case-complexity worst-case
źródło

Odpowiedzi:

$e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

$x$ $x^2 \pmod{n}$ $n$ $n$

Nominalna złożoność najgorszego przypadku wszystkich tych algorytmów to nieskończoność: w przypadku sita kwadratowego i sita pola liczbowego zawsze możesz generować ten sam , podczas gdy w metodzie krzywej eliptycznej zawsze możesz generować tę samą krzywą eliptyczną . Jest na to wiele sposobów, na przykład równoległe uruchamianie algorytmu wykładniczego czasu. $x$

Yuval Filmus
źródło

Skoro poruszył ECM też: wiemy, że subexp randomizowane algorytm do obliczania w razem używając ECM gdzie jest nieznany i randomizacji. Czy masz szacunkową liczbę prób tego algorytmu, aby uzyskać i gdzie ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Nie mam pojęcia, czym jest , ale ogólnie mówiąc, wybierając parametry w ECM, balansujemy między prawdopodobieństwem że krzywa jest wystarczająco gładka, a czasem pracy wymaganym do przetestowania każdej krzywej. Zwykle punkt równowagi występuje, gdy .Tak więc oczekiwana liczba prób powinna wynosić .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus,

n!

$n!$ jest silnia . Problemem otwartym jest uzyskanie złożoności silni prostej. Wiemy, jak obliczyć gdzie jest nieznane w czasie podwyrażenia. Jeśli znamy dwa różne i , możemy uzyskaćw czasie podwyrazu, jeśli .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Pamiętam, jak obliczałem jakiś czas temu. Nie sądzę, żebym mógł poprawić, ponieważ nastąpił haczyk i nie pamiętam szczegółów.

ostatni akapit wydaje się dziwny i można go wyjaśnić więcej. czy mówisz o scenariuszu, w którym RNG jest „zepsuty” w tym sensie, że nie próbkuje całej przestrzeni dystrybucyjnej? ale czy równoległość nie pomogłaby w tym? ponieważ byłby to ten sam „zepsuty” RNG równolegle? czy jest to pomysł, że będzie to inny równoległy RNG? w rzeczywistości równoległa złożoność algorytmów faktoringowych to tak naprawdę zupełnie inny złożony temat, np. niektóre mogą być lepiej zrównoleglone niż inne, big-O może nie mieć zastosowania itp.

vzn

W ciągu ostatnich kilku miesięcy wersja sita z polem liczbowym została poddana dokładnej analizie: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Zasadniczo najgorszym czasem działania jest bezwarunkowo i pod GRH. Nie dotyczy to „klasycznego” sita pola liczbowego, ale nieco zmodyfikowanej wersji, która losuje więcej kroków, aby ułatwić analizę złożoności. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Uważam, że odpowiedni artykuł jest nadal w trakcie przeglądu.

Aktualizacja: papier jest teraz niedostępny. Jonathan D. Lee i Ramarathnam Venkatesan, „Rygorystyczna analiza losowego sita pola liczbowego”, Journal of Number Theory 187 (2018), s. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
źródło

Czy możesz podać pełniejsze odniesienie, w którym możemy dowiedzieć się więcej, z tytułem, autorem i miejscem publikacji, aby odpowiedź była nadal przydatna, nawet jeśli link przestanie działać?

Ponieważ wynik został ogłoszony dopiero niedawno, uważam, że jest on obecnie poddawany przeglądowi, jak wskazano w mojej odpowiedzi, a zatem nie został jeszcze opublikowany. Zaktualizuję swoją odpowiedź w przyszłości, gdy będą dostępne informacje o publikacji.

djao

FWIW nie wygląda na to na arxiv.org. Jednak autorem jest Ramarathnam Venkatesan, który może pomóc w przyszłych poszukiwaniach, jeśli będą konieczne.

Peter Taylor,

W rzeczywistości jest to dzieło dwóch autorów (JD Lee i R. Venkatesan): cmi.ac.in/activities/…

Sary