Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Просте число



План:


Введення

Просте число - це натуральне число, яке має рівно два різних натуральних дільника : одиницю і саме себе. Всі інші числа, крім одиниці, називаються складовими. Таким чином, всі натуральні числа більше одиниці розбиваються на прості і складові. Вивченням властивостей простих чисел займається теорія чисел. В теорії кілець простим числам відповідають незвідні елементи.

Послідовність простих чисел починається так:

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, ... (послідовність A000040 в OEIS,)

1. Розкладання натуральних чисел у твір простих

Основна теорема арифметики стверджує, що кожне натуральне число, більше одиниці, представимо у вигляді добутку простих чисел, причому єдиним способом з точністю до порядку слідування співмножників. Таким чином, прості числа - елементарні "будівельні блоки" натуральних чисел.

Подання натурального числа у вигляді добутку простих називається розкладанням на прості або факторизації числа. На даний момент невідомі поліноміальні алгоритми факторизації чисел, хоча і не доведено, що таких алгоритмів не існує. На передбачуваної великий обчислювальної складності задачі факторизації базується криптосистема RSA і деякі інші. Факторизація з поліноміальною складністю теоретично можливе на квантовому комп'ютері за допомогою алгоритму Шора.


2. Алгоритми пошуку та розпізнавання простих чисел

Прості способи знаходження початкового списку простих чисел аж до деякого значення дають Решето Ератосфена, решето Сундарама і решето Аткіна.

Однак, на практиці замість отримання списку простих чисел найчастіше потрібна перевірити, чи є дане число простим. Алгоритми, вирішальні цю задачу, називаються тестами простоти. Існує безліч поліноміальних тестів простоти, але більшість їх є ймовірнісними (наприклад, тест Міллера - Рабіна) та використовуються для потреб криптографії. В 2002 було доведено, що задача перевірки на простоту в загальному вигляді поліноміальних розв'язана, але запропонований детермінований тест Агравал - Каяла - Сакса має досить велику обчислювальну складність, що ускладнює його практичне застосування.

Для деяких класів чисел існують спеціалізовані ефективні тести простоти (див. нижче).


3. Нескінченність безлічі простих чисел

Простих чисел нескінченно багато. Найстаріше відоме доказ цього факту було дано Евклідом в " Засадах "(книга IX, затвердження 20). Його доказ може бути коротко відтворено так:

Уявімо, що кількість простих чисел звичайно. Перемножимо їх і додамо одиницю. Отримане число не ділиться ні на одне з кінцевого набору простих чисел, тому що залишок від ділення на будь-яке з них дає одиницю. Значить, число має ділитися на деякий просте число, не включене в цей набір. Суперечність.

Математики пропонували інші докази. Одне з них (наведене Ейлером) показує, що сума величин, зворотних до перших n простим числам, необмежено зростає із зростанням n.

Теорема про розподіл простих чисел стверджує, що кількість простих чисел менших n, позначуване \ Pi (n) , Росте як n / \ ln (n) .


4. Найбільше відоме просте

Здавна ведуться записи, що відзначають найбільші відомі на той час прості числа [1]. Один з рекордів поставив свого часу Ейлер, знайшовши просте число 2 ^ {31} -1 = 2147483647 .

Найбільшим відомим простим числом за станом на лютий 2011 року є 2 ^ {43112609} - 1 . Воно містить 12978189 десяткових цифр і є простим числом Мерсенна (M 43112609). Його знайшли 23 серпня 2008 на математичному факультеті університету UCLA в рамках проекту по розподіленому пошуку простих чисел Мерсенна GIMPS.

Числа Мерсенна вигідно відрізняються від решти наявністю ефективного тесту простоти : тесту Люка - Лемера. Завдяки йому прості числа Мерсенна давно утримують рекорд як найбільші відомі прості.

За знаходження простих чисел з більш ніж 100 000 000 і 1000000000 десяткових цифр EFF призначила [2] грошові призи відповідно в 150 000 і 250 000 доларів США. Раніше EFF вже присуджувала призи за знаходження простих чисел з 1 000 000 і 10000000 десяткових цифр.


5. Прості числа спеціального виду

Існує ряд чисел, простота яких може бути встановлена ​​ефективно з використанням спеціалізованих алгоритмів.

  • Числа Мерсенна - числа виду M_p = 2 ^ p-1 , Де p - просте число (послідовність A001348 в OEIS). Як вже було зазначено вище, ефективним тестом простоти є тест Люка-Лемера. Прості числа Мерсенна утворюють послідовність A000668 в OEIS.
  • Числа Ферма - числа виду F_n = 2 ^ {2 ^ n} +1 , Де n - невід'ємне ціле число (послідовність A000215 в OEIS). Ефективним тестом простоти є тест Пепін. Станом на листопад 2011 року відомо лише 5 простих чисел Ферма (для n = 0, 1, 2, 3, 4), і висловлена ​​гіпотеза, що інших простих чисел Ферма немає.
  • Числа Вудалла (англ.) - числа виду W_n = n \ cdot 2 ^ n-1 (Послідовність A003261 в OEIS). Ефективним тестом простоти є тест Люка-Лемера-Різель (англ.). Прості числа Вудалла утворюють послідовність A050918 в OEIS.

