Страница простых чисел

1. простые числа
2. простые множители
3. жк и кгв
4. Специальные номера
5. Запись простых чисел
6. Предположения и открытые вопросы
7. вероятностный тест на простоту и метод rho
8. Безопасный домашний банкинг с 128 битами?
9. Факторизация больших чисел

Matheseitenberblick • Пифагорейские пустяки • назад • © Арндт Брннер

... работает только если Javascript активирован

Пояснения: простые числа • простые множители жк и кгв • специальные номера • Primzahlstze • Догадки, вопросы Использование больших простых чисел в безопасных методах шифрования

Пояснения: простые числа • жк и кгв • специальные номера • Primzahlstze • Догадки, вопросы

простые числа

... являются натуральными числами, которые делятся только на себя и 1 (без остатка). Число 1 удовлетворяет этому условию, но не принадлежит множеству простых чисел. Любое натуральное число n> 1 может быть однозначно представлено как произведение простых чисел (кроме порядка). (Напр .: 2345 = 5767), что Первичная факторизация (см. Ниже) называется. Если нейтральный элемент умножения, номер 1, принадлежал простым числам, то это правило не сработало.
P = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 , 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 ...}

Существует бесконечно много простых чисел. Всегда можно сформировать произведение всех найденных простых чисел и добавить 1. Ни один из используемых факторов не может быть делителем полученного числа, потому что остаток всегда остается равным 1. Это означает, что это число должно иметь ранее неизвестное простое число в качестве делителя! Поэтому всегда находите другое простое число, независимо от того, сколько уже известно.

Греческий математик Эратосфен (c. 275 - 194 до н.э.) описал метод для нахождения всех простых чисел вплоть до предела m, который сегодня называется Сито Эратосфена известен. В списке натуральных чисел> 1 и ≤ m удалите все кратные 2, затем следующего оставшегося числа 3, затем следующего еще не удаленного числа (5) и т. Д. Простые числа остаются.

Если мы хотим проверить, является ли число n простым числом , то достаточно найти возможные делители t числа только для t с t2 <n, поскольку большие числа m больше не могут быть делителями n, если нет меньших делителей: мм> п. При проверке, является ли число 5987 простым числом, оно должно проверяться только для простых чисел до √5987, то есть до 73, если они делят 5987. Если нет простого числа до 5987, то 5987 - простое число. (Это она.)

простые множители

Любое натуральное число может быть записано как произведение простых чисел, уникальных для заказа. Этот продукт называется простой факторизацией числа. Примеры: 700 = 22557; 562309 = 11179731. Нет другого способа приблизиться к этому продукту, кроме этих факторов, когда все факторы должны быть простыми числами. Дальнейшие примеры любого числа через форму выше.

Чтобы получить простую факторизацию, каждый обычно проходит через простые числа снизу (то есть 2, 3, 5, 7 ...) и проверяет, будет ли разделенное число гладко делиться ими без остатка. В этом случае запишите простое число, разделите число, которое нужно разделить, на простое число и продолжайте с результатом (частным), пока в конце не останется только простое число.

Пример: 2394 должен быть разложен на простые факторы. 2394 делится на 2, поэтому: 2 записывается, а 2394: 2 = 1197 вычисляется. 1197 больше не делится на 2, но на 3. Примечание 3 , частное: 1197: 3 = 399. 399 снова делится на 3: обратите внимание на второе 3 , частное: 133. Это больше не делится на 3 и не на 5, а на 7. Примечание 7 ; 133: 7 = девятнадцатый Это простое число, т.е. простое факторизация находится с 2394 = 233719 или 232719.

жк и кгв

Наибольший общий делитель (gcd) двух чисел является произведением тех простых чисел, которые разделяют в точности два разложения на простые множители.
Пример: 53667 = 336789 | 459486 = 233367127 | НОД (53667; 459486) = 3367 = 603
Без простой факторизации жкд двух чисел равен Евклидов алгоритм определить.
Если для двух чисел a и b: gcd (a; b) = 1, то a и b не имеют общего делителя. Следовательно, они также означают разногласия .

Наименьшее общее кратное (кгВ) двух чисел является произведением всех простых чисел, которые встречаются при первичной факторизации двух чисел, и на наибольшую встречающуюся степень. Пример: кгВ (53667; 459486) = 23336789127 = 40894254.
Применяется gcd (a; b) kgV (a; b) = ab и, следовательно, kgV (a; b) = ab / gcd (a; b).

�� Новая интерактивная страница на тему: Как найти gcd?
→ старая страница об алгоритме Евклида

Специальные номера

Числа Mk = 2k-1 (k ∈ IN) называются числами Мерсенна . Mk может быть простым, только если k - простое число. Было найдено, что для k <20000 точно 24 простых числа Мерсенна для k ∈ {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941 11213, 19937}. 219937-1 - это номер с 6002 цифрами ( посмотри здесь ). Они еще выше Простые числа Мерсенна известно, например 2756839-1 число с 227 832 цифрами или число, найденное в 1999 году как простое число 26972593-1 с 2 098 960 цифрами или (обнаружено в ноябре 2003 года) числом Мерсенна 220996011-1 с 6320430 цифрами ,
Последний (сентябрь 2006) был обнаружен с 232582657-1 простое число с числом 9808358.
Есть ли бесконечно много этих простых чисел, неизвестно.

Числа Fk = +1 с k ∈ IN горячими числами Ферма . Пьер де Ферма (1601-1665) предположил, что все эти числа были простыми числами. Для k ∈ {0, 1, 2, 3, 4} это верно, но для более высоких k очевидно, что пока что ничего не найдено. но даже несуществование такого числа еще не доказано.

Совершенными числами называются числа, равные сумме их истинных делителей, кроме самих себя, но включающие 1:
{6, 28, 496, 8128, 33550336, 8589869056, ...}. 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + 14. На Пифагоре идея состоит в том, чтобы вернуться назад, поскольку совершенные числа всегда являются суммой последовательных чисел: 28 = 1 + 2 + 3 + 4 + 5 + 6 + 7, 8128 = 1 + 2 + ... + 126 + 127. Евклид обнаружил, что совершенные числа всегда можно представить как 2n-1 (2n-1), где n - натуральное число. И наоборот, эта формула всегда возвращает идеальное число тогда и только тогда, когда n равно единице. Мерсенн Прайм есть. Например, 219936 (219937-1) является совершенным числом. 232582657-1 - самый большой известный совершенный номер.

Дружественные числа - это два числа, сумма делителей которых равна другому числу. Они были из Пьер Ферма изучали и описывали, но были ранее известны. 220 и 284 - дружественные номера, 1184 и 1210; 17296 и 18416 и 9363584 и 9437056.
→ Список всех известных дружественных номеров (отсортировано по количеству цифр) - внешняя страница

Вы можете проверить в вышеприведенной форме, является ли число идеальным, в области простой факторизации. Введите число в поле ввода и активируйте опцию «Определить количество делителей». Затем вычисляется не только набор делителей, но и сумма делителей, которую можно сравнить с данным числом.
Дружественные числа или так называемые «общительные числа», которые образуют замкнутую цепочку (например, 1264460-1547860-1727636-1305184-1264460), можно найти с помощью опции «Подытог Подытог». Таким образом, сумма делителей автоматически переносится в поле ввода, поэтому вам нужно всего лишь несколько раз нажать на кнопку, чтобы проверить эпизод. Также обратите внимание на простую факторизацию дружественных пар чисел! Есть ли правило?
Самая длинная известная цепочка социальных номеров состоит из 28 чисел и начинается с 14316. Попробуйте и найдите еще больше!

Запись простых чисел

Магазины Ферма:
Если p простое число, а n натуральное число, которое не кратно p, то np-1 всегда на 1 больше, чем следующее меньшее кратное p (так называемое маленькое предложение Ферма → доказательство).

Примеры: a) 45-1 = 44 = 25 6 , 25 5 = 551 b) 1317-1 = 1316 = 66541660918317984 1 , 66541660918317984 0 = 3914215348136352017

Любое простое число p, которое генерируется p = 4n + 1 (n ∈ IN), может быть однозначно представлено как сумма двух целочисленных квадратов (например, 233 = 82 + 132).

Теорема Лагранжа : каждое натуральное число n должно представлять сумму не более четырех квадратов целых чисел.

Теорема Дирихле . Если gcd (a, b) = 1, то существует бесконечно много простых чисел p вида p = na + b (n ∈ IN).

Теорема о трех основных числах. Каждое нечетное натуральное число ≥9 является суммой трех нечетных простых чисел. (Сравните с гипотезой Гольдбаха)

Предположения и открытые вопросы

Простые двойники : два простых числа, примыкающих к серии нечетных чисел, называются простыми двойниками, например: 3 и 5; 17 и 19 или 10007 и 10009. До сих пор неясно, существует ли бесконечно много простых близнецов.

