2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение02.02.2012, 03:47 
Аватара пользователя
Здравствуйте!
Столкнулся с проблемой генерации простых чисел.
Имеется число длиной в 1024 бита. ( около 200 десятичных разрядов ).
Вопрос: как проверить его на простоту?
Обычные алгоритмы абсолютно не подходят и по времени, и по ресурсам.
А вот какие можно посмотреть алгоритмы на ускорение процесса проверки?
Была забавная идея проверить с помощью малой теоремы Ферма, но сразу отпала... вы сами знаете почему :)

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение02.02.2012, 14:08 
Аватара пользователя
Может это даст какую-то наводку. ;)

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение02.02.2012, 19:42 
Сначала Вам надо войти в текущее состояние дел:
http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 1%82%D1%8B
Книжка: Василенко Теоретико-числовые алгоритмы в криптографии. Легко гуглится и скачивается.

loldop в сообщении #533939 писал(а):
Была забавная идея проверить с помощью малой теоремы Ферма,
с этого места на самом деле и началось все наиболее интересное :-)

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение04.02.2012, 11:20 
Аватара пользователя
Простите за незнание, но:
некоторые алгоритмы, как, например, тест Агравала-Каяла-Саксены, используют квадратные корни и логарфмы.
Меня волнует только..
как вычислять эти величины? и это будет очень долго по времени! ( операция сложения уже использует О(n) простых сложений! )
А использовать разложение корня и логарифма не очень-то дешево в случае больших чисел.
( не говоря уже об операции возведения в степень )

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение04.02.2012, 12:57 
loldop, я ведь их сам не реализовывал. Может venco придет и скажет чего-нибудь
Алгоритм Агравала-Каяла-Саксены - это наиболее навороченный алгоритм проверки на простоту, зато он точно детерминированный и полиномиальный. Однако, может оказаться, что он начинает работать быстрее, чем другие алгоритмы, начиная только с очень больших чисел (типа $10^{50}$ - я наугад пишу число). В книге Василенко вообще написано
Василенко писал(а):
Результаты практической реализации данного алгоритма пока неизвестны.

Как извлекать корень и считать логарифм оптимально я тоже не знаю :-( Ну для корня еще можно использовать ряд, а для логарифма - ряд с двоичным уменьшением числа (типа так: $\ln (2n+r)= \ln 2 + \ln n + \ln (1+\frac{r}{2n}), r \in \{ 0;1\}$ - считаем точно $\ln 2$ один раз и $\ln (1+\frac{r}{2n})$ и тогда вычисление $\ln m$ сводится к вычислению $\ln \left[ \frac{m}{2}\right]$):
Попробуйте какой-нибудь более простой алгоритм проверки на простоты, пусть даже с бОльшей асимптотической сложностью. Метод Лемера легко можно запрограммировать (заодно и с факторизацией побаловаться). Вроде несложен алгоритм Миллера. Можете рискнуть здоровьем и попробовать алгоритм Ленстры.
Может Вам вероятностный алгоритм подойдет (их и комбинировать можно) - они еще проще.

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение16.02.2012, 22:50 
Обычно в криптографии используют метод Миллера-Рабина.

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение17.02.2012, 18:09 
Аватара пользователя
loldop
Советую читать Кнута искусство программирования том 2. Читать с начала тома.
А да надо не просто читать, но и разбираться.

 
 
 
 Re: Алгоритмы и их оптимизация: Проверка простоты числа
Сообщение21.02.2012, 19:57 
Аватара пользователя
Спасибо за Кнута, конечно, очень полезная книжка.
Но проблема в том, что данная задача уже решена миллион раз, реализована в куче библиотек и не имеет для меня смысла более, чем интересная задача и алгоритмически сложная.

Спасибо, нашел Миллера-Рабина, действительно, простой метод.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group