Для алгоритма шифрования Эль-Гамаля надо найти большие простые числа порядка 2^24-2^32
Написал простую прогу.
Основана на малой теореме Ферма
до числа 80476 она работает отлично, однако, при базе =5, число 80476 выдается как простое. дальше количество простых чисел на одном и том же интервале зависит от значения базы.
Если у Вас есть алгоритмы нахождения таких простых чисел или Вы видите ошибку моей программе напишите пожалуйста.
Мих, Falcon17@pisem.net
Заранее благодарен.
текст
/*******/
#include <stdio.h>
#include <conio.h>
/*
основана на тмалой теореме ферма:
если х**(р-1) % р == 1, то р — простое х=3,5,7
Здесь 2 функции:
powmod
возвр r = (a**b)%p
multrest
return (a*b) %p
*/
unsigned long mulrest(unsigned long a,unsigned long b,unsigned long c)
{
unsigned long A[2], B[2], X[3], x0r, x1r;
A[0] = a>>16; //разбиваем числа a b надвое
A[1] = a — A[0]*65536;//32768;
B[0] = b>>16;
B[1] = b — B[0]*65536;//32768;
X[0] = A[0]*B[0];
X[1] = A[1]*B[0] + A[0]*B[1];
X[2] = A[1]*B[1];
unsigned long int powmod(unsigned long int a,unsigned long int b,unsigned long p)
{
unsigned long int r=1, t[32];
int i=0;
//быстрое возведение в степень
t[0]=a; // заполним массив t числами a, a*a %p, ...
for (i=1;i<32;i++)
t[i]=mulrest(t[i-1],t[i-1],p);
for (i=1;i<32;i++)
if (((b>>(i-1))%2)) // представим b в двоичном коде, где 1
r=mulrest(r,t[i-1],p); //r умножаем на t[i-1]
return r;
}
void main()
{
clrscr();
unsigned long int i=0,q=0,j;
unsigned long int d,e,s,m,base = 3;
d=1; //от какого числа
e=100; //диапазон
for(i=0;i<e;i++)
{
m=base;
s=d++;
m=powmod(m,s-1,s);
if(m==1) {printf("%7lu|%9lu ",++q,s);
if((q+1)%2)printf("\n");}
}
getch();
}
F>Для алгоритма шифрования Эль-Гамаля надо найти большие простые числа порядка 2^24-2^32
F>Написал простую прогу. F>Основана на малой теореме Ферма
F>до числа 80476 она работает отлично, однако, при базе =5, число 80476 выдается как простое. дальше количество простых чисел на одном и том же интервале зависит от значения базы.
F>Если у Вас есть алгоритмы нахождения таких простых чисел или Вы видите ошибку моей программе напишите пожалуйста.
F>Мих, Falcon17@pisem.net
F>Заранее благодарен.
Тест Ферма не гарантирует, что число будет простым.
База является т.н. свидетелем простоты.
Проводится несколько тестов, (с разной базой есс-но )
и каждый новый тест уменьшает вероятность ошибки.
Тест Ферма плох тем, что существуют такие составные числа
(называемые числами Кармишеля) что для любой базы
1 < w < m, равенство
w^(m-1) = 1 (mod m)
выполняется.
Для проверки на простоту принято применять тест Миллера-Рабина.
Каждый тест Миллера-Рабина ГАРАНТИРОВАННО уменьшает вероятность ошибки в 4 раза
И еще.
Разве это большие простые числа 24-32 бита
Сейчас модуль RSA должен быть не менее 1024 бит,
а модуль Эль-Гамаля — не менее 160 бит.
Соответственно, нужны библиотеки работы с большими числами
(если конечно задача не лабораторная работа, а должна иметь практическую ценность .
Рекомендую найти готовую библиотеку:
в таких библиотеках обычно уже есть проверка на простоту, генерация ключей и пр.
ROP>(называемые числами Кармишеля) Обычно в русской транскрипции их называют числами Кармайкла.
ROP>1 < w < m, равенство ROP>w^(m-1) = 1 (mod m) ROP>выполняется.
Это определение неверно, например ему не удовлетворяет
первое число Кармайкла 561 для основания 3. Более того, легко показать, что
такому определению удовлетворяют простые и только они.
Правильно сказать, что сравнение выполнено для всех обратимых вычетов mod m, т.е. для w
взаимно простых с m.
Здравствуйте, Max2, Вы писали:
ROP>>(называемые числами Кармишеля) M> Обычно в русской транскрипции их называют числами Кармайкла.
Про Кармишеля я у Саломаа вычитал
А еще в гугле попадается "Кармихаэля"
ROP>>1 < w < m, равенство ROP>>w^(m-1) = 1 (mod m) ROP>>выполняется.
M>Это определение неверно, например ему не удовлетворяет M>первое число Кармайкла 561 для основания 3. Более того, легко показать, что M>такому определению удовлетворяют простые и только они.
M>Правильно сказать, что сравнение выполнено для всех обратимых вычетов mod m, т.е. для w M>взаимно простых с m.
Ну да. Это я упустил.
Писал по памяти.
Сейчас вот сверился с первоисточником...
Эти числа Кармайкла еще, ко всему прочему, должны быть нечетными
Re[4]: Простые числа
От:
Аноним
Дата:
10.12.02 14:10
Оценка:
ROP>Эти числа Кармайкла еще, ко всему прочему, должны быть нечетными
Да, конечно! А еще, ко всему прочему, они свободны от квадратов и в их
разложениях на простые должно быть как минимум 3 различных простых... и.т.д
Эти числа довольно редки, хотя их и бесконечно много.
)
