2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки



Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Генерация больших простых чисел
Сообщение18.04.2017, 08:30 
Аватара пользователя


14/09/12
181
Уфа
Здравствуйте.

Дано такое утверждение:
Цитата:
Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.

Пусть $N$, $S$ --- нечётные натуральные числа, $N-1 = S R$, причем для каждого простого делителя $q$ числа $S$ существует целое число $a$ такое, что

$a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$
Тогда каждый простой делитель $p$ числа $N$ удовлетворяет сравнению $p = 1(\mod 2S)$

Следствие.

Если выполнены условия теоремы Ферма и $R \leqslant 4S+2$, то $N$ --- простое число.
http://algolist.manual.ru/maths/teornum/gene_prime.php
Как получили выражение для условия $R \leqslant 4S+2$? Почему поставили такое ограничение $a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$? Не могли бы вы позадавать наводящие вопросы, чтобы я смог понять? Спасибо.

 Профиль  
                  
 
 Re: Генерация больших простых чисел
Сообщение18.04.2017, 10:58 


15/11/15
208

(Оффтоп)

netang в сообщении #1210365 писал(а):
Не могли бы вы позадавать наводящие вопросы, чтобы я смог понять? Спасибо.

Чувак то жгет :)

 Профиль  
                  
 
 Re: Генерация больших простых чисел
Сообщение18.04.2017, 11:16 
Заслуженный участник
Аватара пользователя


01/03/06
12814
Москва
netang, скажите, если некоторое натуральное число меньше выбранного модуля и сравнимо с единицей по этому модулю, то можно ли точно назвать такое число?

 Профиль  
                  
 
 Re: Генерация больших простых чисел
Сообщение18.04.2017, 13:12 
Аватара пользователя


14/09/12
181
Уфа
Я могу ошибаться, но посмею предположить, что только единица удовлетворяет этому условию.

 Профиль  
                  
 
 Re: Генерация больших простых чисел
Сообщение18.04.2017, 13:55 
Заслуженный участник
Аватара пользователя


01/03/06
12814
Москва
Верно. А зачем я это спросил?

 Профиль  
                  
 
 Re: Генерация больших простых чисел
Сообщение18.04.2017, 20:25 
Заслуженный участник


08/04/08
8322
netang в сообщении #1210365 писал(а):
Почему поставили такое ограничение $a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$?
Это можно понять, прочитав про тест простоты Люка (например в Вики: https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BA%D0%B0), он проще, чем это утверждение, и сильно понятнее.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group