Открыли большие простые числа

[Evgeniy Sklyarevskiy]

Математики обнаружили два самых больших простых числа в истории
Добавил Vlad2000Plus Vlad2000Plus 19 часов 43 минуты назад
Группы математиков из США и Германии обнаружили два самых больших простых числа в истории. Данное открытие может значительно увеличить эффективность систем шифрования, применяемых в современной вычислительной технике. Оба числа были открыты с разницей в пару недель и каждое в рамках проекта Great Internet Mersenne Prime Search (GIMPS), длящегося уже 12 лет.

Самое большое простое число было обнаружено 23 августа учеными из Университета Калифорнии, это число содержит 12 979 189 цифр. Второе число, содержащее 11 185 272 цифры, было обнаружено двумя неделями раньше в Германии.

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

Спонсирует поиск крупнейших простых числе фонд EFF (Electronic Frontier Foundation), который намерен в перспективе создать систему шифрования данных, которую без ключа взломать невозможно в принципе.

http://news2.ru/story/123037/

[Azamat Davletmuratov]

Афигеть!!!
Но - с точки зрения математика - это ни есть самая большая цифра (хоть простая, хоть сложная). Цифры бесконечны. (лежачая восьмерка).

[Vitaliy Fioktistov]

Афигеть!!!
Но - с точки зрения математика - это ни есть самая большая цифра (хоть простая, хоть сложная). Цифры бесконечны. (лежачая восьмерка).

Цифры как раз таки конечны, бесконечны числа :)

[Timur Salikhov]

Афигеть!!!
Но - с точки зрения математика - это ни есть самая большая цифра (хоть простая, хоть сложная). Цифры бесконечны. (лежачая восьмерка).

Азамат простое число это число не имеющее делителей без остатка кроме себя и единицы, и их количество не бесконечно.

[Evgeniy Sklyarevskiy]

Афигеть!!!
Но - с точки зрения математика - это ни есть самая большая цифра (хоть простая, хоть сложная). Цифры бесконечны. (лежачая восьмерка).

Азамат простое число это число не имеющее делителей без остатка кроме себя и единицы, и их количество не бесконечно.

А мне казалось, что количество простых чисел бесконечно. Точно не помню теорию, но вроде так. На Арбузе были статьи про простые числа, не могу найти сходу.

[Odil Abdullaev]

ЕС, Вы правы. Множество простых чисел бесконечно

[Nadir Zaitov]

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

Eсли P(i) - простое число с номером i, то числа:

P(1)*P(2)*...*P(N)+1
P(1)*P(2)*...*P(N)-1заведомо простые для любого простого N.

Чтоб набрать их и превзойти товарищей нужно 1,6 млн. простых чисел, которые надежно лежат в интервале от 1 до 30 млн. - исходя из формулы Чебышева (а это 32 разрядная целочисленная арифметика и 100 мегобайта памяти - задача почти для школьника). Далее нужны 1,6 млн. вполне распаралеливаемых произведений при этом реально больших произведений нужно не так уж и много:

1 умножение 6 000 000 значных чисел.
2 умножения 3 000 000 значных чисел.
4 умножения 1 500 000 значных чисел.
8 умножений 750 000 значных чисел и т.д.Каждое сверхбольшое умножение тоже можно рапаралелить. и что? Это такая проблема? А сколько за такой расчет денег дают? Может и нашим институтам в европе такой грант выбыить, а? Умы то у нас эту задачку за нечего делать решат без суперкомпьютеров.

[Nadir Zaitov]

А мне казалось, что количество простых чисел бесконечно. Точно не помню теорию, но вроде так. На Арбузе были статьи про простые числа, не могу найти сходу.

В сущности указанная мной выше формула очередного простого числа доказывает их бесконечность. Чебышев доказал, что число простых чисел в интервале от 1 до N (с точностью до коэффициента) приблизительно равно N/ln(N), а эта последовательность точно уходит в бесконечность.

[Vitaliy Fioktistov]

А мне казалось, что количество простых чисел бесконечно. Точно не помню теорию, но вроде так. На Арбузе были статьи про простые числа, не могу найти сходу.

