Приведите плиз алгортм определения простоты числа.
Но не перебором, а с использованием вероятностных методов, теорем и т.п.
Или киньтесь ссылкой.
Что-то меня эта тема заинтересовала
Здравствуйте flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала
а ты уверен что такие теоремы есть?
По-моему кроме как перебором это никак не решается и вероятности тут не помогут...
Здравствуйте Курилка, Вы писали:
К>По-моему кроме как перебором это никак не решается и вероятности тут не помогут...
Вероятности помогут вот в каком смысле:
Предположим, существует тест, который определяет, что с вероятностью < 1/2 число является составным. Если каждый из k таких независимых тестов скажет, что число составное с вероятностью < 1/2, то значит мы можем утверждать, что число составное с вероятностью < (1/2)^k. При достаточно больших k (на практике хватит ~50) мы можем утверждать в этом случае, что число простое (вероятность, что мы назовем простое число составным, как видно, очень мала).
А вот пара таких тестов (проверяем на простоту число p):
I) Тест Леманна
1) Выбираем случайно число a, меньшее p
2) Вычисляем r=a^((p-1)/2) mod p
3) Если r!=1 && r!=-1 (mod p), то p не является простым.
4) Если r==1 || r==-1 (mod p), то вероятность того, что p не является простым <= 1/2
Повторяем такие проверки k раз. Если результат равен 1 или -1, но не всегда равен 1, то p наверняка простое число (с вероятностью ошибки 1/(2^k)).
II) Очень распространенный тест Рабина-Миллера
Вычислим b — число делений p-1 на 2 (т.е. 2^b — это наибольшая степень числа 2, на которое делится p-1). Затем вычислим m, такое что p=1+(2^b)*m (т.е. m — остаток от деления p-1 на 2^b).
1) Выберем случайное число a, меньшее p.
2) j=0; z=(a*m) mod p
3) Если z==1 или если z==p-1, то p проходит проверку и может быть простым числом.
4) Если j>0 и z==1, то p не является простым числом.
5) j=j+1. Если j<b и z<p-1, устанавливаем z=(z*z) mod p и возвращаемся на шаг 4). Еслм z==p-1, то p проходит проверку и может быть простым числом.
6) Если j==b и z!=p-1, то, p не является простым числом.
В этом тесте вероятность прохождения проверки на простоту составным числом убывает быстрее, чем в предыдущем. Вероятность того, что мы назовем составное число простым после k таких тестов не больше (1/4)^k.
Здравствуйте Курилка, Вы писали:
К>Здравствуйте flyker, Вы писали:
F>>Приведите плиз алгортм определения простоты числа. F>>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>>Или киньтесь ссылкой. F>>Что-то меня эта тема заинтересовала
К>а ты уверен что такие теоремы есть? К>По-моему кроме как перебором это никак не решается и вероятности тут не помогут...
Здравствуйте vladsm, Вы писали:
V>Здравствуйте Курилка, Вы писали:
К>>По-моему кроме как перебором это никак не решается и вероятности тут не помогут...
V>Вероятности помогут вот в каком смысле: V>Предположим, существует тест, который определяет, что с вероятностью < 1/2 число является составным. Если каждый из k таких независимых тестов скажет, что число составное с вероятностью < 1/2, то значит мы можем утверждать, что число составное с вероятностью < (1/2)^k. При достаточно больших k (на практике хватит ~50) мы можем утверждать в этом случае, что число простое (вероятность, что мы назовем простое число составным, как видно, очень мала).
V>А вот пара таких тестов (проверяем на простоту число p):
V>I) Тест Леманна
V> 1) Выбираем случайно число a, меньшее p V> 2) Вычисляем r=a^((p-1)/2) mod p V> 3) Если r!=1 && r!=-1 (mod p), то p не является простым. V> 4) Если r==1 || r==-1 (mod p), то вероятность того, что p не является простым <= 1/2
Мне кажется этот тест очень трудоемкий в смысле вычисления r=a^((p-1)/2)
V> Повторяем такие проверки k раз. Если результат равен 1 или -1, но не всегда равен 1, то p наверняка простое число (с вероятностью ошибки 1/(2^k)).
V>II) Очень распространенный тест Рабина-Миллера
V> Вычислим b — число делений p-1 на 2 (т.е. 2^b — это наибольшая степень числа 2, на которое делится p-1). Затем вычислим m, такое что p=1+(2^b)*m (т.е. m — остаток от деления p-1 на 2^b).
V> 1) Выберем случайное число a, меньшее p. V> 2) j=0; z=(a*m) mod p V> 3) Если z==1 или если z==p-1, то p проходит проверку и может быть простым числом. V> 4) Если j>0 и z==1, то p не является простым числом. V> 5) j=j+1. Если j<b и z<p-1, устанавливаем z=(z*z) mod p и возвращаемся на шаг 4). Еслм z==p-1, то p проходит проверку и может быть простым числом. V> 6) Если j==b и z!=p-1, то, p не является простым числом.
V> В этом тесте вероятность прохождения проверки на простоту составным числом убывает быстрее, чем в предыдущем. Вероятность того, что мы назовем составное число простым после k таких тестов не больше (1/4)^k.
А вот это уже получше Спасибо.
А у тебя нет алгоритма Адлемана — Ленстры ?
Здравствуйте muh, Вы писали:
muh>Здравствуйте vladsm, Вы писали:
V>>I) Тест Леманна
V>>II) Очень распространенный тест Рабина-Миллера
muh>+ еще вариант с построением дерева Кэли %)
Кстати кому интересно я тут еще один способ нарыл
#include <stdio.h>
#include <conio.h>
#include <math.h>
unsigned long n; /* нечетное число, проверяемое на простоту */
/* SPP - функция, равная 1, если */
/* n - сильно псевдопростое число по основанию b */
/* и 0, в противном случае */
int SPP(int b) {
register int k,i;
static unsigned long q;
/* p и x - переменные для точного (64 двоичных разряда) */
/* выполнения промежуточных умножений по mod n */
static double long p,x;
/* вычисление k и нечетного q таких, что n-1=q*2^k */
for(q=n-1,k=0;q%2==0;q>>=1,k++);
/* вычисление p=mod(b^q,n); */
for(x=b,p=q%2?x:1,q>>=1;q>0;q>>=1) {
x=fmodl(x*x,n);
if(q%2) p=fmodl(p*x,n);
}
if(p==1||p==n-1) return 1;
/* поиск i, для которого mod(q*2^i.n)=n-1 */
for(i=1;i<k;i++) if((p=fmodl(p*p,n))==n-1) return 1;
return 0;
}
/*--------------------------------------------------------------------------*/
int main(void) {
FILE *out;
static char *name="rez1.txt"; /* имя файла с результатом */
static unsigned long B,E; /* вводимый диапазон поиска */
static unsigned long NB,NE; /* приведенный диапазон поиска */
static unsigned long k; /* количество простых чисел */
static short p[4]={2,3,5,7},i; /* первые четыре простых числа */
clrscr();
printf("Команда 054. Задача 1.\n");
printf("Простые числа в диапазоне от NB до NE\n");
printf("1<=NB<=NE<=4294967295\n");
/* ввод и приведение начала диапазона к нечетному числу */
printf("NB="); scanf("%lu",&B);
if(B<1) {fprintf(stderr,"*** ошибка NB=%lu\n",B); return 1;}
NB=B; if(B%2==0) NB++;
/* ввод и приведение конца диапазона к нечетному числу */
printf("NE="); scanf("%lu",&E);
if(E<B) {fprintf(stderr,"*** ошибка NE=%lu\n",E); return 1;}
NE=E; if(E%2==0) NE--;
out=fopen(name, "wt");
/* проверка принадлежности введенному диапазону */
/* первых четырех простых чисел */
for(k=0,i=0;i<4;i++) if((B<=p[i])&&(p[i]<=E)) {
k++; fprintf(out," %u",p[i]);
}
/* поиск оставшихся простых чисел в приведенном диапазоне */
n=7; if(NB>9) n=NB-2;
while(n<NE) {
n+=2;
if(SPP(2)&&SPP(3)&&SPP(5)&&SPP(7)&&n!=3215031751L) {
k++; fprintf(out," %lu",n);
}
}
fclose(out);
printf("Количество простых чисел = %lu\n",k);
printf("Результат работы программы записаны в файл %s\n",name);
return 0;
}
F>Мне кажется этот тест очень трудоемкий в смысле вычисления r=a^((p-1)/2)
Нет, это не так. Есть стандартная простая процедура вычисления r=n^m (все вычисления по модулю):
Раскладываем m в двоичном виде: b_(k-1) ... b_0. Наша цель посчитать
r=n^( 2^b_(k-1)+...2^b_0 )=n^(2^b_(k-1))*...*n^(2^b_0). Для этого достаточно вычислить каждый сомножитель, а это делается очень быстро. В общем виде не удобно писать, поэтому приведу пример.
Считаем n^45.
n^45=n^(b101101)=n^(32+8+4+1)=n^32*n^8*n^4*n^1
Теперь посчитаем все сомножители. Делать это будем так:
1) n^1=n
2) n^2=n^1*n^1
3) n^4=n^2*n^2
4) n^8=n^4*n^4
5) n^16=n^8*n^8
6) n^32=n^16*n^16
Заметим, что нам понадобилось всего 6 умножений. А в общем виде log2(m). Теперь выбираем нужные степени и перемножаем. Вот такая быстрая процедура. Ее трудоемкость порядка log2(m) по числу умножений.
F>А у тебя нет алгоритма Адлемана — Ленстры ?
Здравствуйте vladsm, Вы писали:
V>Здравствуйте flyker, Вы писали:
F>>Мне кажется этот тест очень трудоемкий в смысле вычисления r=a^((p-1)/2)
V>Нет, это не так. Есть стандартная простая процедура вычисления r=n^m (все вычисления по модулю):
Господа, берите любой стандартный учебник по криптографии и и смотрите алгоритмы различных числовых решет. Алгоритм Адлемана — Ленстры есть, скорее всего, в реализации SSL. Если нет, то чтение (хотя бы) его исходников все равно очень сильно поможет
МВС
Люди слышат только те вопросы, на которые они в состоянии найти ответ. (с)
Re: Опять простые числа :)
От:
Аноним
Дата:
18.04.02 10:03
Оценка:
Здравствуйте flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала :)
HI flyker,
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала :)
Я на днях полночи по нету лазил — наваждение было наверное — простые числа заразны:)
Здравствуйте!
V>II) Очень распространенный тест Рабина-Миллера
V> Вычислим b — число делений p-1 на 2 (т.е. 2^b — это наибольшая степень числа 2, на которое делится p-1). Затем вычислим m, такое что p=1+(2^b)*m (т.е. m — остаток от деления p-1 на 2^b).
V> 1) Выберем случайное число a, меньшее p. V> 2) j=0; z=(a*m) mod p V> 3) Если z==1 или если z==p-1, то p проходит проверку и может быть простым числом. V> 4) Если j>0 и z==1, то p не является простым числом. V> 5) j=j+1. Если j<b и z<p-1, устанавливаем z=(z*z) mod p и возвращаемся на шаг 4). Еслм z==p-1, то p проходит проверку и может быть простым числом. V> 6) Если j==b и z!=p-1, то, p не является простым числом.
А кто-нибудь пробовал реализовать этот алгоритм? У меня получается, что ни одно число не проходит проверку. Возможно, я неправильно понял этот алгоритм, но другого (понятного для меня) описания теста Р-М я не встречал...
Здравствуйте, flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала
Покопайся еще на cryptography.ru, там даже полиномиальный тест выложен. Но на практике лучше использовать тест Рабина-Миллера, а если хочется уверенности, то Коэна-Ленстры.
Здравствуйте, flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала
private int GetPrime(int minSize) {
if (minSize < 0)
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
for (int i = 0; i < primes.Length; i++) {
int size = primes[i];
if (size >= minSize) return size;
}
//outside of our predefined table.
//compute the hard way.
for (int j = ((minSize — 2) | 1);j < Int32.MaxValue;j+=2) {
if (Primep (j))
return j;
}
return minSize;
}
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, sergey222, Вы писали:
S>Здравствуйте!
V>>II) Очень распространенный тест Рабина-Миллера
S>А кто-нибудь пробовал реализовать этот алгоритм? У меня получается, что ни одно число не проходит проверку. Возможно, я неправильно понял этот алгоритм, но другого (понятного для меня) описания теста Р-М я не встречал...
S>Спасибо.
Если поможет, то могу дать несколько другое описание.
Пусть p — число, которое проверяем, a — некоторое фиксированное целое число, взаимнопростое с p.
Пусть p==(2^k)*q, где q — нечетное.
Находим t = a^q.
Если t==1 или t==-1, значит есть вероятность, что число простое, но больше ничего сказать не можем, выход.
Для всех i от 1 до k повторяем
{
t = t*t;
Если t==-1, то опять есть вероятность, что число простое, выход.
Если t==1, значит число составное, при желании даже можно указать делители.
(Действительно, имеем t*t-1==0, (t-1)(t+1)==0 — один из них делитель нуля).
}
Если в конце t!=1, то число составное.
Этот тест повторяется для нескольких a, вероятность того, что число составное, если оно прошло s тестов равна 1/(4^s).
Здравствуйте, flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п. F>Или киньтесь ссылкой. F>Что-то меня эта тема заинтересовала
Есть один метод, например, сравнивая, с предварительно созданным множеством. Принцип создания множества: заполняем его до необхожимого нам предела (если не жаль машину то лучше всего до предела используемого формата числа) и исключяем все кратные ему из этого множества. Для определения простоты чаисла достаточно воспользоваться встроенной функцией.
P.S. Метод легко реализуем на PASCAL'е его листинг, если я не ошибаюсь, можно найти в учебнике по TURBO PASCAL'ю С.А.Немнюгина, ИД питерпресс.
Re: Опять простые числа :)
От:
Аноним
Дата:
12.06.05 21:13
Оценка:
Здравствуйте, flyker, Вы писали:
F>Приведите плиз алгортм определения простоты числа. F>Но не перебором, а с использованием вероятностных методов, теорем и т.п.
Кстати, прошлым летом группа индусов доказала полиномиальность задачи определения простоты числа и привела полиномиальный и точный(в противовес вероятностному) алгоритм решения задачи. Точно не помню, где видел статью, можно поискать здесь http://citeseer.ist.psu.edu/
Re[2]: Вот с этого и следовало начинать! :)))
От:
Аноним
Дата:
14.06.05 04:01
Оценка:
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, flyker, Вы писали:
F>>Приведите плиз алгортм определения простоты числа. F>>Но не перебором, а с использованием вероятностных методов, теорем и т.п.
А>Кстати, прошлым летом группа индусов доказала полиномиальность задачи определения простоты числа и привела полиномиальный и точный(в противовес вероятностному) алгоритм решения задачи. Точно не помню, где видел статью, можно поискать здесь http://citeseer.ist.psu.edu/
Их зовут: M.Agrawal, N.Kayal, N.Saxena (это вам в качестве ключа для поиска статьи).
Приведу суть их алгоритма (выяснения простоты натурального числа n>2; здесь a^b означает "a в степени b"; sqrt — квадратный корень, log — логарифм по основанию 2).
1. Если n=x^y для некоторых x,y>1, выдать отрицательный ответ.
2. Положить p=2.
3. Если числа p и n не взаимно просты (проверка вычислением НОД), выдать отрицательный ответ.
4. Если число p не простое (здесь — проверка тупейшим алгоритмом), перейти к шагу 7.
5. Определить наибольший простой делитель q числа p-1 (тупейшим алгоритмом).
6. Если q>=4sqrt(p)log(n) и (n^((p-1)/q))mod(p)!=1, перейти к шагу 8.
7. Учеличить p на 1; если p<n, перейти к шагу 3.
8. Если для некоторого целого k, 1<=k<=2sqrt(p)log(n), выполнено ((x-k)^n!=(x^n-k))(mod(x^p-1,n), выдать отрицательный ответ.
9. Выдать положительный ответ.
