Нужно построить алгоритм на С++ проверки простоты числа ( interger ) по Rabin M. ,на основе работы его "Probabilisctic algorithms for testing primality" Journal of Number Theory 12, 1980,p.128-138 . если у кого материалл данный, или ссылка. я вроде нашел в рунете, как всё это делается,но запутлся. Что делать когда a^(n-1) выходит за границу размера int?
Меня умиляют люди, которые не читают Кнута... А вот тебе и код готовый, на С, правда: http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=6802 А вообще, алгоритмических реализаций этого добра в сети как ... гм...
Да ..до Кнута я еще не дошел. И что? http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=6802 - читал , до того как запостил. Я первый раз в эти, для меня еще пока, дебри шагнул. Поэтому делаю сам. А если пользоваться Вашим Владимир кодом , то у меня вопросы..) ТО гда уж сразу вопрос по коду: Код (Text): * Donald Knuth, vol 2., algorithm 4.5.4P - probability test for prime*/ static bool isprime(unsigned n) { srand(time(0)); -------------------- /* у меня Visual C++ 6.0 пишет, что неверный индентификатор. srand в iostream заголовочном файле?*/ ------------------- unsigned x = rand() % (n - 1); ----------------------- /*эту строчку не понял*/ ------------------------ unsigned k, q; do_N(n, k, q); -------------------- /*не нашел реализации кода для do_N * , как я понял это нахождения ввида n-1=(2^k)*q */ -------------------- unsigned j = 0; unsigned y = powmod(x, q, n); ------------------ /* что делает powmod, те как выглядит алгебраическая запись?*/ ----------------- while(j < k) { if(((!j) && (y == 1)) || (y == n - 1)) return true; if((j > 0) && (y == 1)) return false; j++; y = (y*y)%n; -------------- /* Тут наверно пойму как только с powmod разберусь))) */ -------------- } return false; }
Мда... Тяжелый случай... /* у меня Visual C++ 6.0 пишет, что неверный индентификатор. srand в iostream заголовочном файле?*/ Эххх... Ты CRT когда-нибудь пользовался? Как инитить их долбаный PRNG знаешь? Что такое rand/srand, слышал? Гуглим. /*эту строчку не понял*/ Тогда, может, рано тебе еще в это лезть, а? unsigned x = rand() % (n - 1); означает, что x будет лежать в диапазоне 0 < x < n - 1. Операция %(n-1) гарантирует это. /*не нашел реализации кода для do_N * , как я понял это нахождения ввида n-1=(2^k)*q */ Нда... Как же ты читал-то? Еще раз, для особо одаренных, из того же топика! 2) вероятностный тест Миллера-Рабина на простоту числа - взят из Кнута и дополнительно требует: 2.1) быстрое возведение в степень 2.2) представление числа в форме n - 1 = 2kq: http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=6841 /* что делает powmod, те как выглядит алгебраическая запись?*/ Я офигеваю. КАК ТЫ ЧИТАЕШЬ ВООБЩЕ?
А вообще, я подумал, что зря на тебя ору. Вот тебе отрывок из моей с Relf'ом книги: Часто необходимо знать ответ на вопрос – а является ли данное число простым? Это возможно установить и без разложения числа на множители за очень и очень приемлимое время. Известно два вида тестов числа на простоту: 1) Вероятностые (ответ получаем в виде утверждений: “вероятно, n простое” или “вероятно, n составное”) 2) Детерминистические (ответ получае в виде “n – простое” или “n – составное”) Существует достаточно много тестов и первого, и второго рода. Казалось бы, откуда возникнуть проблеме? Очевидно, что малая теорема Ферма замечательно походит для теста числа на простоту! Ну, пусть n – число, которое необходимо проверить. Теорема гласит, что, если n – простое, то a^n === a (mod n). Тогда, казалось бы, все просто. Возьмем парочку разных a для пущей надежности, возведем их в степень по модулю и поглядим, а выполняется ли равенство? Умножений уйдет немного... Однако, вот беда, существуют специальные числа, для которых малая теорема Ферма выполняется, однако сами числа простыми не являются! Мы говорим о числах Кармайкла (Carmichael) [xxx]. Попробуйте, к примеру, число 561.
Так вот, малая теорема ферма не может детектить такие числа. Однако ее модифицированная версия - может вполне. Итак, теорема: n - нечетное простое число (выводит из рассмотрения двойку) и n - 1 = 2^s*t, где t - нечетное. Если а не делится на n, то 1) или a^t === 1(mod n); 2) или a^((2^i)*t) === -1 (mod n), 0 <= i <= s - 1 Так что тот код выше, всего лишь, доказывает выполнение или невыполнение условий этой теоремы. Теперь, думаю, должно быть более понятно...
ОГРОМНОЕ спасибо. Фермыча понял, и модернизацию его. и числа кармайкла. и с вероятностью понятно. Твой код ясен теперь. У меня проблема со своей реализацией на С++. (((( у меня проблемы с возведением в степень. Так ли я понял, что придется пользоваться bignum?( ps мне просто небольшую программу надо по вероятностному алгоритму нахождения просты числа.(
У меня проблема со своей реализацией на С++. (((( у меня проблемы с возведением в степень. Эххх.. На, еще отрывок из моей же книги держи... *** Вкратце рассмотрим теперь один из разделов модулярной арифметики – возведение в степень по модулю (exponentiation). Положим, нам надо вычислить нечто вида 73^17 mod 8881. Ясно, что конечный результат не превысит 8881, а вот как быть с промежуточными значениями? Подходя к проблеме с наивной точки зрения, можно просто умножить 73 само на себя 17 раз и поделить результирующее число на 8881, взяв, при этом, остаток от деления. Легко видеть, что если числа будут велики, вполне возможно, не хватит и 2-3 гигабайт виртуальной памяти, что нам любезно предоставляет Windows. Поэтому необходимы какие-то алгоритмы, способные выполнять подобные операции без громадных промежуточных результатов. В данном разделе мы рассмотрим только бинарный алгоритм возведения в степень. Идея метода достаточно проста. Итак, нам необходимо решить задачу вида x^n mod m, где n – положительное целое число, x,m принадлежат Z. Представим n в двоичной форме счисления. В нашем примерчике это выглядит так: (17)<sub>10</sub> = (10001)<sub>2</sub> Теперь распишем последовательность нулей и единиц согласно следующему правилу: каждую единицу заменяем на пару символов “SX”, каждый 0 – на символ “S”. 10001 -> SXSSSSX Теперь избавляемся от самой первой левой пары SX. Вот так: SXSSSSX -> SSSSX Теперь мы имеем ряд директив, указывающих нам, как возводить x в степень n. Каждый “S” мы трактуем как директиву “возвести x в квадрат”, каждый “X” как “умножить текущее значение x на изначальное значение x”. На каждом шаге алгоритма мы вычисляем операцию взятия остатка. В нашем примере это выглядит так: S: 732 (mod 8881) = 5329 S: 53292 (mod 8881) = 5684 S: 56842 (mod 8881) = 7659 S: 76592 (mod 8881) = 1276 X: 1276*73 (mod 8881) = 4338
Так ли я понял, что придется пользоваться bignum?( Все зависит от того, какие у тебя числа. Если они выходят за пределы int - то тут ты ничего поделать не можешь. Тебе ПРИДЕТСЯ сделать реализацию арифметики многократной точности либо самому, либо заюзать какую-нибудь либу типа GMP или MIRACL.
volodya А книжка на русском будет? (и когда, если не секрет) А то я недавно обнаружил, что метематику толи забыл, толи не знал (((
Книжка будет на русском. Книжка будет свободно доступной и бесплатной. Формат - PDF. Будет алгоритмическая иллюстрация и исходный код.