В сущности указанная мной выше формула очередного простого числа доказывает их бесконечность. Чебышев доказал, что число простых чисел в интервале от 1 до N (с точностью до коэффициента) приблизительно равно N/ln(N), а эта последовательность точно уходит в бесконечность.

Вообще, есть Евклидово, Пойа и Эйлерово доказательства бесконечности ряда простых чисел. Некоторых идиотов они не устраивают, поэтому появляются подобные измышления: http://lit.lib.ru/s/sergej_e_s/text_0100.shtml

[Nadir Zaitov]

В сущности - вопрос в сложности больших (длинных) произведений.
Eсли P(i) - простое число с номером i, то числа:

P(1)*P(2)*...*P(N)+1
P(1)*P(2)*...*P(N)-1заведомо простые для любого простого N.


Я видимо погоречился. :shok: Вношу свои извинения за впыльчивый характер. Подумав внимательно нашел ошибку.

[Vitaliy Fioktistov]

В сущности - вопрос в сложности больших (длинных) произведений.
Eсли P(i) - простое число с номером i, то числа:

P(1)*P(2)*...*P(N)+1
P(1)*P(2)*...*P(N)-1заведомо простые для любого простого N.


Я видимо погоречился. :shok: Вношу свои извинения за впыльчивый характер. Подумав внимательно нашел ошибку.

Насчет -1?

[iDead]

Eсли P(i) - простое число с номером i, то числа:
P(1)*P(2)*...*P(N)+1
P(1)*P(2)*...*P(N)-1заведомо простые для любого простого N.


та формула верна, если P(1)*P(2)*...*P(N) - это произведение ВСЕХ простых чисел от 2 до P(N) включительно.
Если предположить, что P(N)- самое большое простое число, а m - любое простое число, меньшее P(N), то легко увидеть, что дробь (P(1)*P(2)*...*P(N)+1)/m будет несокращаемой (т.е. не будет целым числом), так как P(1)*P(2)*...*P(N)/m будет давать целое число, а 1/m - заведомо не сокращается. Учитывая, что составное число состоит из произведения простых чисел, а также тот факт, что если число не делиться на одно из двух чисел, то оно не будет делиться на произведение этих двух чисел, то можно сказать, что число P(1)*P(2)*...*P(N)+1 не будет сокращаться ни на какое целое число, т.е. будет простым. :)

З.Ы. Кстати задача о несуществовании самого большого простого числа давалась на областной олимпиаде по математике для 9 -10 классов (кажется все же для 9го класса) в начале девяностых. :)

[Georgick]

число P(1)*P(2)*...*P(N)+1 не будет сокращаться ни на какое целое число, т.е. будет простым.


Евклид. 300 лет до н.э. «Начала», книга IX, ©

[Makarov]

И что с того? Тупейшая задача по перемалыванию чисел. Теорему Ферма оказалось слабо доказать, хотя больше века бьются.

[Evgeniy Sklyarevskiy]

Теорему Ферма оказалось слабо доказать, хотя больше века бьются.

Окончательно доказана в 1995 году Уайлсом.

http://ru.wikipedia.org/wiki/%D0%A4%D0%B5%D1%80%D0%BC%D0%B0_%D0%B2%D0%B5%D0%BB% D0%B8%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D 0%B5%D0%BC%D0%B0

[Makarov]

Evgeniy Sklyarevskiy,
Вот и как после этого читать газеты? Буквально на прошлой неделе одна из них утверждала что теорема еще не доказана.
Усе, завязываю читать в газетах все кроме гороскопа! :)

[Azamat Davletmuratov]

Я видимо погоречился. Вношу свои извинения за впыльчивый характер. Подумав внимательно нашел ошибку.
А то смотрю и считаю на бумажке - как это так? Все равно под конец согласно вашей формуле выходит цифра которая делится и на "3".


Цифры как раз таки конечны, бесконечны числа
Извиняюсь - цифрами можно назвать согласно закону математики - от нуля до девяти. Дальше идут числа. Но никак не цифры.


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

[Azamat Davletmuratov]

