2020-01-14
112
Существуют различные алгоритмы генерации простых чисел. Многие из них вырабатывают числа, обладающие специальными свойствами. Рассмотрим способ генерации, использующий вероятностные алгоритмы проверки чисел на простоту.
Алгоритм 7 Генерация простого числа, [Молдовян Н.А. и др., 2004].
Вход. Разрядность к искомого числа р; параметр t ≥ 1
Выход. Число р, простое с вероятностью не менее 
1. Сгенерировать случайное k-битное число 
2. Положить bk=1, b0=1
3. Проверить, что р не делится на простые числа 3, 5, 7,...,251.
4. Для i = 1,2, ..., t выполнить следующие действия.
4.1. Выбрать случайное число а, 2 < а <р - 2.
4.2. Проверить число р тестом Миллера-Рабина для основания а. Если число р не прошло тест, то p = p+2 и вернуться на шаг 3.
5. Результат: p.
Равенство bk=1 на шаге 2 гарантирует, что длина числа p в точности равна к бит, равенство b0=1 обеспечивает нечетность числа p.
Код функции random (генерация простого числа):
void random(unsigned char c[33]){
unsigned int prost[54]={2,3,5,7,…, 241,251};
unsigned char copy_mod[33]={0};
|
|
|
int w,x,i,k,t,s,f,g=2,r,z,flag=0;
srand(time(0));
for(i=0;i<=31;i++){
mod[i]=rand();
}//генерация простого числа
mod[0]|=1;
mod[31]|=128; //не четное и 256 бит
st[0]=mod[0]-1;
for(k=1;k<=31;k++){
st[k]=mod[k];
}//st= простое-1
for(w=0;;w++){
for(r=0;r<=31;r++){
copy_mod[r]=mod[r];
mod2[r]=mod[r];
}
flag=0;
for(i=0;i<=53;i++){
r=0;
for(k=31;k>=0;k--){
t=mod[k]+(r<<8);
r=t%prost[i];
}//проверка на делимость на маленькие простые числа
if(r==0){//число составное
flag=1;
break;
}
}
if(flag==0){
x=rabin();//проверка на простоту
if(x==1){
for(k=0;k<=6;k++){//еще 7 проверок на простоту
st[0]=mod[0]-1;
for(f=1;f<=31;f++){
st[f]=mod[f];
}
x=rabin();
if(x==0)break;//ели не прошло тест
}
if(x!=0){
x=razlogenie();//если простое
// нахождение первообр. корня
if(x==1)break;//если число разложено
//на простые и найден первообр. корень
}
}
for(r=0;r<=31;r++)mod[r]=copy_mod[r];
}
s=0;
g=2;
for(k=0;k<=31;k++){//прибавить к проверяемому 2
|
|
|
t=mod[k]+g+s;
g=0;
s=t>>8;
mod[k]=t;
if(s==0)break;
}
mod[0]|=1;
mod[31]|=128;
for(k=0;k<=31;k++){st[k]=mod[k];}
st[0]-=1;
}
}
