Участник:Forodirch/Простые числа
Материал из Lurkmore
Простые числа — это все те натуральные числа, которые делятся только на себя и на единицу. Простое определение, проходят в школе. Это вообще первый специальный класс натуральных чисел, выделенный человечеством из всего многообразия натуральных чисел. Один из главнейших поставщиков лулзов и butthurtа в математике начиная со времен древних греков. С ними связаны многие нерешенные до сих пор проблемы математики и они же поставили немало пациентов в псих. больницы всего человечества. Однако же обо всем по порядку.
Содержание |
Древние греки
С развитием общества математика, как часть философии (в хорошем смысле слова) почувствовала необходимость в формальных определениях и точных доказательствах. Собственно одним из первых, изучаемых древними греками, понятий математики стали натуральные числа. После осознания того, что междву семью баранами и семью деревьями есть нечто общее, а именно число семь, появилось четко оформленное понятие натурального числа. Греки, уже умеющие умножать числа, подметили что некоторые числа можно собрать умножением из меньших чисел, а некоторые нельзя. Так и произошло разбиение чисел на простые и составные.
Первым вопросом, который заинтересовал греков в связи с простыми числами был вопрос конечности. Доказательство бесконечности множества простых чисел само по себе цугундер, ибо является одним из первых дошедших до нас математических доказательств и, сцуко, красивое. Предположим, что множество всех простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из простых чисел, значит или просто, или имеет делителем не перечисленное простое число. Противоречие.
Но что, сука, характерно не известно конечно ли число простых чисел такого вида.
=== пифагор===
гармония
Возрождение
Мерсен, Ферма, Эйлер, Гольдбах, Гаусс же
Кетай
Адский трехчлен
Новое время
Тьюринг, дойчланд. Дзета-функция
ТРК
Начиная с середины XX века, изучение простых чисел обрело второе дыхание. Новые вопросы были связаны с поиском больших простых чисел. Собственно основной вопрос: "зачем?". А разгадка проста - проклятый капитализм. В современном мире нужно шифровать данные, пересылаемые по интернету. Причем алгоритм должен быть таким, чтобы им мог быстро зашифровать отправитель, быстро расшифровать тот, кому отправлен мессадж, а тот кто мессадж перехватил его расшифровать не мог. По возможности, никогда. Дополнительно требуется еще чтобы алгоритм исправлял ошибки, то есть если дошли не все символы или в части символов есть ошибки, то чтобы восстановить исходное сообщение можно было всё равно. За алгоритмы, удовлетворяющие этим требованиям между прочем платят нормальное такое бабло (вместе с подпиской о невыезде и жизнью под колпаком). Алгоритмов разной степени эффективности можно вспомнить много, но наиболее известен б-гомерзкий RSA. Собственно процесс дешифрации перехватчиком (если попросту) сводится к тому, что нужно произвести численное логарифмирование в простом поле. Сие, по общепринятому мнению, на данный момент делается только полным перебором. А поскольку количество перебираемых вариантов напрямую зависит от степеней ОЧЕНЬ больших простых чисел, задача эта необозримая.
Наши дни, совок
Виноградов Распределение простых чисел, Чебышев