我正在为RSA算法创建所有必要的函数。不幸的是,我似乎不能成为一个合适的卡迈克尔函数。在
以下是我编写的函数:
def gcd(a, b): # Greatest Common Divisor Generator (Euclidean Algorithm)
while b != 0: # While remainder exists
t = b # Initially r[k-1]
b = a % t # Initially r[k] = r[k-2] mod r[k-1] (where r[k-2] is a)
a = t # Predecessor of remainder (b)
return a
def phi(n): # Leonard Euler's Totient Function
y = 0
for k in range(1, n + 1): # Phi(+n) is the number of integers k in the range (1 <= k >= n)...
if gcd(n, k) == 1: # for which gcd(n, k) = 1
y += 1
return y
def carmichael(n): # Robert Daniel Carmichael's Function
y = (phi(n) * 1/2) if (n > 4 and ((n & (n - 1)) == 0)) else phi(n) # phi(n) * 1/2 if 2^x = n, else phi(n) * 1
return y
我用tolient函数来生成数字。据我所知,有一个简单的规则,如果数是2的幂,并且大于4,那么它的质数的量应该减半,否则等于phi(n)。在
上面的规则在我的代码中非常有效,例如,如果输入值为8,则结果如下:
^{pr2}$但问题是,出于某种原因,Carmichael函数也将其他数字减半,例如,如果输入为12,则函数返回的值如下:
phi(12) = 4
carmichael(12) = 4
但它应该是这样的:
phi(12) = 4
carmichael(12) = 2
为什么会这样?或许非质数奇数应该区别对待?有什么我需要添加到我的功能吗?在
谢谢你!在
首先我们创建
gcd
函数来计算2个数的最大公约数,稍后在lambda函数中需要它。在然后我们来看看carmichael函数是如何工作的。在
注意,我们正在寻找
k
,一旦有了n,a
的值就确定了现在我们用默认条件初始化函数
^{pr2}$为了找到所有的a值,我们使用
gcd(a,n)=1
来测试a和n是否有最大的公约数为1,这意味着它们是互质的。如果不是,则为+
如果
gcd(a,n)==1
,我们将这个值存储到a的列表中,然后测试下一个a,直到我们测试所有的a<=n
好的,现在我们有一个列表,回头看定义
首先我们计算a的个数,即列表的长度
timer=len(alist)
然后我们使用
if (a**k)%n==1:
测试这个k是否为列表中的所有值生成
a^k≡1(mod n)
。我们构建一个循环为了测试2中的所有k数,如果它不满足要求,我们做
k=k+1
现在我们有如下的整体功能
相关问题 更多 >
编程相关推荐