Друзья, расскажите, какие сейчас есть наиболее быстрые тесты простых чисел общего вида, вероятностные и детерминистичекие? Правильно ли я понимаю, что тест, основанный на псевдопростых числах Фробениуса — самый быстрый вероятностный, а AKS с дополнениями — детерминистический? Или методы, основанные на эллиптических кривых, быстрее, чем AKS?

GD Star Rating
loading...
Tagged with →  

16 Responses to Какие есть тесты простых чисел общего вида?

  1. Zvin:

    Ау? Никто мне не подскажет? Мне правда нужно.

  2. Zvin:

    Я к чему спрашиваю: тут на досуге придумал и опробовал на небольших числах новый тест вероятностный, вроде как довольно быстрый, но я хочу понять, быстрее ли он ныне существующих.

  3. Lakm:

    Ну если он полиномиальный от длины числа, то это уже интересно, вне зависимости от того, быстрее ли он других методов или нет. А если нет, то он как бы слишком медленный.

  4. Re:

    В чем состоит алгоритм, если не секрет? Какие–то оценки на сложность есть?

  5. Zvin:

    полиномиальный. Я только пока не могу оценить точно вероятность, которую даёт каждый следующий его цикл. Дело в том, что она зависит от размера проверяемого числа, а вот каким образом — неясно.

  6. Zvin:

    пока секрет, вдруг это открытие. Оценку дать сложно, я пока не решил, как именно выстраивать параметры циклов проверки в зависимости от проверяемого числа. Если одним образом, то для очень хорошей вероятности (очень хорошая это такая, для которой первое псевдопростое число будет очень–очень большим числом Кармайкла) нужно два цикла, но с привлечением больших чисел, которые долго считать. То же самое можно достичь за, например, десять других циклов, но считать числа для каждого из них быстрее.

  7. Taova:

    эмпирические тесты проводили?

  8. Zvin:

    на тех величинах, что можно проверить на моём компьютере, он вообще не даёт псевдопростых чисел после достаточного количества циклов, вчера весь вечер считал. Я пока не понял, как доказать, какое нужно количество циклов для каждого конкретного проверяемого числа — иногда достаточно одного цикла, иногда 11, иногда 7.

    Тут ещё что приятно, так это скорость вычисления и нужные объёмы памяти при каждом цикле. Грубо говоря, нужно для проверяемого числа n проделать 2 sqrt n простых арифметических действий на цикл, при этом самые большие числа будут порядка (1+epsilon)^n. То есть хотя формально зависимость степенная, реально числа растут очень медленно и не сильно больше проверяемого n.

  9. Zvin:

    хотя нет, я ошибся, если другим методом считать, то много меньше арифметических действий на цикл нужно.

  10. Taova:

    sqrt(n) это не быстро…

  11. Zvin:

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

  12. Re:

    sqrt n действий означает что алгоритм неполиномиальный — в теоретико–численных алгоритмах за размер входа принимают log n и получается что действий у тебя O(2^(log n / 2)). А уж экспоненциальная зависимость от n (даже не от log n) убивает асимптотику начисто — алгоритм получается дважды экспоненциальным!

  13. Zvin:

    жаль. А на малых n всё так хорошо было.

  14. Re:

    на малых n и trial division хорошо работает) Кстати тоже за O(sqrt n)

  15. Zvin:

    я после обеда вычитал в одной умной статье, как за log(n) укладываться в один цикл. Но, честно говоря, тест не нужный получился, потому что я не могу доказать, сколько нужно всего проделать циклов (как в тесте Миллера–Рабина детерминистическом), а так он просто остаётся вероятностным тестом.

  16. Zvin:

    Ладно, раз уж не сложилось со скоростью, расскажу вкратце суть идеи.

    Возьмём последовательности следующего вида:
    T[k]=T[k+1–n]+T[k–n], где n больше или равно 3.
    Первые значение определим как:
    T[0]=n, T[1]=0, T[2]=0, …, T[n–2]=0, T[n–1]=n–1
    Тогда k|T[k] для простых k и для псевдопростых k
    Чем больше n, тем медленнее растёт последовательность, соответственно T[k] тоже будут небольшими, сопоставимыми с k.
    n нужно выбирать как (2 sqrt k)–k, чтобы не попасть на нулевые значения T[k] (это примерно та граница, после которой все T[k]>0)
    Идея заключалась в том, чтобы выбирать наибольшее n в зависимости от k, проводить на нём первый цикл. Потом брать n–1 и проводить с его помощью второй цикл и так далее. Если в одном из циклов T[k] не делится на k нацело, выдавать, что число составное.
    А предположение состояло в том, что, поскольку псевдопростые числа для каждого n имеют разные особенности, то при проведении достаточно большого количества циклов, вероятность, что мы будем получать только псевдопростые числа, будет ничтожной. Я не думаю, что можно доказать теорему, по которой можно найти количество циклов, гарантирующее, что они не пропустят ни одного псевдопростого числа, но если такая теорема возможна, тест будет детерминистическим.

Добавить комментарий