НГУ

Форумы НГУ
Текущее время: Вт дек 10, 2019 9:52 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 27, 2007 10:54 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
maxal писал(а):
У вас превратное представление о существующих тестах простоты. Например, непростота для n=3^8=6561 на современном компе устанавливается за доли секунд.


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

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

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


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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 27, 2007 11:01 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Коба писал(а):
Краем уха что-то слышал о том, что определение простоты/непростоты больших чисел --- очень важная для криптографии задача и для её решения разработаны весьма замысловатые, но "быстрые" алгоритмы. Однако специально этими вопросами никогда не интересовался.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 27, 2007 11:06 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Коба писал(а):
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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу Пред.  1, 2

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB