4

我正在为 RSA 算法创建所有必要的函数。不幸的是，我似乎无法做出正确的 Carmichael 功能。

这些是我编写的函数：

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

我正在使用 totient 函数进行数字生成。据我所知，有一个简单的规则，如果数字是 2 的幂并且大于 4，则其质数的数量应减半，否则等于 phi(n)。

上面的规则在我的代码中完美运行，例如，如果输入值为 8，则结果如下：

phi(8) = 4
carmichael(8) = 2

但问题是，Carmichael 函数也出于某种原因将其他数字减半，例如，如果输入是 12，这就是我的函数返回的内容：

phi(12) = 4
carmichael(12) = 4

但它应该是这样的：

phi(12) = 4
carmichael(12) = 2

为什么会这样？也许非质数奇数应该被区别对待？有什么我需要添加到我的函数中的吗？

谢谢！

4

1 回答 1

1

首先，我们创建gcd计算 2 个数字的最大公约数的函数，稍后我们将在 lambda 函数中使用它。

 def gcd(a,b):
        while (a>0):
            b=b%a
            (a,b)=(b,a)
        return b

然后我们看看 carmichael 函数是如何工作的。

令n为正整数。然后 λ(n) 被定义为最小正整数k使得
a^k≡1( mod n)
对于所有a使得gcd(a,n)=1。

请注意，我们正在寻找，一旦我们有了 n k，就确定了 的值。a

现在我们用默认条件初始化函数

n=int(n)
k=2
a=1
alist=[]

为了找到所有 a 值，我们gcd(a,n)=1用来测试a和n的最大公约数是否为 1，这意味着它们是互质的。
如果不是，a++
if gcd(a,n)==1，我们将此值存储到 a 的列表中并测试下一个 a 直到我们测试所有a<=n

        while not ((gcd(a,n))==1):
            a=a+1

        while ((gcd(a,n))==1) & (a<=n) :
            alist.append(a)
            a=a+1
            while not ((gcd(a,n))==1):
                a=a+1

好的，现在我们在列表 alist 中有一个，回头看看定义

最小的正整数 k 使得
a^k≡1(mod n)

首先我们统计 a 的个数，也就是 alist 的长度，
timer=len(alist)
然后我们用
if (a**k)%n==1:
这个来测试这个 k 是否a^k≡1(mod n)为 alist 中的所有值。我们构建一个循环

for a in alist:
      if (a**k)%n==1:
           timer=timer-1
              if timer <0:
                  break
              pass
      else:
           timer=len(alist)
           k=k+1

测试 2 中的所有 k 数，如果不符合要求，我们执行k=k+1

现在我们有如下的整个功能

    def carmichael(n):
        n=int(n)
        k=2
        a=1
        alist=[]

        while not ((gcd(a,n))==1):
            a=a+1

        while ((gcd(a,n))==1) & (a<=n) :
            alist.append(a)
            a=a+1
            while not ((gcd(a,n))==1):
                a=a+1

        timer=len(alist)
        while timer>=0:
            for a in alist:
                if (a**k)%n==1:
                    timer=timer-1
                    if timer <0:
                        break
                    pass
                else:
                    timer=len(alist)
                    k=k+1
        return k
于 2019-07-27T04:06:34.513 回答