Совершенные числа называются числами, равными сумме их истинных делителей, кроме самих себя, но включая 1. ( См выше .) Есть много чисел, сумма делителей которых только на единицу меньше числа, например, все степени 2; однако пока не найдено ни одного числа, у которого сумма делителей равна 1 или даже немного больше, чем само число.На сегодняшний день также не доказано, могут ли такие числа существовать вообще. Прежде всего, до сих пор неясно, существуют ли четные нечетные совершенные числа .

Есть много других нерешенных проблем с простыми числами! Вообразите больше этого.

вероятностный тест на простоту и метод rho

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

В так называемом методе RSA публикуется «пара ключей» из двух чисел e и n, где n - произведение двух очень больших простых чисел p и q, а e - это число, которое не имеет общего делителя с (p-1) (q- 1) имеет. Кстати, этим произведением является набор чисел <n, у которых нет общего делителя с n, кроме 1. С формулой xe mod n → y числа шифруются. «mod n» означает, что при делении на n учитывается только остаток от числа xe. В результате результаты настолько «запутаны», что уже не видят, откуда они берутся. Кроме того, и это интригующая вещь, с числами n и e, процесс не собирается возвращаться!

Следовательно, эти два числа также могут быть опубликованы - они используются для шифрования сообщений для владельца пары ключей. Он единственный, кто знает два простых числа p и q, с помощью которых он может вычислить число d, которое может снова декодировать зашифрованные числа: yd mod (p-1) (q-1) → x.

Безопасные интернет-соединения обычно работают жизненно важно в этой системе. Прежде всего, ключ передается с каждой страницы, с которой контрагент возвращает ключ к обычному шифрованию. Обычное («симметричное») шифрование намного быстрее, и, кроме того, шифрование RSA становится еще более безопасным, если с помощью ключа RSA передается только небольшое количество информации, то есть только симметричный ключ.

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

Первое желание более или менее выполняется с помощью процедуры, называемой вероятностным тестом на простоту. «Пробар» - латинское слово для дегустации, тестирования, пробования. Проверяемое число, возможный главный кандидат, проходит специальную математическую процедуру (здесь скоро появится специальная страница), где можно очень быстро решить, определенно не является ли оно простым числом или является простым числом с вероятностью 75%. , Если тест выполняется сто раз при определенных условиях, то коэффициент ошибок чрезвычайно низок, а именно (1/4) 100 ~ 6,22310-59%.

Название метода rho происходит от греческой буквы ρ. Это дал ей разработчик Джон Майкл Поллард, потому что этот процесс иногда имеет периодические последствия. Сам метод главным образом учитывает большие числа с высокой степенью достоверности (но также и с возможными ошибками, вероятность которых числовое утверждение еще не может быть сделано) на высокой скорости.

В 1640 году Ферма написал Мерсенну, он подозревает, что 232 + 1 = 4294967297 это простое число, но оно не может однозначно доказать это. Ни он, ни Мерсенн не решили проблему, хотя именно с точки зрения Ферма деление любого числа ap-1 на p оставляет остаток 1, если p - простое число, а a не кратно p, ключ все быстрый вне. (Сравните выше → Мерсенн номера .)

Почти 150 лет назад английский экономист В.С. Джевонс считал маловероятным, чтобы кто-нибудь когда-либо узнал, на какие два числа он умножил 8616460799 получить. Даже медленный Javascript за этой страницей выходит через несколько секунд; но метод ро делает это за полчаса.

Поскольку оба метода предоставляются через апплет Java на этой странице, Java должна быть активирована. Я выбрал решение Java из-за огромных преимуществ в скорости и того факта, что апплет теоретически может обрабатывать произвольно большие числа; также практически за пределы 32-битных чисел или даже 15 цифр. Даже мой самый медленный на данный момент компьютер (Pentium I, 100 МГц, 32 МБ ОЗУ, но на котором были созданы все эти страницы) разлагает 55-значный продукт на соответственно наибольшее простое число из одной, двух, трех и десяти цифр (7 97 997 9973 99991 999983 9999991 99999989 999999937 9999999967 = 6750622348964143051956305469326962117763788889781985387) в среднем 17 секунд (и в настоящее время мой самый быстрый в 2).

Безопасный домашний банкинг с 128 битами?

Замечание о безопасности безопасных интернет-соединений. До недавнего времени в США запрещали экспорт браузеров с программными модулями, которые могли шифровать и дешифровать ключи размером более 40 бит. Сегодня ключи являются общими с 128-битным (и могут быть экспортированы).

