Самое большое простое число

Сообщение №2085 от Alexander 20 декабря 2001 г. 17:49
Тема: Самое большое простое число

Громоздкая простота


Последний месяц уходящего года принес известие об открытии самого большого простого числа, из известных человечеству. В десятичном представлении это число, равное 213466917-1, имеет более четырех миллионов цифр. Честь открытия принадлежит двадцатилетнему 11канадцу Майклу Камерону (Michael Cameron), участвующему в проекте распределенных вычислений Great Internet Mersenne Prime Search (GIMPS).


Простые числа, делящиеся лишь на себя и на единицу, называют фундаментальными строительными блоками мира математики. Всякое натуральное число либо само простое, либо единственным образом разлагается в произведение простых чисел. Особый же интерес математиков привлекают простые мерсенновские числа вида 2n-1, обозначаемые как Mn и названные так в честь французского монаха-ученого Марина Мерсенна (на фото), изучавшего их в XVII веке. Если Mn простое, то легко показать, что и число n должно быть простым. Более того, каждое новое простое число Мерсенна известным способом приводит к открытию нового «совершенного» числа, то есть числа, равного сумме всех своих делителей. Но если совершенные числа пока остаются интеллектуальной забавой в теории чисел, то большие простые получили важное практическое приложение в криптографии.


Найденное Камероном число стало 39-м из известных в математике простых мерсенновских чисел. Предыдущее, 38-е число, обнаруженное два с половиной года назад (также в рамках проекта GIMPS), содержит более двух миллионов цифр. Технология отыскания этих чисел чрезвычайно напоминает организацию других распределенных Интернет-вычислений, таких как поиск сигналов внеземных цивилизаций по программе SETI@home или нахождение новых препаратов для борьбы со СПИДом. Добровольцы скачивают на свой компьютер программу-клиент, и та «перемалывает» полученные из центра данные в свободное от основной работы ПК время. Ради отыскания новых мерсенновских чисел десятки тысяч компьютеров по всему свету гоняют так называемый тест Люка-Лемера, который время от времени и приносит жемчужины открытий. В общей же сложности, как показывают оценки, на отыскание нового простого числа проект GIMPS затратил около 13 тысяч лет работы некоего «среднего ПК». Лишь на подтверждение открытия Камерона, к примеру, ушло около трех недель проверочных вычислений.

Берд Киви [kiwi@computerra.ru], Компьютерра №48 (425)

Громоздкая простота


Отклики на это сообщение:

I suppose your website is ok, but maby you should have a consultation with a proffesional web designer.


Ты что этим сказать хотел, деточка? Что, число на 13 мегабит памяти большое по твоему. На дискетку влезет? А новое число мерсена будешь еще 10 лет ждать,
вероятность простого числа - 1/lnX, а мерсеновского - 1/2^lnX ~1/X.


> Ты что этим сказать хотел, деточка? Что, число на 13 мегабит памяти большое по твоему. На дискетку влезет? А новое число мерсена будешь еще 10 лет ждать,
> вероятность простого числа - 1/lnX, а мерсеновского - 1/2^lnX ~1/X.

Нового простого числа Мерсенна ждать осталось до начала декабря. ;-)

====

По неофициальной информации в рамках проекта GIMPS найдено 40-е простое число Мерсенна. Официально число будет опубликовано в начале декабря, когда ожидается завершение независимой проверки.

Несмотря на то, что недавно в проекте ошибочно анонсировали нахождение очередного простого числа Мерсенна, принятые вследствии дополнительные меры по предовращению ошибок вселяют уверенность, что в этот раз ошибка исключена.

Пока не завершена проверка, само число держится в секрете, но уже известно, что его длина находится между 5-ю и 10-ю миллинонами цифр. Таким образом, оно не может претендовать на награду в $100000 обещанную Electronic Frontier Foundation за нахождение простого числа с более чем 10 миллионами цифр. Безусловно интересно, насколько же близко проект подошел к заветному рубежу. Напомним, что текущий официальный рекордсмен (так же найденный GIMPS) имеет длину чуть более 4 миллионов цифр.


Официально опубликовано 40-е простое число Мерсенна, найдейное 17-го ноября в рамках проекта GIMPS. Это число

220996011-1


содержит 6320430 цифр и является самым большим простым числом, известным человечеству.


Уважаемые софорумники
На сайте http://www.utm.edu/research/primes/largest.html
опубликованы максимальные известные простые числа. Я хотел бы предложить вашему вниманию свои два последовательных простых числа с количеством десятичных знаков не менее 5612.
Они попадают в десятку самых больших праймориальных простых чисел. Праймориал - это произведение последовательных простых чисел.
Пусть П=2*3*5*7*11*...*13033
Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.
Причем между ними больше простых нет.
Если найдутся энтузиасты, то можно побороться за рекордные числа.
Не все ж буржуинам рекорды ставить! ;)
15 декабря 2003 г. 16:05:



> На сайте http://www.utm.edu/research/primes/largest.html
> опубликованы максимальные известные простые числа. Я хотел бы предложить вашему вниманию свои два последовательных простых числа с количеством десятичных знаков не менее 5612.
> Они попадают в десятку самых больших праймориальных простых чисел. Праймориал - это произведение последовательных простых чисел.
> Пусть П=2*3*5*7*11*...*13033
> Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.

Они не primorial из-за коэффициента перед П. Primorial prime - это простое вида [произведение первых k простых чисел] +/- 1.

Кстати, если вы откроете новое достаточно большое простое число какого-то специального вида - его можно заявить на
http://primes.utm.edu/bios/submission.php
и вписать свое имя в анналы математики ;)


> Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.
Спорное утверждение.
> Причем между ними больше простых нет.
А это очень даже может быть.

Андрей Сапожников.


> > Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.
> Спорное утверждение.
> > Причем между ними больше простых нет.
> А это очень даже может быть.

> Андрей Сапожников.

Уважаемый Андрей! Эти числа в самом деле простые, поскольку не единожды проверял математическим пакетом Mathematika. А вот то, что они последовательные, следует из разработанной мной теории.


> > > Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.


> Уважаемый Андрей! Эти числа в самом деле простые, поскольку не единожды
>проверял математическим пакетом Mathematika. А вот то, что они
>последовательные, следует из разработанной мной теории.

Уважаемый Александр!

Если проверяли - тогда ой! Только зачем проверять несколько раз? И сколько времени пакет Mathematika проверяет простоту числа с количеством десятичных знаков не менее 5612 ? Что за алгоритм ? И что за теория ?
Интересно - честное слово.

Андрей Сапожников.


> Если проверяли - тогда ой! Только зачем проверять несколько раз? И сколько времени пакет Mathematika проверяет простоту числа с количеством десятичных знаков не менее 5612 ? Что за алгоритм ? И что за теория ?

Читайте главу "4.6. Как проверить большое число на простоту" в книге
"Введение в криптографию"


> > > > Тогда Р1=1155*П+1 и Р2=1155*П+13759 простые.

>
> > Уважаемый Андрей! Эти числа в самом деле простые, поскольку не единожды
> >проверял математическим пакетом Mathematika. А вот то, что они
> >последовательные, следует из разработанной мной теории.

> Уважаемый Александр!

> Если проверяли - тогда ой! Только зачем проверять несколько раз? И сколько времени пакет Mathematika проверяет простоту числа с количеством десятичных знаков не менее 5612 ? Что за алгоритм ? И что за теория ?
> Интересно - честное слово.

> Андрей Сапожников.

Конкретно на эти числа Mathematika тратит около 50 минут на простое число.
Зная некоторые закономерности распределения простых чисел, я не генерировал простые числа случайным образом. Я проверял на простоту только конкретные "подозрительные на простоту" числа. Так как другие числа однозначно составные, я и сделал вывод, что это два последовательных простых числа.
Насколько серьезно вы интересуетесь простыми?


> > Если проверяли - тогда ой! Только зачем проверять несколько раз? И сколько времени пакет Mathematika проверяет простоту числа с количеством десятичных знаков не менее 5612 ? Что за алгоритм ? И что за теория ?

> Читайте главу "4.6. Как проверить большое число на простоту" в книге
> "Введение в криптографию"

Что-то сразу не соображу:
В алгоритме Адлемана - Ленстры априорная информация о специфике тестируемого
числа, а именно, его представлении в виде

k*П +r ,

где П - произведение последовательных простых
как-то упрщает вычисления?

Александр работает в основном с числами в таком представлении...


Здравствуйте, Александр!

> Насколько серьезно вы интересуетесь простыми?
Интересуюсь простыми серьезно, т.к. интересоваться серьезно чем-либо другим в математике не позволяет образование - высшее техническое.
Все что смог придумать по этому поводу здесь :
Усовершенствованный алгоритм решета
Доказательство бесконечности близнецов
Первую работу даже пытался опубликовать - не получилось.
Насчет 50 минут на проверку - в архиве форума нашел ваш ответ (С числами до 40 десятичных знаков прекрасно справляется математический пакет "Mathematika"), а здесь 5612 - сомневаюсь я однако.

Успехов.

Андрей Сапожников.


похоже работаете

Усовершенствованный алгоритм решета
Сапожникова

и "Таблица Менделеева-Побережного" :)


> > Читайте главу "4.6. Как проверить большое число на простоту" в книге
> > "Введение в криптографию"

> Что-то сразу не соображу:
> В алгоритме Адлемана - Ленстры априорная информация о специфике тестируемого
> числа, а именно, его представлении в виде

> k*П +r ,

> где П - произведение последовательных простых

Отнюдь. Во-первых, там простые необязаны быть последовательными. А, во-вторых, о числе N там ничего не предполагается априорно.

> как-то упрщает вычисления?

Я думаю, знание разложения N-1 на простые множители упрощает вычисления. Дело в том, что для доказательства простоты достаточно найти элемент порядка N-1. А когда известно разложение N-1, можно легко определить порядок любого элемента.

Но это наблюдение никак не связано с алгоритмом Адлемана-Ленстры. Просто нужда в нем отпадает.

> Александр работает в основном с числами в таком представлении...

Да, для kП+1 простоту легко доказать, не прибегая к алгоритму Адлемана-Ленстры.

Кстати, я хотел на самом деле сослаться на алгоритм Миллера-Рабина, который значительно проще, но является вероятностным. Он описан в главе "4.4. Как отличить составное число от простого".
Для практических приложений его как правило достаточно.



> Я думаю, знание разложения N-1 на простые множители упрощает вычисления.
сабж
т.е. задача факторизации

> Дело в том, что для доказательства простоты достаточно найти элемент порядка N-1.

> А когда известно разложение N-1, можно легко определить порядок любого элемента.

Имхо, не так чтоб совсем легко определяются первообразные корни. Или есть оценки сложности?

> Но это наблюдение никак не связано с алгоритмом Адлемана-Ленстры. Просто нужда в нем отпадает.

Это-то понятно...


> Кстати, я хотел на самом деле сослаться на алгоритм Миллера-Рабина, который значительно проще, но является вероятностным.
> Он описан в главе "4.4. Как отличить составное число от простого".

Я в курсе...

> Для практических приложений его как правило достаточно.

Не сильно много "массовых" практических задач, где нужно тестирование на простоту.
По утверждению того же Ященко, задача тестирования больших целых на простоту - вне криптопроблем.


> Здравствуйте, Александр!

> > Насколько серьезно вы интересуетесь простыми?
> Интересуюсь простыми серьезно, т.к. интересоваться серьезно чем-либо другим в математике не позволяет образование - высшее техническое.
> Все что смог придумать по этому поводу здесь :
> Усовершенствованный алгоритм решета
> Доказательство бесконечности близнецов
> Первую работу даже пытался опубликовать - не получилось.
> Насчет 50 минут на проверку - в архиве форума нашел ваш ответ (С числами до 40 десятичных знаков прекрасно справляется математический пакет "Mathematika"), а здесь 5612 - сомневаюсь я однако.

> Успехов.

> Андрей Сапожников.

Андрей, обращаю ваше внимание, что существуют две различные задачи:
а) разложение числа на множители
б) генерация новых простых чисел

Так вот первая задача намного сложнее, чем вторая. На этом основывается метод криптографии RSA. Я же сейчас предложил одно из решений второй задачи.


>
> > Я думаю, знание разложения N-1 на простые множители упрощает вычисления.
> сабж
> т.е. задача факторизации

Никакой факторизации. Я говорю про случай, когда разложение N-1 известно априори в силу выбора N. Как в случае Александра с N=k*П+1.

> > Дело в том, что для доказательства простоты достаточно найти элемент порядка N-1.
> > А когда известно разложение N-1, можно легко определить порядок любого элемента.

> Имхо, не так чтоб совсем легко определяются первообразные корни.

В случае простого N понятия "первообразный корень" и "элемент порядка N-1" совпадают.

> Или есть оценки сложности?

Ну количество таких элементов равно phi(N-1), что пропорционально N. Т.е. перебрав некоторое число случайных элементов мы с большой вероятностью натолкнемся на такой элемент. При этом доказывается, что его степень действительно N-1, что и завершает доказательство простоты N.

Элемент x имеет порядок N-1, если
x^(N-1) = 1 (mod N) и
x^((N-1)/p) <> 1 (mod N) для всех простых чисел p делящих N-1.

[...]

> Не сильно много "массовых" практических задач, где нужно тестирование на простоту.
> По утверждению того же Ященко, задача тестирования больших целых на простоту - вне криптопроблем.

Да, но тем не менее в прошлом году строго доказали, что она полиномиальна. Доказательство тут: http://www.cse.iitk.ac.in/news/primality.html


Доброе утро, Михалыч!

Вот еще один претендент на кооперацию
В. П. Голиков НЕКОТОРЫЕ АНАЛИТИЧЕСКИЕ СВОЙСТВА РЕШЕТА ЭРАТОСФЕНА
Как говорится - идеи витают в воздухе, хоть там вроде о мелодиях говорилось.

Успехов.

Андрей Сапожников.


Уважаемый Refl!
1. Оставим в покое специфику случая, рассматриваемого А.Побережным.

> >
> > > Я думаю, знание разложения N-1 на простые множители упрощает вычисления.
> > сабж
> > т.е. задача факторизации

> Никакой факторизации. Я говорю про случай, когда разложение N-1 известно априори в силу выбора N. Как в случае Александра с N=k*П+1.

> > > Дело в том, что для доказательства простоты достаточно найти элемент порядка N-1.

2. Предлагаю предположить также, что Ваш собеседник в курсе проблематики

> > > А когда известно разложение N-1, можно легко определить порядок любого элемента.

> > Имхо, не так чтоб совсем легко определяются первообразные корни.

> В случае простого N понятия "первообразный корень" и "элемент порядка N-1" совпадают.
и, следовательно, писать банальности не имеет смысла.
> > Или есть оценки сложности?

> Ну количество таких элементов равно phi(N-1), что пропорционально N. Т.е. перебрав некоторое число случайных элементов мы с большой вероятностью натолкнемся на такой элемент. При этом доказывается, что его степень действительно N-1, что и завершает доказательство простоты N.

> Элемент x имеет порядок N-1, если
> x^(N-1) = 1 (mod N) и
> x^((N-1)/p) <> 1 (mod N) для всех простых чисел p делящих N-1.

> [...]

Меня интересуют детерминированные алгоритмы отыскания первообразного корня.
Если есть факторизация (р-1), то все распараллеливается.
Но эта факторизация может быть "плохой"

Например ("софижерменовской" :-)

47 = 2*23+1
далее
23=2*11+1
итд

Вроде бы "плохих" простых не очень много, что следует из результатов П.Эрдеша (1935)
Думаю, что можно доказать, что иерархически плохо факторизуемых цепочек, порождающих простые не очень много - таких простых до N асимптотически
О(N/((logN)^2)...
Но более новых результатов типа эрдешевских я не видел.
Буду благодарен за любую информацию.

> > Не сильно много "массовых" практических задач, где нужно тестирование на простоту.
> > По утверждению того же Ященко, задача тестирования больших целых на простоту - вне криптопроблем.

> Да, но тем не менее в прошлом году строго доказали, что она полиномиальна. Доказательство тут: http://www.cse.iitk.ac.in/news/primality.html
Я читал статью.

Неоднозначно я отношусь к "О"-оценкам. Там еще в символе "О" константа живет.
А мы не в асимптотике живем.
Кстати, у меня один мальчонка попробовал упомянутый "полиномиальный" алгорим реализовать. Хуже он работает, чем Ленстры...
То ли "по жизни", то ли программа неудачная...


> 2. Предлагаю предположить также, что Ваш собеседник в курсе проблематики

К сожалению, Вы смешиваете в кучу много разных вещей, и не всегда понятно о чем идет речь.

> > > > А когда известно разложение N-1, можно легко определить порядок любого элемента.

> > > Имхо, не так чтоб совсем легко определяются первообразные корни.

> > В случае простого N понятия "первообразный корень" и "элемент порядка N-1" совпадают.
> и, следовательно, писать банальности не имеет смысла.

Это не банальность, это синхронизация терминологии. ;) Если Вам больше нравится понятие "первообразный корень" - буду придерживаться его.

> > > Или есть оценки сложности?

> > Ну количество таких элементов равно phi(N-1), что пропорционально N. Т.е. перебрав некоторое число случайных элементов мы с большой вероятностью натолкнемся на такой элемент. При этом доказывается, что его степень действительно N-1, что и завершает доказательство простоты N.

> > Элемент x имеет порядок N-1, если
> > x^(N-1) = 1 (mod N) и
> > x^((N-1)/p) <> 1 (mod N) для всех простых чисел p делящих N-1.

> Меня интересуют детерминированные алгоритмы отыскания первообразного корня.
> Если есть факторизация (р-1), то все распараллеливается.

Распараллеливание здесь ни к чему. Кстати, предложенный выше алгоритм является детерминированным, ожидаемое время работы которого полиномиально (но есть ничтожно малая вероятность экспоненциального времени работы). Хотя если справедлива расширенная гипотеза Римана, то его время работы можно сделать полиномиальным всегда.

