2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Решето Сундарама и его следствия ч.2
Сообщение20.09.2012, 20:09 
freeot в сообщении #621388 писал(а):
Если найдется математический аппарат, с помощью которого можно быстро качественно показать имеет ли решение уравнение $z=2xy+x+y$ для заданного $z$ в натуральных $x$ и $y$, то перед нами - самый простой тест на простоту любого числа ;-)

Задача факторизация тоже сводится к задаче разрешимости квадратного диофантова уравнения двух неизвестных. Но скорее всего последняя также NP-сложна, как и первая.

freeot в сообщении #621388 писал(а):
Допустим, мы хотим найти простые числа порядка $10^{10000}$ (или $10^{10^{1000000000}}$ - без разницы) :-)

Важно научиться "чувствовать" запредельную грандиозность чисел такого размера. Нет лучше способа "прочувствовать", чем самостоятельно запрограммировать собственный алгоритм. Для этого более всего подходит программируемый калькулятор pari/gp. Если можете программировать в 1С, то тем более сможете и в pari/gp программировать проверочные алгоритмы для своих изысканий.

 
 
 
 Re: Решето Сундарама и его следствия
Сообщение21.09.2012, 23:39 
Аватара пользователя
venco в сообщении #621532 писал(а):
Это говорит лишь о том, что решето Сундарама ничего особенного не представляет по сравнению с решетом Эратосфена. Эта оптимизация приходит в голову самостоятельно практически любому, кто пользуется решетом для поиска простых чисел.

venco, а метод квадратичных вычетов АССА? Или до сих пор в математических кругах форума алгоритм считается модернизацией решета Эратосфена?

 
 
 
 Re: Решето Сундарама и его следствия
Сообщение22.09.2012, 00:53 
SerjeyMinsk в сообщении #622123 писал(а):
venco, а метод квадратичных вычетов АССА? Или до сих пор в математических кругах форума алгоритм считается модернизацией решета Эратосфена?
А он разве изменился с тех пор, как его обсудили?

 
 
 
 Re: Решето Сундарама и его следствия
Сообщение23.09.2012, 23:54 
Аватара пользователя
venco в сообщении #622135 писал(а):
А он разве изменился с тех пор, как его обсудили?

Ему изменятся нет нужды. Он вполне себе самодостаточен и уникален.
Вопрос полиномиальности в этом алгоритме мною признан и понят, но уж никак не модернизация. Это современный детерминированный метод квадратичных вычетов с экспоненциальной сложностью.

 
 
 [ Сообщений: 19 ]  На страницу Пред.  1, 2


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