Если бы это были ключи RSA, это было бы не очень хорошо для секретности, как вы можете прочитать или попробовать в нижней части этой страницы, потому что там факторизация таких чисел через апплет возможна в очень короткое время. Если вам известны ключевые факторы ключа, вы можете декодировать закодированные с ним сообщения (см. Выше).

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

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

Однако фактические ключи RSA для безопасных интернет-соединений с RSA сегодня имеют 1924 бита и не могут быть учтены в обозримом будущем с помощью известных в настоящее время методов.

Безопасный обмен данными может работать по следующей схеме: если секретные данные должны передаваться из А в В, B сначала отправляет свой открытый ключ RSA в A. Это кодирует его симметричный ключ в RSA с помощью полученного ключа RSA и отправляет его в кодировке B кто может расшифровать его своим секретным ключом. Теперь А кодирует свое сообщение симметрично и отправляет его B. Теперь, когда у него есть симметричный ключ, он может расшифровать сообщение.
Сегодня симметричное 128-битное шифрование (DES, 3DES, AES, Blowfish, IDEA, CAST и т. Д.) Распространено в Интернете и поддерживается новыми экспортными версиями браузеров.

Факторизация больших чисел

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

Очевидно, что 40-битные ключи RSA имеют секретную открытку, написанную в памфлете, в 64-битном формате это может быть почерк, подобный моему. И с 128-битными ключами ...? Java-апплет на этом сайте уже испытывает трудности. На моем самом быстром компьютере он работает с алгоритмом CF Моррисона и Брильхардта, в конце концов, в среднем за полчаса.

CF означает продолжение фракции. Эволюция квадратного корня из числа, подлежащего факторизации, в (не заканчивающуюся) непрерывную дробь - смотри мою страницу - и в результате краткосрочных разрывов генерируются числа, которые можно использовать для решения скрытых факторов, хотя и с довольно высокими вычислительными затратами. QF обозначает квадратные формы; также этот алгоритм основан на продолжении дробного разложения √N. По моему опыту, скорость двух алгоритмов непрерывной дроби зависит не только от тактовой частоты процессора, но и в значительной степени от доступной памяти компьютера. Конечно, вычисления с очень большими целыми числами в основном занимают много памяти; однако алгоритм rho далеко не так сильно зависит от этого аспекта. Кстати, алгоритм CF не намного быстрее для небольших чисел, чем для больших. Поэтому рекомендуется только для факторинга очень больших чисел, в которых процесс Rho подметает паруса. Однако число в двух алгоритмах непрерывной дроби сначала делится на первые 10000 простых чисел (до 104729). Так что, если все основные факторы, кроме одного в этой области, опять же, эти два имеют преимущество - но только из-за вышестоящего Pro Division.
Очень интересно сравнение (скорости) с более чем 200-летним алгоритмом, который Карл Фридрих Гау использовал для письменного факторинга больших чисел. Вероятно, он обнаружил это независимо от Эйлера, у которого несколько десятилетий назад был похожий алгоритм. Конечно, современные алгоритмы основаны на идеях Гау и Эйлера. В любом случае, старую процедуру наверняка скрывать не пришлось!

Достаточно мощная математическая программа, такая как Derive, может разложить 128-битный ключ за считанные минуты. Продолжительность является переменной и зависит от самого числа непредсказуемым образом. (С Derive она менялась не слишком много попыток от 2 до 14 минут). Java, язык программы за этой страницей, все еще довольно медленный против машинных программ или даже программ на C ++. Установите максимальное время ожидания.

Постскриптум: Я подозреваю, что да, потому что «наполовину мощная» программа Derive, настолько хорошие сервисы, которые она до сих пор доказала мне, и мне нравится работать с ней, все еще находится на вершине, но, поскольку есть такая разница, я действительно не ожидал: после Когда я написал это, я получил Mathematica версии 4.2. Это учитывает все протестированные 128-битные ключи на моем ноутбуке за мгновение, всего за 4 секунды. (Как это возможно?!)

Симметричные ключи теперь передаются с использованием 1924-битных ключей RSA. До сих пор не известно ни одного математического метода, чтобы разложить такие числа в течение жизни. Но кто знает: может быть, уже есть машины, которые используют секретные математические методы для взлома больших ключей за считанные минуты или хотя бы день!

Версия: 7. 3. 2005

© Арндт Брннер
Matheseitenberblick
назад

Проект GIMPS
Размер на данный момент известного простого числа (7816230 мест)

Похожие

Комментарии