НГУ
http://forum.nsu.ru/

легкая задачка по т.ч.
http://forum.nsu.ru/viewtopic.php?f=24&t=17557
Страница 2 из 2

Автор:  Коба [ Чт сен 27, 2007 10:54 am ]
Заголовок сообщения: 

maxal писал(а):
У вас превратное представление о существующих тестах простоты. Например, непростота для n=3^8=6561 на современном компе устанавливается за доли секунд.


Да, согласен. Краем уха что-то слышал о том, что определение простоты/непростоты больших чисел --- очень важная для криптографии задача и для её решения разработаны весьма замысловатые, но "быстрые" алгоритмы. Однако специально этими вопросами никогда не интересовался.

Всё, что приходит на ум (кроме залезания в специальную литературу) --- это либо перебор возможных делителей от 2 до корня из числа, простоту которого проверяем, либо решето Эратосфена. Оба способа для больших n не годятся.

maxal писал(а):
Почему бы не воспользоваться мат.пакетами, в которых все уже давно запрограммировано? Например, PARI/GP - и бесплатный, и быстрый пакет для теоретико-числовых вычислений.


Ну так если бы не Ваша ссылка, то я бы никогда и не узнал, где такие пакеты брать. Так что ответ очевиден :)

Автор:  maxal [ Чт сен 27, 2007 11:01 am ]
Заголовок сообщения: 

Коба писал(а):
Краем уха что-то слышал о том, что определение простоты/непростоты больших чисел --- очень важная для криптографии задача и для её решения разработаны весьма замысловатые, но "быстрые" алгоритмы. Однако специально этими вопросами никогда не интересовался.

Вот просветитесь: http://nature.web.ru/db/msg.html?mid=11 ... ode32.html

Автор:  maxal [ Чт сен 27, 2007 11:06 am ]
Заголовок сообщения: 

Коба писал(а):
maxal писал(а):
Почему бы не воспользоваться мат.пакетами, в которых все уже давно запрограммировано? Например, PARI/GP - и бесплатный, и быстрый пакет для теоретико-числовых вычислений.


Ну так если бы не Ваша ссылка, то я бы никогда и не узнал, где такие пакеты брать. Так что ответ очевиден :)

Вот пример нахождения ответов на ваши вопросы в PARI/GP. Сначала задаем нашу функцию, потом распечатываем первые 4 значения, затем факторизуем их же, а затем еще четыре следующих значения проверяем на простоту:
Код:
? f(k)=1+2^(3^k)+4^(3^k)
? for(k=1,4,print(f(k)))
73
262657
18014398643699713
5846006549323611672814741748716771307882079584257
? for(k=1,4,print(k,": ",factor(f(k))))
1: Mat([73, 1])
2: Mat([262657, 1])
3: [2593, 1; 71119, 1; 97685839, 1]
4: [487, 1; 16753783618801, 1; 192971705688577, 1; 3712990163251158343, 1]
? isprime(f(5))
%1 = 0
? isprime(f(6))
%2 = 0
? isprime(f(7))
%3 = 0
? isprime(f(8))
%4 = 0

Страница 2 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/