Reactor
Новичок
|
     
Народ. Приветствую всех. Два вопроса:
1. Как Первушин доказал, что 2^61-1 - простое?
2. Сохранилась ли книга, которую он написал? (Кажется она называлась - Проверка на делимость с помощью чисел 10^n-2).
|
Всего сообщений: 10 | Присоединился: июль 2005 | Отправлено: 31 мая 2006 14:55 | IP
|
|
VF 
Administrator
|
 
1. Первушин доказал, что число 2^61-1 простое в 1883 г. Самый быстрый известный сейчас способ проверки чисел Мерсенна на простоту: тест Люка - Лемера был описан в 1878 г. Но еще в 1876 г. Люк доказал, что число 2^127-1 простое. Так что не исключено, что Первушин занялся исследованием на волне популярности новой теории.
Можно использовать другой факт:
Пусть p и q простые. Если q делит 2^p-1, то q = +/- 1 (mod 8) и q = 2kp + 1 для целых k.
Доказательство и много другой информации на внешняя ссылка удалена
Прикинул - для 2^61-1 нужно проверить больше миллиона делителей 
2. внешняя ссылка удалена
В 1893 году Первушин отправил на математический конгресс в Чикаго свою заметку "о наилучшей поверке арифметических действий над огромными числами при посредстве делителей: 10 в 3-й степени - 2 = 998, 10 в 4-й степени - 2 = 9998"
Вопрос интересный - весь вечер читал о простых числах Мерсенна
|
Всего сообщений: 3110 | Присоединился: май 2002 | Отправлено: 31 мая 2006 21:31 | IP
|
|
Reactor
Новичок
|
Спасибо за проявленный интерес.
Разумеется. Когда я писал свой вопрос я знал и о числах Мерсенна и о методе люка-Леммера. Я вообще повернутый на поисках делителей больших чисел. И на эту тему я сам могу рассказать очень много. даже про 100000 баксов тому, кто найдет простое число длинною больше 10 млн.знаков и как с помощью распределенных вычислений ищут это число среди чисел вида 2^p-1. (Подробнее на внешняя ссылка удалена). Кстати тест Люка-Лемера позволяет только определить наличие делителей, но не их самих. Для поиска делителей есть другой алгоритм, но он (относительно) медленный (ссылку тоже могу дать,если есть интерес). У меня есть свой алгоритм, который я стараюсь усовершенствовать и потихонечку собираю коллекцию делителей чисел вида 2^p-1. Сейчас их в моей коллекции уже более полутора тысяч, но последнее время я стремлюсь не за количеством, а за качеством. Например делителя 2^101-1 у меня пока нету, т.к. мой алгоритм просит около месяца на нахождения всех делителей этого числа. Это меня не устраивает. Слишком долго. Но это Лирика.
Мой вопрос родился не спроста. Позволю себе утверждать, что Люку, при проверке числа 2^127-1 было гораздо легче, чем Первушину. И далеко не очевидно, что Первушин использовал тест Люка (тестом Люка-Лемера он стал позже).
Тут дело вот в чем: Люк целенаправленно взялся за проверку именно этого числа,т.к. на тот момент уже прослеживалась "логическая" цепочка
2^3-1=7 - число Мерсенна
2^7-1=127 - тоже число Мерсенна, после чего и напрашивалась проверка числа 2^127-1, что и сделал Люк. Кстати вопрос и числе 2^(2^127-1)-1 открыт до сих пор.
Но у числа Первушина никакой логики не просматривается. Возникает вопрос, что это? Простое везение? Ведь Первушин мог потратить уйму времени на число 2^67-1 (делитель которого очень большой), да и 2^59-1 на тот момент проверено не было. А он стал проверять именно 2^61-1. причем не имея никаких вычислительных приборов. И проверил. Как он это сделал?
И еще больше вопросов вносит справедливо упомянутый доклад. (Вот бы его раздобыть). Как его тема может соотносится с проверкой на делимость? И книга,упомянутая мною имеет сходное название.
Буду очень признателен, если кто поделится инфой.
|
Всего сообщений: 10 | Присоединился: июль 2005 | Отправлено: 1 июня 2006 22:22 | IP
|
|
VF
Administrator
|
В ссылках на mersenne.org обратил внимание на пару проектов, связанных с обсуждаемой темой:
внешняя ссылка удалена
Поиск делителей числа 2^(2^61-1)-1
Т.е. степень в числе Мерсенна равна простому числу Первушина
внешняя ссылка удалена
Поиск делителей больших чисел.
|
Всего сообщений: 3110 | Присоединился: май 2002 | Отправлено: 3 июня 2006 11:33 | IP
|
|
VF
Administrator
|
Оказывается существует полином 25 степени от 26 переменных, положительные значения которого в точности совпадают со множеством всех простых чисел!
http://en.wikipedia.org/wiki/Formula_for_primes
Существует подобный многочлен и с 9 переменными, правда его степень 1.6*10^45 
внешняя ссылка удалена
Вопрос: почему в алгоритмах шифрования с открытым ключем простые числа генерируются с помощью вероятностного алгоритма (т.е. существует возможность, что полученное число окажется не простым)? Ведь можно было бы используя генератор случайных чисел получить 26 значений и подставить их в формулу, гарантирующую получение простого числа!
Конечно, с формулой тоже не все просто - на выходе она может дать отрицательное или не достаточно большое положительное число. Но я думаю, ее можно исследовать и определить допустимые диапазоны параметров для получения приемлемого для шифрования простого числа.
|
Всего сообщений: 3110 | Присоединился: май 2002 | Отправлено: 3 июня 2006 18:00 | IP
|
|
|
Форум
Простое число Первушина