Теорему Ферма
Какая теорема? те что в кубе сумма получается число в кубе ? Она (теорема) доказана уже. Щас хотят доказать что в пятой степени равно пятой степени другого числа.

[Georgick]

Evgeniy Sklyarevskiy,
Вот и как после этого читать газеты? Буквально на прошлой неделе одна из них утверждала что теорема еще не доказана.
Усе, завязываю читать в газетах все кроме гороскопа! :)


Боже Вас сохрани – не читайте до обеда "местные" газеты.

- Так ведь других нету?

- Ну вот никаких и не читатйте. ©

[nop]

Eсли P(i) - простое число с номером i, то числа:
P(1)*P(2)*...*P(N)+1
P(1)*P(2)*...*P(N)-1заведомо простые для любого простого N.


та формула верна, если P(1)*P(2)*...*P(N) - это произведение ВСЕХ простых чисел от 2 до P(N) включительно.
Если предположить, что P(N)- самое большое простое число, а m - любое простое число, меньшее P(N), то легко увидеть, что дробь (P(1)*P(2)*...*P(N)+1)/m будет несокращаемой (т.е. не будет целым числом), так как P(1)*P(2)*...*P(N)/m будет давать целое число, а 1/m - заведомо не сокращается. Учитывая, что составное число состоит из произведения простых чисел, а также тот факт, что если число не делиться на одно из двух чисел, то оно не будет делиться на произведение этих двух чисел, то можно сказать, что число P(1)*P(2)*...*P(N)+1 не будет сокращаться ни на какое целое число, т.е. будет простым. :)

З.Ы. Кстати задача о несуществовании самого большого простого числа давалась на областной олимпиаде по математике для 9 -10 классов (кажется все же для 9го класса) в начале девяностых. :)

А ты попробуй на P(N)=13 и будет облом:187:

[Nadir Zaitov]

И что с того? Тупейшая задача по перемалыванию чисел. Теорему Ферма оказалось слабо доказать, хотя больше века бьются. Вроде доказано, что Большая теорема Ферма по аксиоматике выскакивает за пределы аксиоматики натуральных чисел. Ее доказали в 1995 году (через 300 лет) на 130 страницах через особые свойства эллиптических кривых над полем рациональных чисел. Если это просто и тупо... то Вы видать гений.
:worship8nz:

[Nadir Zaitov]

Насчет -1?

Неа. с +1 и -1 проблем нету - доказательство по Евклиду одинаковое. В указанной мной последовательности бесконечно много простых чисел. Просто получившиеся числа могут быть и составным - делиться на простые числа большего номера, чем N. Там нужно еще помозговать. А вот случай N=13 я вроде проверил. Число вроде не составное.

[nop]

Насчет -1?

Там нужно еще помозговать. А вот случай N=13 я вроде проверил. Число вроде не составное.

Значит не так уж хорошо проверил, потому что 2*3*5*7*11*13+1=30031=59*509;:cray:
P(N)=17,19,23 тоже составные, вобщем там больше составных, чем простых.
Больше месяца ломал голову, потом сказали что гипотеза не верна.
А вот тебе и прога, проверяй на здоровье:
#include <iostream.h>

void main(){
int i=2,n;
cin>>n;
while(n%i)i++;
cout<<n<<"="<<i<<"*"<<n/i<<endl;
}

[Nadir Zaitov]

Значит не так уж хорошо проверил, потому что 2*3*5*7*11*13+1=30031=59*509;:cray:
Это N=6, но в любом случае спасибо. Речь была о томже. Кстати, я почти сразу обнаружил ошибку и сообщил об этом. Сорри, что Вы месяц потеряли. Жесть.

[nop]

Кстати, я почти сразу обнаружил ошибку и сообщил об этом. Сорри, что Вы месяц потеряли. Жесть.
Не за что извиняться, я не о вас. Дело в том, что мы с другом подумали, что таким образом (умножая), можно получить большие простые числа, а потом через месяц спросили у преподавателя есть ли такая теорема?
Через неделью приходит и говорит, что P(N)=13 составное. Было обидно...:cray: