Выполнение условий теоремы Поклингтона

как напитать программу? тема: теорема Поклингтона. что бы выполнялось условие теоремы?

Теорема Поклингтона
Пусть n = q^k * R + 1 где q - простое число, k \geqslant 1. Если существует такое целое число a , что a^{n-1} \equiv 1 \pmod n и НОД(a^{{(n-1)}/q} - 1, n) = 1, то каждый простой делитель p числа a имеет вид p = q^kr + 1 при некотором натуральном r

Критерий Поклингтона
Пусть n - натуральное число. Пусть число n -1 имеет простой делитель q, причем q > \sqrt {n} -1 . Если найдётся такое целое число a, что выполняются следующие два условия:

a^{n-1} \equiv 1 \pmod n
числа n и ~a^{(n-1)/q} -1 взаимнопросты,
то n - простое число.

Доказательство критерия Поклингтона
Предположим, что n является составным числом. Тогда существует простое число p - делитель n, причем p < \sqrt {n} . Заметим, что q > p -1 , следовательно q и p -1 - взаимнопросты. Следовательно, существует некоторое целое число u, такое, что uq \equiv 1 \pmod{p-1}. Но в таком случае ~a^{(n-1)/q}\equiv a^{uq(n-1)/q} = a^{u(n-1)}\equiv 1 \pmod p (в силу условия 1)). Но таким образом получено противоречие условию 2). Следовательно, n является простым числом.

Замечания к критерию Поклингтона
Теорема Поклингтона является отличным тестом на простоту при условии, что n-1 делится на простое число q > \sqrt {n} -1 , а также если q можно найти и доказать его простоту. Иначе, этим критерием пользоваться нельзя. Так же стоит отметить, что этот критерий является вероятностым только в том смысле, что случайно выбранное число a может либо удовлетворять условию НОД ~(a^{(n-1)/q} -1, n) = 1 , либо не удовлетворять ему. Однако, как только найдено такое a, критерий доказывает, что n - простое число. В отличие от вероятностных тестов (таких, например, как тест Миллера-Рабина, тест Соловея-Штрассена и др.) заключение теста Поклингтона - вполне определенное.



Пример
Докажем, что число n=31 является простым. Найдём простой делитель числа n-1, т.е. 30. Им является q=5, причём 5 > \sqrt {31} -1. Число a=2 удовлетворяет обоим критериям:

2^{30} \equiv 1 \pmod {31}
числа 31 и ~2^{(31-1)/5} -1 взаимнопросты,
Следовательно число 31 простое по критерию Поклингтона

0

Я так понимаю, формулы надо расшифровать.

0

А, нет. Всё ясно. Зря я Вам про редактор формул написал. Это у Вас перепечатка статьи из Википедии: Критерий Поклингтона.

И... Собственно, в чём состоит Ваш вопрос? Найти определённые числа по критерию Поклингтона? Ну-ну. А если вдруг не найдём, тогда что? И вот ещё вопрос: нужно ли доказывать, что таких чисел не существует? Написано же:

Сообщение от Ewgen <Условия использования> ... Иначе, этим критерием пользоваться нельзя

Опишите задачу подробнее.

0

нужно написать программу что бы при вводе с компьютера любого числа, она дала ответ простое это число или нет, опираясь на вот эту теорему. при помощи теоремы можно определять простоту числа. я сама математик и в программировании не очень силен, а программа очень нужна. если кто сможет написать, то это бы мне очень помогло.

0

Сообщение от Ewgen при вводе с компьютера любого числа

Максимальное целое число, представимое с помощью стандартных типов паскаля точно (да и других языков тоже), это 2⁶⁴-1 (тип uint64). До этого числа (число Мерссена, какое оно там, 63 или 64 по порядку) все простые числа и без того прекрасно известны. Получается, критерий этот при вычислениях с помощью стандартных типов данных вроде бы как-то и не требуется. Хотя... Может быть, вычислений при тесте простоты поменьше будет при достаточно большом числе для тестирования.

Тогда вопрос. Насколько большое число Вы желаете видеть в качестве максимального для конкретной реализации теста?

Если больше, чем указанное - конечно, можно применить biginteger из Pascal ABC.NET или длинную арифметику, но с этого места нужно уже разговаривать поподробнее.

Итак?

1

на сколько оно может быть максимальным, такое и хочу видеть. и еще что бы открывалась а АВС паскале.

0

Сообщение от Ewgen что бы открывалась а АВС паскале

Боюсь, что от этого... Нет, матом нельзя... Недоделанного учебного диалекта паскаля Вам придётся отказаться. Максимально ёмкий тип данных в этом диалекте - integer - охватывает диапазон чисел -2³¹..2³¹-1. Это учебный диалект паскаля, в котором ампутировано всё, что можно и нельзя.

Сообщение от Ewgen на сколько оно может быть максимальным, такое и хочу видеть

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

Поскольку требуется упихать в программу не только само n, но и a^(n-1)/q-1, всё равно придётся использовать длинную арифметику. И, чтобы проверка критерия происходила за приемлемое время, все числа, используемые при проверке критерия, должны находиться в памяти. Само n можно считать из файла в память, не вопрос.

Предлагаю использовать Free Pascal (может быть, плюс Lazarus), и решить всё с помощью длинной арифметики. Или - давайте перенесём тему в Pascal ABC.NET, и попытаемся решить задачу с помощью типа BigInteger. В этом случае я устраняюсь: ABC.NET я знаю плохо.

В любом случае, требуется конкретизация, а не это:

Сообщение от Ewgen на сколько оно может быть максимальным

Может-то он может, но вряд ли у Вас есть собственный числогрыз с быстродействием хотя бы 10 GFlop/s. Давайте так. Пусть будет максимально возможное число, такое, чтобы все числа для проверки критерия поместились в памяти, с одной стороны, и чтобы для проверки критерия требовалось менее часа на одно число.

0

ну тогда как получится. если мах 2^64 то пусть это и будет мах

0

Буду пробовать.

Сообщение от Ewgen если мах 2^64

Нет, придётся забавляться с длинной арифметикой, потому что a^(n-1)/q-1, и если число близко к a⁶⁴, а q=2, то всё равно будет примерно 2⁽²⁶³⁾. Не так прост этот критерий, как кажется.

0

ну что там ничего не выходит?

0

Пока не очень. Со временем туго, в разъездах был последнее время.

0

У FPC вроде бы есть штатный модуль для длинной арифметики - http://wiki.freepascal.org/gmp (и ещё ссылка http://www.freshports.org/math/fpc-gmp).

Добавлено через 3 минуты
При условии наличия на компе динамической библиотеки gmp.dll.

1

Хм... Не знал. Завтра гляну, что за зверь.

0

Этот модуль на форуме время от времени использует volvo. Есть даже примеры Найти все элементы начального отрезка из n членов последовательности Фибоначчи, являющиеся квадратами, Циклический алгоритм вычисления произведения всех чисел от 25 до 40.

1

Не обращал внимания... volvo обычно оперирует для этих целей ABC.NET'ом, а там biginteger. Ладно, всё равно до завтра отложу... Сейчас башка что-то не очень соображает.

0

Попробовал пример от volvo, действительно требуется gmp.dll. После скачивания и переименования dll, пример отработал. Если ТС нельзя использовать внешние библиотеки, то можно хотя бы временно использовать готовую длинную арифметику для реализации алгоритма, а потом уже и самопальную реализовать.

0

ну что ни как? время уже поджимает((((((((((((((((((((((((((((

0

вот исходники из книги

Миниатюры

     

 

0

Задача довольно большая, никак не могу выкроить время на её решение... Боюсь, всё же не успею.

0