数的原根
Primitive root of a number
我已经尝试实现 here 中描述的算法来寻找素数的原根。
它适用于小质数,但是当我尝试大数时,它不再 return 正确答案。
然后我注意到 a^(p-1)/pi
往往是一个大数字,它在 MATLAB 中 returns inf
,所以我认为因式分解 (p-1)
会有所帮助,但我我没看到如何。
我用 MATLAB 写了一小段代码,就在这里。
clear all
clc
%works with prime =23,31,37,etc.
prime=761; %doesn't work for this value
F=factor(prime-1); % the factors of prime-1
for i = 2: prime-1
a=i;
tag =1;
for j= 1 :prime-1
if (isprime(j))
p_i = j;
if(mod(a^((prime-1)/p_i),prime)== 1)
tag=0;
break
else
tag = tag +1;
end
end
end
if (tag > 1 )
a %it should only print the primitive root
break
end
end
欢迎任何意见。
谢谢
Matlab 在这种情况下所做的是在取模之前计算 a^((p-1)/p)。由于 a^((p-1)/p) 很快变得太大而无法处理,Matlab 似乎通过将其转换为浮点数来解决此问题,从而失去一些分辨率并产生取模时的错误结果。
如@rayreng 所述,您可以使用任意精度工具箱来解决此问题。
或者,您可以将取幂分成几个部分,在每个阶段取模。这应该更快,因为它占用的内存更少。您可以将它转储到一个函数中,然后调用它。
% Calculates a^b mod c
i = 0;
result = 1;
while i < b
result = mod(result*a, c);
i = i + 1;
end
我已经尝试实现 here 中描述的算法来寻找素数的原根。
它适用于小质数,但是当我尝试大数时,它不再 return 正确答案。
然后我注意到 a^(p-1)/pi
往往是一个大数字,它在 MATLAB 中 returns inf
,所以我认为因式分解 (p-1)
会有所帮助,但我我没看到如何。
我用 MATLAB 写了一小段代码,就在这里。
clear all
clc
%works with prime =23,31,37,etc.
prime=761; %doesn't work for this value
F=factor(prime-1); % the factors of prime-1
for i = 2: prime-1
a=i;
tag =1;
for j= 1 :prime-1
if (isprime(j))
p_i = j;
if(mod(a^((prime-1)/p_i),prime)== 1)
tag=0;
break
else
tag = tag +1;
end
end
end
if (tag > 1 )
a %it should only print the primitive root
break
end
end
欢迎任何意见。 谢谢
Matlab 在这种情况下所做的是在取模之前计算 a^((p-1)/p)。由于 a^((p-1)/p) 很快变得太大而无法处理,Matlab 似乎通过将其转换为浮点数来解决此问题,从而失去一些分辨率并产生取模时的错误结果。
如@rayreng 所述,您可以使用任意精度工具箱来解决此问题。
或者,您可以将取幂分成几个部分,在每个阶段取模。这应该更快,因为它占用的内存更少。您可以将它转储到一个函数中,然后调用它。
% Calculates a^b mod c
i = 0;
result = 1;
while i < b
result = mod(result*a, c);
i = i + 1;
end