AKS алгоритм определения простоты числа

[Nerazumovskiy]

Вот описание алгоритма о котором пойдёт речь.
1)Да я понимаю что это алгоритм по програмированию.

В ходе обоснования алгоритма (2 страница) вводиться обозначение (3) с обяснениями.
Беда в том что я немогу понять что они имеют ввиду под этим выражением $(x-a)^n \equiv (x^n -a) (mod$ $n,x^r-1)$

Если перефразировать вопрос, то что под собой подрозумевает сужение многочлена на кольцо из многочленов?

-- Пн ноя 16, 2009 21:09:30 --

Естественно было бы очень шыкарно еслиб ктото подсказал как это реализовать(но очу понять хотябы суть).

[Xaositect]

Вычисления по $(\mathrm{mod}\ n, x^r -1)$ - это значит, что все коэффициенты многочлена рассматриваются по $\mathrm{mod}\ n$, а сами многочлены - по $\mathrm{mod }\ x^r - 1$ - то есть, грубо говоря, $x^r$ полагается равным $1$: от многочлена $P(x)\cdot x^r + Q(x)$ мы можем перейти к $P(x) + Q(x)$.

Указанное конкретное сравнение проверяется возведением $x-a$ в $n$-ю степень бинарным алгоритмом ($O(\log n)$ умножений), причем после каждого умножения производится редукция по $(\mathrm{mod }\ n, x^r -1)$ указанным выше образом: многочлен разбивается на 2 части - степени $<r$ и $\geqslant r$, складываем их, и все коэффициенты приводим по модулю $n$.

[Nerazumovskiy]

Цитата:

многочлен разбивается на 2 части - степени $<r$ и $\geqslant r$

Мне кажеться что у вас тут опечатка, ведь $x^r$ нам неподходит.
______________
Смотрите как я понял, если немного затронуть алгоритм, то там $r<n$ соответственнно справа в моём равенстве мне $x^n$ надо разсматривать тоже $mod{x^r}$.
И второе уточнение, получаеться что когда мы получили уже урезаные полиномы, то чтобы проверить равенство мне достаточно будет посмотреть равны ли коефициенты при степенях, или лучше изначально проводить данные сравнения в $r$ точках(интерполируя). Исходя из вашего ответа я так понимаю что нужно интерполировать, но тогда при выполнении вего одного такого сравнения многочленов будет затрачено
$log^7(n)$ , так как $r \approx log^6(n)$(это они говорят на 3 странице). Тогда если выполнять ещо и данное сравнение $\sqrt{r}log(n)$ раз, то сложность у алгоритма получаеться нехилая.

[Батороев]

Nerazumovskiy в сообщении #262735 писал(а):

Вот описание алгоритма о котором пойдёт речь.

Цитата:

В основе этого теста на простоту лежит следующее тождество:
Утверждение. Пусть НОД$(a, n)=1$. Тогда $n$ - простое тогда и только тогда, когда

$$ (x-a)^n\equiv (x^n - a)\pmod n $$

$$ (13 - 5)^{561}\equiv (13^{561} - 5)\pmod {561} $$

Чем такой тест может быть сильнее теста по МТФ?

Или в статье очепятка?
Или я что-то не правильно понял?

[Nerazumovskiy]

Ониже обясняют что они делают не так, они потом это условие очень хитро оптимизируют, посути про то как они это делают и написана стаття.
(чуть ниже приведён настоящий алгоритм)

И справедливости ради, ониже сами говорят, что этот алгоритм на практике хуже других, но зато это уже непереборный алгоритм, у которого есть заявленная неполимиальная сложность(об этом тоже написано на 5 стр).

Насколько я понял у этого алгоритма только теоритическая ценность, он решает проблему $P=NP$.

[ИСН]

Nerazumovskiy в сообщении #262903 писал(а):

он решает проблему $P=NP$.

Тут Вы, боюсь, оказываетесь немного впереди паровоза.

[Nerazumovskiy]

Почему?

P.S.Может ктото заодно прокоментирует моё второе сообщение.

[Xaositect]

Nerazumovskiy в сообщении #262886 писал(а):

Смотрите как я понял, если немного затронуть алгоритм, то там соответственнно справа в моём равенстве мне надо разсматривать тоже $\mathrm{mod}\ x^r$.

Да, только не $\mathrm{mod}\ {x^r}$, а $\mathrm{mod}\ {x^r-1}$, то есть $x^n \equiv x^{n \mod r}$

Цитата:

то сложность у алгоритма получаеться нехилая.

Там $(\log n)^{12}$, насколько я помню.

-- Вт ноя 17, 2009 16:10:28 --

Nerazumovskiy в сообщении #262910 писал(а):

Почему?

Nerazumovskiy в сообщении #262903 писал(а):

Насколько я понял у этого алгоритма только теоритическая ценность, он решает проблему $P=NP$.

Он не решает проблему $P=NP$.
Тут такая ситуация. Когда были определены классы $P$ и $NP$ и понятие $NP$-полноты, почти все естественные задачи сразу удалось классифицировать. Для некоторых ашлись полиномиальные алгоритмы, а некоторые оказались $NP$-полными. А задача определения простоты непонятно куда относилась, AKS и решили этот вопрос. У них оригинальная статья так и называется "$PRIMES$ is in $P$"

[Батороев]

Nerazumovskiy в сообщении #262903 писал(а):

Ониже обясняют что они делают не так, они потом это условие очень хитро оптимизируют, посути про то как они это делают и написана стаття.
(чуть ниже приведён настоящий алгоритм).

То, что изначально не верно, можно оптимизировать сколько угодно. От этого оно верным не станет.

А еще в статье приводится "Доказательство" этого не верного утверждения!!!

[Xaositect]

Батороев в сообщении #262957 писал(а):

То, что изначально не верно, можно оптимизировать сколько угодно. От этого оно верным не станет.

Там в оригинале тоже не очень хорошо написано, но суть в том, что это должно быть верным для произвольного $a$, взаимно простого с $n$.

[Батороев]

Xaositect в сообщении #262961 писал(а):

Там в оригинале тоже не очень хорошо написано, но суть в том, что это должно быть верным для произвольного $a$, взаимно простого с $n$.

Так я выполнил условие взаимной простоты: $a=5$; $n=561=3\cdot 11\cdot 17$.

Батороев в сообщении #262894 писал(а):

$$ (13 - 5)^{561}\equiv (13^{561} - 5)\pmod {561} $$

[Xaositect]

А где $X$-то? $X$-это не число, это переменная над $\mathbb{Z}$

[Батороев]

Понял. Хотя ничего не понял.
Спасибо!

[Xaositect]

Ну в общем это сравнение должно пониматься как равенство многочленов над $(\mathbb{Z}/n\mathbb{Z})$

[Nerazumovskiy]

Вобщем написал я сеё чудо, и что забавно даже несмог определить простоту чесла 9901 (обломался ждать).
Вот такой он неполимиальный метод

-- Вт ноя 17, 2009 19:37:05 --

P.S. код канешно далёк до идеального, но результат есть результат.