Xreferat.com » Рефераты по математике » Побудова простих великих чисел

Побудова простих великих чисел

alt="Побудова простих великих чисел" width="15" height="17" align="BOTTOM" border="0" /> таке, що Побудова простих великих чисел й Побудова простих великих чисел, то знайдеться простий дільник Побудова простих великих чисел числа Побудова простих великих чисел виду Побудова простих великих чисел при якомусь Побудова простих великих чисел.

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

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

Хоча цей результат слабкіше, ніж теорема Поклінгтона, даний підхід, як показав Н. Дієметко в 1988 р., також може бути ефективно використаний для доведення простоти чисел.

Теорема (Дієметко). Нехай Побудова простих великих чисел, де Побудова простих великих чисел – просте, Побудова простих великих чисел– парне й Побудова простих великих чисел Якщо існує ціле Побудова простих великих чисел таке, що Побудова простих великих чисел й Побудова простих великих чисел , то Побудова простих великих чисел – просте.

Доведення. Нехай Побудова простих великих чисел – не просте й Побудова простих великих чисел. Тоді за лемою отримуємо, що існує таке Побудова простих великих чисел, щоПобудова простих великих чисел.

Позначимо Побудова простих великих чисел Тоді Побудова простих великих чисел, де Побудова простих великих чисел й Побудова простих великих чисел. Звідси Побудова простих великих чисел. Отже, Побудова простих великих чисел, де Побудова простих великих чисел – не може дорівнювати 0, інакше Побудова простих великих чисел – просте, або 1, тому що Побудова простих великих чисел – непарне. Аналогічно,Побудова простих великих чисел. Таким чином,


Побудова простих великих чисел.


Протиріччя. Теорему доведено.

Зазаначимо, що за умовою теореми числа Побудова простих великих чисел й Побудова простих великих чисел можуть бути не взаємно прості. Ця теорема лежить в основі алгоритму генерації простих чисел у вітчизняному стандарті на цифровий підпис Р 34.10-94.

У ньому як Побудова простих великих чисел обираються не дуже високі степені числа 2, а Побудова простих великих чисел перебуває перебором. (З 1 липня 2002 р. цей стандарт був замінений на новий Р 34.10-2001).

Метод Маурера

В 1995 р. У. Маурер опублікував швидкий алгоритм генерації доведених простих чисел, близьких до випадкового. У його основі лежить посилення теореми Поклінгтона на випадок, коли факторизована частина Побудова простих великих чисел числа Побудова простих великих чисел задовольняє нерівності Побудова простих великих чисел. Крім того, йому вдалося оцінити ймовірність успіху при випадковому пошуку числа Побудова простих великих чисел в умові теореми Поклінгтона.

Наступна лема є спеціальним випадком теореми Поклінгтона.

Лема 2. Нехай Побудова простих великих чисел Якщо існує ціле Побудова простих великих чисел таке, що для будь-якого простого дільника Побудова простих великих чисел числа Побудова простих великих чисел виконані умови Побудова простих великих чисел і Побудова простих великих чисел, те кожен простий дільник Побудова простих великих чисел числа Побудова простих великих чисел має вигляд Побудова простих великих чисел при деякому цілому Побудова простих великих чисел Якщо, крім того, Побудова простих великих чисел або Побудова простих великих чисел – парне й Побудова простих великих чисел, то Побудова простих великих чисел – просте.

Доведення. Нехай Побудова простих великих чисел – складене й Побудова простих великих чисел – нетривіальний простий дільник числа Побудова простих великих чисел. Тоді за умови теореми випливає, що Побудова простих великих чисел й Побудова простих великих чисел . Міркуючи аналогічно зауваженню до теореми Люка, отримуємо, що має знайтися елемент, який має порядок рівний Побудова простих великих чисел за модулем Побудова простих великих чисел. У силу малої теореми Ферма Побудова простих великих чисел.

Для доведення другого твердження, припустимо, що Побудова простих великих чисел. Тоді Побудова простих великих чисел.
Якщо Побудова простих великих чисел, то Побудова простих великих чисел Якщо Побудова простих великих чисел - непарне й Побудова простих великих чисел, то Побудова простих великих чисел й


Побудова простих великих чисел

просте число поклінгтон мауер люк

Протиріччя.

Наступна лема доведена Д. Коувером і Дж. Куіскуотером в 1992 р.

Лема 3. Нехай Побудова простих великих чисел і Побудова простих великих чисел задовольняють умову леми 1. Визначимо числа Побудова простих великих чисел й Побудова простих великих чисел рівністю Побудова простих великих чисел. Якщо Побудова простих великих чисел й число Побудова простих великих чисел не дорівнює нулю й не є повним квадратом, то Побудова простих великих чисел - прості.

Доведення. Відповідно до леми 1 для кожного простого дільника Побудова простих великих чисел числа Побудова простих великих чисел виконується нерівність Побудова простих великих чисел За умовою Побудова простих великих чисел. Тому, якщо число

Побудова простих великих чисел – складене, то воно не може мати більше двох простих дільників. Нехай


Побудова простих великих чисел и. Побудова простих великих чисел.


Маємо Побудова простих великих чисел інакше Побудова простих великих чисел.

Якщо Побудова простих великих чисел , то Побудова простих великих чисел

Звідси Побудова простих великих чисел, однак у цьому випадку Побудова простих великих чисел Тому Побудова простих великих чисел.

Отже, Побудова простих великих чисел і Побудова простих великих чисел. За теоремою Вієта Побудова простих великих чисел є коренями квадратного рівняння Побудова простих великих чисел, що має розв’язання в цілих числах у тому і тільки в тому випадку, якщо Побудова простих великих чисел є повним квадратом або нулем. Лему доведено.

Зазначимо, що переконатися, що задане число не є повним квадратом, можна, обчисливши символ Лежандра для декількох маленьких простих модулів. Якщо при деякому модулі число не буде квадратичним відрахуванням, то воно не буде й повним квадратом.

Нехай Побудова простих великих чисел – функція Ейлера.

Лема 4. Нехай Побудова простих великих чисел – просте число й Побудова простих великих чисел. Позначимо через Побудова простих великих чисел число елементів Побудова простих великих чисел, порядок яких ділиться на Побудова простих великих чисел. Тоді справедлива оцінка


Побудова простих великих чисел,


причому рівність виконується в тому й у тільки в тому випадку, коли Побудова простих великих чисел


Доведення. Використовуючи властивості функції Ейлера, отримуємо


Побудова простих великих чисел

причому рівність виконана в тому і тільки в тому випадку, коли


Побудова простих великих чисел

Размещено на

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: