Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Простое число Первушина
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

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.

Доказательство и много другой информации на http://primes.utm.edu/mersenne/index.html

Прикинул - для 2^61-1 нужно проверить больше миллиона делителей

2. http://www.rulex.ru/01160215.htm

В 1893 году Первушин отправил на математический конгресс в Чикаго свою заметку "о наилучшей поверке арифметических действий над огромными числами при посредстве делителей: 10 в 3-й степени - 2 = 998, 10 в 4-й степени - 2 = 9998"

Вопрос интересный - весь вечер читал о простых числах Мерсенна  

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 31 мая 2006 21:31 | IP
Reactor


Новичок

Спасибо за проявленный интерес.

Разумеется. Когда я писал свой вопрос я знал и о числах Мерсенна и о методе люка-Леммера. Я вообще повернутый на поисках делителей больших чисел. И на эту тему я сам могу рассказать очень много. даже про 100000 баксов тому, кто найдет простое число длинною больше 10 млн.знаков и как с помощью распределенных вычислений ищут это число среди чисел вида 2^p-1. (Подробнее на www.mersenne.org). Кстати тест Люка-Лемера позволяет только определить наличие делителей, но не их самих. Для поиска делителей есть другой алгоритм, но он (относительно) медленный (ссылку тоже могу дать,если есть интерес). У меня есть свой алгоритм, который я стараюсь усовершенствовать и потихонечку собираю коллекцию делителей чисел вида 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 обратил внимание на пару проектов, связанных с обсуждаемой темой:

http://www.ltkz.demon.co.uk/ar2/mm61.htm
Поиск делителей числа 2^(2^61-1)-1
Т.е. степень в числе Мерсенна равна простому числу Первушина

http://www.nfsnet.org/
Поиск делителей больших чисел.

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 3 июня 2006 11:33 | IP
VF



Administrator

Оказывается существует полином 25 степени от 26 переменных, положительные значения которого в точности совпадают со множеством всех простых чисел!
http://en.wikipedia.org/wiki/Formula_for_primes

Существует подобный многочлен и с 9 переменными, правда его степень 1.6*10^45
http://www.math.ucalgary.ca/~jpjones/abst1982.htm

Вопрос: почему в алгоритмах шифрования с открытым ключем простые числа генерируются с помощью вероятностного алгоритма (т.е. существует возможность, что полученное число окажется не простым)? Ведь можно было бы используя генератор случайных чисел получить 26 значений и подставить их в формулу, гарантирующую получение простого числа!

Конечно, с формулой тоже не все просто - на выходе она может дать отрицательное или не достаточно большое положительное число. Но я думаю, ее можно исследовать и определить допустимые диапазоны параметров для получения приемлемого для шифрования простого числа.

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 3 июня 2006 18:00 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com