Правильная функция Кармайкла

Я создаю все необходимые функции для алгоритма 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

Я использую функцию totient для генерации чисел. Насколько мне известно, существует простое правило: если число является степенью двойки и больше 4, количество его простых чисел должно быть уменьшено вдвое, иначе оно равно фи (n).

Приведенное выше правило отлично работает в моем коде. Например, если входное значение равно 8, это результаты:

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

Но проблема в том, что функция Кармайкла по какой-то причине также делит пополам другие числа, например, если вход равен 12, вот что возвращают мои функции:

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

Но вот как это должно выглядеть:

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

Почему это происходит? Возможно, к непростым нечетным числам следует относиться по-другому? Есть ли что-то, что мне нужно добавить к моей функции?

Благодарю вас!


python abstract-algebra
person ShellRox    schedule 11.12.2017    source источник
comment
Существует codegolf ответ с реализацией функции Python Carmichael и подробным объяснением, которое может оказаться полезным .   -  person import random    schedule 12.12.2017
comment
Поскольку заявленная связь с тотиентом Эйлера существует только для степеней или удвоенной степени нечетного простого числа и степеней двойки< /а>? Кроме того, не проще ли вычислить тотиент Эйлера с n (1-1/p1)(1-1/p2)...(1-1/pm)   -  person Mr. T    schedule 12.12.2017
comment
@Piinthesky Спасибо! Формула произведения Эйлера кажется проще, но я думаю, что правило gcd быстрее.   -  person ShellRox    schedule 12.12.2017
comment
@ Эрик Обязательно посмотрю, спасибо!   -  person ShellRox    schedule 12.12.2017
comment
@ShellRox Зависит. Для одного числа подход gcd, вероятно, быстрее. Для повторяющихся вызовов, вероятно, быстрее создать список простых чисел - составные числа обычно довольно быстро ломаются. Существуют генераторы prime sieve написанный на C, который, вероятно, в любой момент опережает сценарий Python.   -  person Mr. T    schedule 12.12.2017
comment
@Piinthesky Большое спасибо! Обязательно попробую оба способа!   -  person ShellRox    schedule 12.12.2017

Ответы (1)


arrow_upward
1
arrow_downward

Сначала мы создаем функцию gcd для вычисления наибольшего общего делителя двух чисел, она понадобится нам позже в лямбда-функции.

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

Затем мы посмотрим, как работает функция Кармайкла.

Пусть n — целое положительное число. Тогда λ(n) определяется как наименьшее натуральное число k такое, что
a^k≡1(mod n)
для всех a такой, что gcd(a,n)=1.

Обратите внимание, что мы ищем k, значения a определяются, когда у нас есть n.

Теперь мы инициализируем функцию с условием по умолчанию

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

Чтобы найти все значения a, мы используем gcd(a,n)=1, чтобы проверить, имеют ли a и n наибольший общий делитель, равный 1, что означает, что они взаимно просты.
Если нет, то a++< br> если 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

Хорошо, теперь у нас есть все в списке, вернемся к определению

наименьшее натуральное число k такое, что
a^k≡1(mod n)

Сначала мы подсчитываем число a, которое является длиной списка
timer=len(alist)
Затем мы используем
if (a**k)%n==1:
, чтобы проверить, составляет ли это k a^k≡1(mod n) для всех значений в списке. Мы строим петлю

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

для проверки всех k номеров из 2, если это не соответствует требованию, мы делаем 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
person user9073637    schedule 27.07.2019
comment
Извините, если это немного поздно, но я должен сказать, что, хотя ваше решение хорошее, ваш код полностью непитоновский. - person Gderu; 28.02.2020
comment
Вместо этого я бы написал функцию так: def carmichael(n): coprimes = [] for i in range(n): if gcd(i, n) == 1: coprimes.append(i) k = 0 while True: for coprime in coprimes: if (coprime ** k) % n != 1: break else: return k k += 1 - person Gderu; 28.02.2020