Правильная функция Кармайкла
Я создаю все необходимые функции для алгоритма 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 функцию для генерации чисел. Насколько мне известно, существует простое правило: если число является степенью 2 и больше 4, количество его простых чисел должно быть уменьшено вдвое, в противном случае оно равно phi(n).
Приведенное выше правило отлично работает в моем коде. Например, если входное значение равно 8, это результаты:
phi(8) = 4
carmichael(8) = 2
Но проблема в том, что функция Кармайкла также почему-то делит пополам другие числа, например, если input равен 12, это то, что возвращают мои функции:
phi(12) = 4
carmichael(12) = 4
Но вот как это должно выглядеть:
phi(12) = 4
carmichael(12) = 2
Почему это происходит? Возможно, не простые нечетные числа должны рассматриваться по-разному? Есть ли что-то, что мне нужно добавить к моей функции?
Спасибо!
0 ответов
Сначала мы создаем 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=[]
Чтобы найти все значения, мы используем gcd(a,n)=1
чтобы проверить, имеют ли a и n наибольший общий делитель, равный 1, что означает, что они взаимно просты.
Если нет, то ++
если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