З використанням тесту Бріллхарта-Лемера-Селфрідж (​​англ.) може бути перевірена простота наступних чисел:

  • Числа Куллена (англ.) - числа виду C_n = n \ cdot 2 ^ n +1 (Послідовність A002064 в OEIS). Прості числа Куллена утворюють послідовність A050920 в OEIS.
  • Числа Прота - числа виду P = k \ cdot 2 ^ n +1 , Причому k непарній і 2 ^ n> k (Послідовність A080075 в OEIS). Числа Куллена є окремим випадком чисел Прота при k = n. Числа Ферма є окремим випадком чисел Прота при k = 1 і n = 2 ^ m . Прості числа Прота утворюють послідовність A080076 в OEIS.

Для пошуку простих чисел позначених типів в даний час використовуються проекти розподілених обчислень GIMPS, PrimeGrid, Ramsey @ Home, Seventeen or Bust, Riesel Sieve, Wieferich @ Home.


6. Деякі властивості

  • Безліч позитивних значень многочлена
    \ Begin {align} & (k +2) (1 - [wz + h + j - q] ^ 2 - [(gk + 2g + k + 1) (h + j) + h - z] ^ 2 - [ 2n + p + q + z - e] ^ 2 - \ \ & [16 (k + 1) ^ 3 (k + 2) (n + 1) ^ 2 + 1 - f ^ 2] ^ 2 - [e ^ 3 (e + 2) (a + 1) ^ 2 + 1 - o ^ 2] ^ 2 - [(a ^ 2 - 1) y ^ 2 + 1 - x ^ 2] ^ 2 - \ \ & [16r ^ 2y ^ 4 (a ^ 2 - 1) + 1 - u ^ 2] ^ 2 - [((a + u ^ 2 (u ^ 2 - a)) ^ 2 - 1) (n + 4dy) ^ 2 + 1 - (x + cu) ^ 2] ^ 2 - [n + l + v - y] ^ 2 - \ \ & [(a ^ 2 - 1) l ^ 2 + 1 - m ^ 2] ^ 2 - [ai + k + 1 - l - i] ^ 2 - [p + l (a - n - 1) + b (2an + 2a - n ^ 2 - 2n - 2) - m] ^ 2 - \ \ & [q + y (a - p - 1) + s (2ap + 2a - p ^ 2 - 2p - 2) - x] ^ 2 - [z + pl (a - p) + t (2ap - p ^ 2 - 1) - pm] ^ 2) \ end {align}
при невід'ємних цілих значеннях змінних в точності збігається з безліччю простих чисел. [6] [7] [8] Цей результат є окремим випадком доведеною Юрієм Матіясевічем діофантових будь-якого перечислимого безлічі.

7. Відкриті питання

Розподіл простих чисел p n = fs n); Δ s n = p n +1 - p n. Δ p n = p n +1 - p n; Δ p n = 2, 4, 6, ....

До цих пір існує багато відкритих питань щодо простих чисел, найбільш відомі з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі [9] :

  1. Проблема Гольдбаха (перша проблема Ландау): чи вірно, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел?
  2. Друга проблема Ландау: нескінченно Чи безліч "Простих близнюків" - простих чисел, різниця між якими дорівнює 2?
  3. Гіпотеза Лежандра (третя проблема Ландау) чи вірно, що для всякого натурального числа n між n ^ 2 і (N + 1) ^ 2 завжди знайдеться просте число?
  4. Четверта проблема Ландау: нескінченно Чи безліч простих чисел вигляду n ^ 2 + 1 , Де n - натуральне число?

Відкритою проблемою є також існування нескінченної кількості простих чисел в багатьох цілочисельних послідовностях, включаючи числа Фібоначчі, числа Ферма і т. д.


8. Додатки

Великі прості числа (порядку 10 ^ {300} ) використовуються в криптографії з відкритим ключем. Прості числа також використовуються в хеш-таблицях і для генерації псевдовипадкових чисел (зокрема, в ГПСЧ вихор Мерсенна).


9. Варіації і узагальнення


Примітки

  1. Рекорди простих чисел по роках - primes.utm.edu / notes / by_year.html
  2. EFF Cooperative Computing Awards - www.eff.org / awards / coop (Англ.)
  3. Доказ . Непарне число p, не кратне 3, дорівнює 1 або 2 по модулю 3 і дорівнює 1, 3, 5 або 7 по модулю 8. При зведенні в квадрат це дає 1 по модулю 3 і 1 по модулю 8. Віднімаючи 1, отримуємо 0 по модулю 3 і 0 по модулю 8. Отже, p ^ 2-1 кратно 3 і кратно 8; отже, воно кратно 24.
  4. Weisstein, Eric W. Теорема Гріна-Тао - mathworld.wolfram.com / Green-TaoTheorem.html (Англ.) на сайті Wolfram MathWorld.
  5. Ці 2 властивості безпосередньо випливають з формул розкладання суми і різниці ступенів.
  6. Jones JP, Sato D., Wada H., Wiens D (1976). " Diophantine representation of the set of prime numbers - mathdl.maa.org/images/upload_library/22/Ford/JonesSatoWadaWiens.pdf ". Amer. Math. Mon. +83 (6): 449-464.
  7. Yuri Matiyasevich, Diophantine Equations in the XX Century - www.inf.unisi.ch/guest-lectures/matiyas/Lugano_public1_print.pdf
  8. Matijasevic's polynomial - primes.utm.edu / glossary / page.php? sort = MatijasevicPoly. The Prime Glossary.
  9. Weisstein, Eric W. Landau 's Problems - mathworld.wolfram.com / LandausProblems.html (Англ.) на сайті Wolfram MathWorld.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Випадкове просте число
Незаконне просте число
Просте поле
Просте кільце (алгебра)
18 (число)
e (число)
26 (число)
-1 (Число)
70 (число)
© Усі права захищені
написати до нас