> Но эта факторизация может быть "плохой"

> Например ("софижерменовской" :-)

> 47 = 2*23+1
> далее
> 23=2*11+1
> итд

В свете отыскания первообразных корней они совсем не "плохие", а очень даже хорошие. Здесь хорошесть меряется соотношением phi(N-1)/(N-1). Для "софижерменовских" чисел это соотношение равно ((N-1)/2-1)/(N-1) - почти 1/2. Т.е. практически каждый второй элемент является первообразным корнем.

> Вроде бы "плохих" простых не очень много, что следует из результатов П.Эрдеша (1935)
> Думаю, что можно доказать, что иерархически плохо факторизуемых цепочек, порождающих простые не очень много - таких простых до N асимптотически
> О(N/((logN)^2)...
> Но более новых результатов типа эрдешевских я не видел.
> Буду благодарен за любую информацию.

Я не понимаю, о чем Вы говорите. И почему это "софижерменовские" простые для Вас "плохие"? И вообще что значит "плохие" в Вашем понимании? О каком именно результате П.Эрдеша (1935) идет речь?

> > > Не сильно много "массовых" практических задач, где нужно тестирование на простоту.
> > > По утверждению того же Ященко, задача тестирования больших целых на простоту - вне криптопроблем.

> > Да, но тем не менее в прошлом году строго доказали, что она полиномиальна. Доказательство тут: http://www.cse.iitk.ac.in/news/primality.html
> Я читал статью.

> Неоднозначно я отношусь к "О"-оценкам. Там еще в символе "О" константа живет.
> А мы не в асимптотике живем.
> Кстати, у меня один мальчонка попробовал упомянутый "полиномиальный" алгорим реализовать. Хуже он работает, чем Ленстры...
> То ли "по жизни", то ли программа неудачная...

"По жизни" не может быть, но вот от длины числа - зависит. И начиная с некоторой длины (возможно, очень большой) полиномиальный алгоритм будет превосходить субэкспоненциальный алгоритм Адлемана-Ленстры.
Кстати, проверить удачная программа или нет можно сравнив с "профессиональной" реализацией этого же алгоритма (хотя бы по скорости) в последних версиях Pari/GP:
http://www.math.u-psud.fr/~belabas/pari/


Так а в чем прикол? Существуют же два множества, {2^k-1, k-простое} и {2^2^n+1, n-натуральное}, состоящие из простых чисел. Подставляйте k или n и считайте простые числа хоть из дециллиона знаков.


> Так а в чем прикол? Существуют же два множества, {2^k-1, k-простое} и {2^2^n+1, n-натуральное}, состоящие из простых чисел. Подставляйте k или n и считайте простые числа хоть из дециллиона знаков.

Кто Вам такую глупость сказал?

2^11 - 1 = 2047 = 23*89
2^(2^5)+1 = 4294967297 = 641 * 6700417


>> А вот то, что они последовательные, следует из разработанной мной теории.

Уважаемый Александр!

Вычитал, что Э. Лебон в своих работах рассматривал прогрессии вида BK+I, где B=2*3*5...pn, I - взаимно простое с B положительное число для охоты за "большими" простыми числами.

Успехов!

Андрей Сапожников.


> >> А вот то, что они последовательные, следует из разработанной мной теории.

> Уважаемый Александр!

> Вычитал, что Э. Лебон в своих работах рассматривал прогрессии вида BK+I, где B=2*3*5...pn, I - взаимно простое с B положительное число для охоты за "большими" простыми числами.

> Успехов!

> Андрей Сапожников.


Андрей, буду весьма признателен, если пришлете ссылку на него. Хотелось бы познакомиться с его подходом.


> Андрей, буду весьма признателен, если пришлете ссылку на него. Хотелось бы познакомиться с его подходом.

Добрый вечер, Александр!


Собственно это я вычитал в книге Эльнатанов Б.А., "Развитие метода решета", изд. "Дониш", Душамбе, 1984 г.
Дословно :числу I придается φ(B) =(2-1)(3-1)...(pn-1) значение и решается неопределенное уравнение BK+I=MD, где D - число вида BK'+I', а K и M неизвестные. В случае существования целочисленных решений рассматриваемого уравнения числа BK+I составные, в противном случае число BK+I простое. Э.Лебон на основании составленных им таблиц значений K, когда оно принимает возможные значения от 17 до B, предлагает приемы быстрого вычисления K и M. Так принимая B=2*3*5*7*11*13=30030, сравнительно быстро исследуются числа от 1 до B*B=9011800900. Конец цитаты.
В Инете книги этой не нашел, скорее всего нет ее там.

Успехов.

Андрей Сапожников.


> > Андрей, буду весьма признателен, если пришлете ссылку на него. Хотелось бы познакомиться с его подходом.
>
> Добрый вечер, Александр!

>
> Собственно это я вычитал в книге Эльнатанов Б.А., "Развитие метода решета", изд. "Дониш", Душамбе, 1984 г.
> Дословно :числу I придается φ(B) =(2-1)(3-1)...(pn-1) значение и решается неопределенное уравнение BK+I=MD, где D - число вида BK'+I', а K и M неизвестные. В случае существования целочисленных решений рассматриваемого уравнения числа BK+I составные, в противном случае число BK+I простое. Э.Лебон на основании составленных им таблиц значений K, когда оно принимает возможные значения от 17 до B, предлагает приемы быстрого вычисления K и M. Так принимая B=2*3*5*7*11*13=30030, сравнительно быстро исследуются числа от 1 до B*B=9011800900. Конец цитаты.
> В Инете книги этой не нашел, скорее всего нет ее там.

> Успехов.

> Андрей Сапожников.

Андрей, я рассуждал немного по другому. Если интересно, то загляните на мой сайт http://paii1.narod.ru/ideya/simple1.htm Я попытался коротко изложить свою идею. Обращаю ваше внимание на приложение, где можно оценить, как красиво простые записываются в таблицы. Как вы понимаете, эту закономерность я использовал для поиска новых простых чисел.
С уважением Александр.


Здравствуйте, Александр!

Зашел на Ваш сайт, показалось, что где-то уже я это видел. Поискал вроде здесь
http://www.omsu.omskreg.ru/vestnik/articles/y1998-i3/a013/article.html ,
и еще по моему в журнале Квант, но ссылку не нашел.

Успехов!

Андрей.


Очень нужна информация по лажевым числам мерсенна
вида 2^a +/- 2^b +/- 2^c ... +/- 2^0
Например, 2^384-2^128-2^96+2^32-1 - простое.
Они имеют все достоинства нормальных чисел Мерсенна
1) Простой быстрый детерминированный тест типа Лукаса-Ламера =).
2) Простое взятие модуля-вычета-остатка (магические свойства "девятки")

Внимание, а теперь вопрос:
как в натуре выполнять действия 1 и 2?
Как, к примеру, быстро взять модуль 9909 в десятичной системе,
чего-йта никак сообразить не могу.

Ах да, совсем забыл, а чем лажевые числа мерсена лучше обычных?
А тем, что их можно состряпать скока душе угодно для любого 2^a,
а нормальных чисел мерсена - только 40 штук на сегодня.


I need an information about nongenuine (generalized?) Mersenne numbers
in terms of 2^a +/- 2^b +/- 2^c ... +/- 2^0,
for instance, 2^384-2^128-2^96+2^32-1 is prime.
I believe, they have all the advantages of regular mersenne numbers:
1) there is a fast deterministic Lucas-Lahmer-like test;
2) there is a way of simple modular reduction based on magic figure "nine"
properties (I don't mean IBWDFFT here...)

How can I perform the items 1 and 2 really?
For example, how can I get a residue from division by 9909 in the decimal numeration?

Sorry, I have forgotten completely, why are nongenuine mersenne numbers much
better than regular mersenne numbers? Because there are a lot of them,
contrary to 40-ty known regular ones.
29 декабря 2003 г. 14:12:



я нашёл простое число, которое содержит больше 13 000 000 количество цифр. прошу дать совет, как опубликовать мой результат и доказательства...


Ничего себе заявочка!!!
За такое число полагается приз - $100,000.
В долг и в ожидании этих денег работает 100 человек-экспертов на GIMPS, не считая тыщ подключившихся добровольцев...
Вообщета я малешка разбираюсь в простых числах как никто другой,
хотя в математике мои познания невелики.
Прямая экспериментальная проверка простоты такого числа может занять
от 2 месяцев до 2 лет. Соостветствующее програмное обеспечение
свободно валяется в сети. Если это праймориал - то это концы, нужно возводить в степень по модулю отдельно для каждого делителя N-1. Если обобщенный-мерсен-ферма-прот типа a*b^n +/- 1, то в степень нужно возвести один или пару раз.
Проверка делимости на 200,000,000 первых простых < 2^32 на пне4 занимает несколько секунд (независимо от длины числа ессно - модульная арифметика), рекомендую проверить для начала.

А вообщета, даже доказательсто чисел мерсена такой длины тестом Лукаса-Ламера требует 3 месяца круглосуточной работы ЭВМ. Если вы пытаетесь состряпать рекордное число из уже имеющихся размером, скажем, по 2 млн цифр каждое,
то без малой теоремы FERMAT вам все равно не обойтись, а это ГОД работы P4.

Короче, скорее всего у вас ашипка. Обычно люди наивно полагают, что каждый факториал+1 или праймориал+1 всегда простое число, неправильная интерпретация доказательства Евклида. А может, вы позарились на двойной мерсен MM127?


>> я нашёл простое число, которое содержит больше 13 000 000 количество цифр. прошу дать совет, как опубликовать мой результат и доказательства...
>
> Зайди на http://www.eff.org/awards/coop.html. Организация Electronic Frontier Foundation (EFF) оплачивает такие простые числа (ест-но, после проверки). Ваше стоит $50,000. Там описана процедура сдачи/приемки числа.
> Советую предварительно самому убедиться в простоте числа с помощью общедоступных и проверенных программ (добраться до них можно, например, начиная с http://www.utm.edu/research/primes/prove/index.html.
>


А самое малое простое число какое?
1
3
5...


в чём суть?

ИНДИЙСКИЕ МАТЕМАТИКИ НАШЛИ УНИКАЛЬНЫЙ АЛГОРИТМ ПОИСКА ПРОСТЫХ ЧИСЕЛ


> в чём суть?

Вот еще оттуда же:

ОБНАРУЖЕНА "ПУШИСТАЯ" АКУЛА, КОТОРАЯ ПРЫГАЕТ ПО ДНУ КАК ЛЯГУШКА

До первого апреля далеко еще вроде бы. Жажда сенсаций. Что попало публикуют. И что характерно и для статьи о простых числах и для статьи про мохнатую акулу, так это то, что нет ссылок на источники. Сплетни собирают.

Модератору: правила я знаю, но трудно удержаться, не судите строго.


> в чём суть?
Агравал и сотоварищи (Agrawal-Saxena-Kayal) в 2002 г. (так-что "Известия" жуют новость двухлетней свежести) придумали детерминированный алгоритм проверки натуральных чисел на простоту с полиномиальной сложностью (грубо говоря - для проверки больших чисел на простоту количество арифметических операций зависит от длины числа (=количества цифр) как полином фиксированной степени). Степень полинома изначально у них получилась 12 (http://www.cse.iitk.ac.in/news/primality.html см. также http://www.ams.org/notices/200305/fea-bornemann.pdf). В 2003 г. Ленстра и Померанс (см. http://developer.apple.com/hardware/ve/pdf/aks3.pdf) снизили степень полинома до 6. На сегодня лучшие реализации алгоритма ASK на числах, востребованных для нужд практики (криптография) не могут конкурировать по скорости с наиболее быстрыми экспоненциальными вероятностными алгоритмами (хороший обзор с массой ссылок - http://primes.utm.edu/prove/prove4_1.html).


за пояснения.


мало подробностей про закуску.

ЛЮБОЕ СПИРТНОЕ ПОЛЕЗНО ДЛЯ СЕРДЦА


Как сгенерировать простое число

Нужно взять произвольное число , которое наверняка является простым , обозначим его "А". Затем разделить "А" на два с остатком. Так как число "А" простое , то нацело на два оно не делится и остаток равен еденице. Результат деления числа "А" на два с остатком обозначим "В". Далее обозначим два числа "В" и "В + 1". Перемножим эти два числа "В" и "В + 1" между собой и результат умножения обозначим как "С". Если к "С" прибавить или отнять еденицу то получим простое число. При этом "С + 1" или "С - 1"больше чем "А". Можно повторить преобразования вместо "А" используя "С + 1" или "С - 1".

Существует нестрогое доказательство справедливости приведенных рассуждений.
11 мая 2005 г. 12:40:


> Как сгенерировать простое число

> Нужно взять произвольное число , которое наверняка является простым , обозначим его "А". Затем разделить "А" на два с остатком. Так как число "А" простое , то нацело на два оно не делится и остаток равен еденице. Результат деления числа "А" на два с остатком обозначим "В". Далее обозначим два числа "В" и "В + 1". Перемножим эти два числа "В" и "В + 1" между собой и результат умножения обозначим как "С". Если к "С" прибавить или отнять еденицу то получим простое число. При этом "С + 1" или "С - 1"больше чем "А". Можно повторить преобразования вместо "А" используя "С + 1" или "С - 1".

Для каждого А = 2 mod 7 (в силу теоремы Дирихле среди них имеется бесконечно много простых чисел) соответствующее ему число С + 1 (вычисленное по вашим формулам) делится на 7, т. е. имеется бесконечно много простых А, для которых С+1 - составное число. Наименьшее из них есть А = 23.
Аналогично, для чисел А = 4 mod 11 соответствующие им числа С - 1 делится на 11 (наименьшее из них - А=37). Т. е. и здесь имеется бесконечно много простых А, для которых С-1 - составное число.
И, наконец, для чисел А = 77t + 37 (среди них, в силу той же теоремы, имеется бесконечно много простых чисел) одновременно выполняется А = 2 mod 7 и А = 4 mod 11. Поэтому для всех простых чисел такого вида оба числа С-1 и С+1 являются составными.

> Существует нестрогое доказательство справедливости приведенных рассуждений.

К математическим утверждениям, полученным в результате нестрогих доказательств, следует относиться с осторожностью.

> 11 мая 2005 г. 12:40:


Слушайте,а я не понимаю,ЗАЧЕМ вычислять самые большие простые числа.Можно ведь просто записать 10 миллионов или даже несколько миллиардов нечетных чисел,да и всё!А то всё подсчитывают,подсчитывают...


> Слушайте,а я не понимаю,ЗАЧЕМ вычислять самые большие простые числа.Можно ведь просто записать 10 миллионов или даже несколько миллиардов нечетных чисел,да и всё!А то всё подсчитывают,подсчитывают...

0. Несколько миллиардов нечётных чисел - это числа, не превышающие 1010.
А наибольшее полученное простое число - http://www.arsfoodcourt.com/43.txt
содержит 9,152,052 разрядов...
1. Практическая польза от простых чисел сейчас связана в основном с криптографией, в частности, с очень важными, особенно для гражданских приложений, шифрами с открытым ключом. Реально используемые числа меньше рекордных, но существенно больше "десятков миллиардов".
2. Постановка рекордных вычислений, кроме спортивного и рекламного интереса, имеет значение для разработки алгоритмов работы с числами сверхбольшой длины, проверки на простоту и т.п.
3. Кроме того, это достаточно сложный и разнообразный, но при этом привлекательный своей эффектностью учебный проект.



старая задачка:какое самое большое число?


Хотел спросить.
Разработал некий ряд. Степенной ряд основанный на возведении 2 в степень.
На его основании получаю список "простых" чисел. Ну естественно в нем есть исключения.

Из первых 100 милл чисел я получаю 109856 простых чисел (причем с очень высокой вероятностью что эти числа являются первыми числами в парах простых чисел), в которых имеются всего 7 исключений. Эти исключения не проходят тест на малой теореме Ферма (который по сути тоже является быстрым степенным методом). Короче эти исключения не являются числами Кармайкла. Итого объединив два метода мой и малую теорему ферма получаем 109849 НАСТОЯЩИХ простых чисел из первых 100 милл начиная с 7. Все эти числа я проверил прямым методом.

Метод на самом деле (как и малая теорема Ферма) позволяет работать с большими числами.
Подскажите как я могу проверить результаты своей работы на ОГРОМНЫХ числах.


> Подскажите как я могу проверить результаты своей работы на ОГРОМНЫХ числах.

Установите Mathematica6. Получите возможность работать без ошибок до миллиона знаков.


> > Подскажите как я могу проверить результаты своей работы на ОГРОМНЫХ числах.

> Установите Mathematica6. Получите возможность работать без ошибок до миллиона знаков.

спасибо за ответ, воспользуюсь советом

еще один вопрос
Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью малой теоремы Ферма???? или есть еще какието исключения???? Или этот вопрос остается открытым???


Теперь можно поблагодарить автора понравившегося сообщения, которое содержит полезную информацию, решение задачи и т.д. Со временем это приведёт к созданию рейтинга авторов сообщений по количеству полученных ими благодарностей от других участников форума. С одной стороны сразу будет видно насколько можно доверять автору сообщения, а с другой стороны это даст некие преференции наиболее популярным авторам, о которых пока говорить чуть рано. Пусть наберётся статистика.

Чтобы поблагодарить автора понравившегося сообщения нажмите ссылку [Поблагодарить] слева в верхней строчке меню (прямо под баннером и заголовком темы). Особенно это касается тех участников форума, которые получили решения своих задач.

Около каждого имени участника форума в круглых скобках зелёным шрифтом отображается общее число благодарностей, поступивших в адрес этого участника.


> > > Подскажите как я могу проверить результаты своей работы на ОГРОМНЫХ числах.

> > Установите Mathematica6. Получите возможность работать без ошибок до миллиона знаков.

> спасибо за ответ, воспользуюсь советом

> еще один вопрос
> Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью малой теоремы Ферма???? или есть еще какието исключения???? Или этот вопрос остается открытым???

Обратитесь на форум
http://dxdy.ru/


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100