Простые числа вида 2^n -1
Пятнадцать.
Эта формула не означает,что все числа вида 2^n -1 являются простыми.
Среди таких чисел есть простые, и у них есть специальное название типа числа pipisk'и. Сюда запостил потому, что из занятий по инфе вспомнил
А по какому правилу отбирать из этой последовательности простые числа? Я знаю последовательность стопудово простых чисел - "n^n - 2", n>1, n-нечётное. Насчёт "2^n - 1" - какое правило для n?
127, хуле 
последовательность стопудово простых чисел - n^n - 2, n>1, n-нечётноеВы уверены? Я не математик, но слыхал, что все попытки придумать формулу, которая дает только простые числа, обламываются...
Более "правильный" слух - не найдено никакой формулы, позволяющей найти все простые числа. Про формулы, дающие часть простых чисел ничего плохого не говорится.
Могу доказать, если тебе очень надо.
Могу доказать, если тебе очень надо.
(deleted by me)
Называются числами Мерсенна
Здесь
Здесь
Блин, есть формула. 1 3 7 15 31 63 127 255 511 1023 и тд... Из этих чисел часть - простые. Как они называются? Это стопудово какие-то именные. Кого-то вроде Эйлера. Не вспомним настоящего автора - будем звать числами pipisk'и 
О, стопудово! Не удалось мне авторство присвоить. Следующий вопрос - самое большое и нафиг нужны?
Позволю не согласиться, они криптографии нафиг нужны эти числа мерсенна. Эй надо поменьше знаков и порандомнее.
поботай кодирование с открытым ключом (RSA). Там очень нужно число m=p*q, p и q - очень большие простые числа.
Суть "защищённости" сводится к тому, что чтобы взломать шифр нужно m разложить на множители (т.е. шифр открыт тому, кто знает разложение).
Задача разложения на множители сейчас очень плохо решается. Нижняя оценка, по-моему не доказана, но все верхние оценки о количестве операций всё ближе и ближе к ней. но и нижняя оценка (предполагаемая) весьма плоха. сейчас не помню - но она вроде как даже не полиномиальна (от длины числа)
Суть "защищённости" сводится к тому, что чтобы взломать шифр нужно m разложить на множители (т.е. шифр открыт тому, кто знает разложение).
Задача разложения на множители сейчас очень плохо решается. Нижняя оценка, по-моему не доказана, но все верхние оценки о количестве операций всё ближе и ближе к ней. но и нижняя оценка (предполагаемая) весьма плоха. сейчас не помню - но она вроде как даже не полиномиальна (от длины числа)
Гыгы) Я как раз RSA-алгоритм недавно прогал на Сях.
Поясню: простые большие числа для RSA нужны очень даже. Размером они нужны не таким уж большим (для практики, Ватсон, для практики) - порядка 2^256 за глаза. Использовать же числа Мерсенна здесь, мягко говоря, не имеет смысла - таких всего явно меньше трех сотен. Не дай бог кому-нибудь догадаться, что ты ( , программист Вася, ) использовал Мерсенна... какая ж тут блин стойкость ключа, а?
Поясню: простые большие числа для RSA нужны очень даже. Размером они нужны не таким уж большим (для практики, Ватсон, для практики) - порядка 2^256 за глаза. Использовать же числа Мерсенна здесь, мягко говоря, не имеет смысла - таких всего явно меньше трех сотен. Не дай бог кому-нибудь догадаться, что ты ( , программист Вася, ) использовал Мерсенна... какая ж тут блин стойкость ключа, а?
Ну хз.. я целочисленными алгоритмами не занимаюсь.. всё больше синтаксическим анализом. 
и мы тут с гадфазером уже выяснили, что "программист Вася" - это не про меня
А ты знаешь, как 100% проверить число на простоту за полиномиальное время? (вероятностные методы не пройдут)
и мы тут с гадфазером уже выяснили, что "программист Вася" - это не про меня А ты знаешь, как 100% проверить число на простоту за полиномиальное время? (вероятностные методы не пройдут
)Просвяти алгоритмом. (Полиномиальное время - это "сумма по и от нуля до бесконечности а итое на эн в степени и" да?)
таких всего явно меньше трех сотен.Если ты про уже известные, то их всего 42. А вообще всего их явно не меньше бесконечности
Ты бы ещё из контекста выдрал одно слово и над ним стебался
Быстрый алгоритм определения, является ли числе простым, уже давно найден. И я даже как-то видел его в одном журнале.
вот статья: http://main.news.izvestia.ru/tech/11-08-02/news22067
вот статья: http://main.news.izvestia.ru/tech/11-08-02/news22067
Не тормози, плиз. Я ничего из контекста не вырывал.
Более "правильный" слух - не найдено никакой формулы, позволяющей найти все простые числа. Про формулы, дающие часть простых чисел ничего плохого не говорится.Множество положительных значений (принимаемых в целых точках) следующего многочлена совпадает с множеством простых чисел.
F ( a , b , c , d , e , f , g , h , i , j , k , l , m , n , o , p , q , r , s , t , u , v , w , x , y , z ) =
= { k + 2}{1 - ( wz + h + j - q )^2 - (2 n + p + q + z - e )^2 -
- ( a^2 y^2 - y^2 + 1 - x^2 )^2 -({ e^4 + 2 e^3 }{ a + 1}^2 - o^2 )^2 -
- (16{ k + 1} ^3 { k + 2}{ n + 1}^2 + 1 - f^2 )^2 -
- ({( a + u^4 - u^2 a )^2 - 1}{ n + 4 dy }^2 + 1 - { x + cu }^2 )^2 - ( ai + k + 1 - l - i )^2 -
- ({ gk + 2 g + k + 1}{ h + j } + h - z )^2 - (16 r^2 y^4 { a^2 - 1} + 1 - u^2 )^2 -
- ( p - m + l { a - n - 1} + b {2 an + 2 a - n^2 - 2 n - 2})^2 -
- ( z - pm + pla - p^2 l + t {2 ap - p^2 - 1})^2 -
- ( q - x + y { a - p - 1} + s {2 ap + 2^a - p^2 - 2 p - 2})^2 -
- ( a^2 l^2 - l^2 + 1 - m^2 )^2 - ( n + l + v - y )^2 }
А доказательство?
Существование многочлена с таким свойством доказал Ю.В. Матиясевич. Есть в труде "Диофантовость перечислимых множеств", который был опубликован в 1970г. Когда и кем был получен конкретный пример и где его д-во, не знаю. Искать не хочу, т.к. не верю, что ты его проверять будешь.
Хорошо, так и быть, поясню : количество чисел вида 2^n-1 в интервале от 0 до 2^256 меньше трёхсот. Уразумел?
вот тут интересно написано
http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node32.html
Есть алгоритм работающий за O(ln^3(N но он "условный":
Он даёт правильный ответ, при условии, что верна т.н. расширенная гипотеза Римана.
http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node32.html
Есть алгоритм работающий за O(ln^3(N но он "условный":
Он даёт правильный ответ, при условии, что верна т.н. расширенная гипотеза Римана.
Если не очень длинный - положи его сюда.
Я уразумел только то, что ты свои мысли выражать не умеешь.
Ладно тебе огнём пыхать! Мне казалось всё понятным ... Держать в голове надо было сразу три предложения:
"простые большие числа ... Размером ... порядка 2^256 ... Использовать же числа Мерсенна здесь ... не имеет смысла - таких всего явно меньше трех сотен."
"Здесь" = "в данном случае", "в этом примере".
"простые большие числа ... Размером ... порядка 2^256 ... Использовать же числа Мерсенна здесь ... не имеет смысла - таких всего явно меньше трех сотен."
"Здесь" = "в данном случае", "в этом примере".
Оставить комментарий
iakobi91
Как называются? И какое самое большое известное?