2020-01-14
144
В ходе реализации понадобилось разложить большое число на простые множители один из которых является большим.
Алгоритм 8 Разложение числа на простые множители, [Молдовян Н.А. и др., 2004].
Вход. Раскладываемое число n.
Выход. Число не раскладывается на простые множители (с большим простым множителем); число раскладывается на q1 , q2 ,…, qk - различных простых делителя.
1. Создание ряда простых чисел p1=2,p2= 3,…, p844= 6491;
2. Положить t = 0.
3. Для i = 1,2, ..., 844выполнить следующие действия.
3.1. Если w=n/pi целое, t = t + 1, qt = pi;
3.1. Пока w=n/pi целое, n=n/pi.
4. Проверить число n тестом Миллера-Рабина.
Код функции разложение razlogenie()
int razlogenie(){
int i,r,k,t,x,w,fl=0,counter=0;;
unsigned char p[33]={0};
int mass[300]={0};
unsigned char c[33]={0};
unsigned int prost[6900]={2,3,5,7,…,69491,69493};
for(k=0;k<=32;k++) p[k]=mod[k];
p[0]-=1;
for(i=0;i<=6860;i++){
r=0;
for(k=31;k>=0;k--){
t=p[k]+(r<<8);
c[k]=t/prost[i];
r=t%prost[i];
}
for(k=0;k<=31;k++) p[k]=c[k];
if(r==0){
for(k=0;k<=31;k++) mod[k]=p[k];
if(fl!=i){
|
|
|
fl=i;
mass[counter]=prost[i];
counter++;
}
i--;
}
if(r!=0){
for(k=0;k<=31;k++) p[k]=mod[k];
}
}
x=rabin();
if(x==1){
pervoobr(mass);//вычисление первообразного корня
}
return x;
}
Нахождение первообразного корня.
Утверждение
Пусть q1 , q2 ,…, qk - различные простые делители функции Эйлера 
от числа п. Для того чтобы число g, взаимно простое с п, было первообразным корнем по модулю п, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений:
, 
,…, 
.
Алгоритм 9 Нахождение первообразного корня, [Молдовян Н.А. и др., 2004].
Вход. Простое число n, q1 , q2 ,…, qk - различные простые делители функции Эйлера 
Выход. Первообразный корень g.
1. Генерация числа 1 < g < n.
2. Для i = 1,2, ..., kвыполнить следующие действия.
2.1. Если 
перейти к шагу 1.
3. Число g первообразный корень по модулю n.
Код функции pervoobr (нахождение первообразного корня):
void pervoobr(int mass[300]){
unsigned char g[33]={0};
unsigned char c[33]={0};
unsigned char b[33]={0};
int i,k,t,x,flag;
srand(time(0));
for(i=0;i<=31;i++){
g[i]=mod[i];
mod[i]=mod2[i];
osn[i]=0;
}
for(k=0;k<=1000;k++){
flag=2;
for(i=0;i<=28;i++) osn[i]=rand();
del(mod,g,st);
step(c);
x=rav(c);
if(x!=0){
flag=1;
for(i=0;i<=31;i++){
c[i]=0;
for(i=0;i<=300;i++){
if(mass[i]!=0){
c[0]=mass[i];
c[1]=(mass[i]>>8);
del(mod,c,b);
|
|
|
for(t=0;t<=31;t++)st[t]=b[t];
step(b);
x=rav(b);
if(x==0) flag=0;
}
}
}
}
if(flag==1){
break;
}
}
}
Глава 3. Оценка алгоритма.
