11+ цифр int не работают

Я использую python 3 для небольшого дополнительного кредита, чтобы написать взломщик RSA. Учитель дал нам довольно большой (достаточно большой, чтобы потребовать более 32 бит) int и открытый ключ. Мой код работает для простых чисел <32 бит. Одна из причин, по которой я выбрал python 3, заключается в том, что я слышал, что он может обрабатывать сколь угодно большие целые числа. В терминале python я протестировал это, выполнив небольшие действия, такие как 2 ** 35 и factorial (70). Это работало нормально.

Теперь, когда я написал код, у меня возникли проблемы с ошибками переполнения и т. Д. Почему операции с большими числами кажутся работающими в терминале, но не работают в моем актуальный код? В ошибках указано, что они не могут быть преобразованы в их типы C, поэтому я сначала предполагаю, что по какой-то причине материал в интерпретаторе python не конвертируется в типы C, в то время как кодированный материал. Есть ли способ заставить это работать?

В качестве первой попытки я попытался вычислить список всех простых чисел от 1 до n (большое число). Так работало, пока я не понял, что индексаторы списков [] принимают только целые числа и взрываются, если число больше, чем int. Кроме того, победило создание массива длиной n t работает, если n> 2 ** 32. (не говоря уже о памяти, которую это займет)

Из-за этого я переключился на использование функции, которая, как я обнаружил, может дать очень точное предположение относительно того, является ли число простым или нет. Эти методы вставлены ниже.

Как видите, я выполняю только операции , * , / и%. Похоже, что все это работает в интерпретаторе, но при использовании с этим кодом я получаю ошибки «невозможно преобразовать в c-тип».

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

В последних трех строках появляется сообщение «Невозможно преобразовать в c-тип».

Ниже функция оценивает с очень высокой степенью уверенности, что число является простым. Как упоминалось выше, я использовал это, чтобы избежать создания массивных массивов.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Возможно, мне следует уточнить, вставив ошибку: Я переключился на использование функции, которая, как я обнаружил, может дать очень точное предположение о том, является ли число простым. Эти методы вставлены ниже.

Как видите, я выполняю только операции , * , / и%. Похоже, что все это работает в интерпретаторе, но при использовании с этим кодом я получаю ошибки «невозможно преобразовать в c-тип».

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

В последних трех строках появляется сообщение «Невозможно преобразовать в c-тип».

Ниже функция оценивает с очень высокой степенью уверенности, что число является простым. Как упоминалось выше, я использовал это, чтобы избежать создания массивных массивов.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Возможно, мне следует уточнить, вставив ошибку: Я переключился на использование функции, которая, как я обнаружил, может дать очень точное предположение о том, является ли число простым. Эти методы вставлены ниже.

Как видите, я выполняю только операции , * , / и%. Похоже, что все это работает в интерпретаторе, но при использовании с этим кодом я получаю ошибки «невозможно преобразовать в c-тип».

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

В последних трех строках появляется сообщение «Невозможно преобразовать в c-тип».

Ниже функция оценивает с очень высокой степенью уверенности, что число является простым. Как упоминалось выше, я использовал это, чтобы избежать создания массивных массивов.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Возможно, мне следует уточнить, вставив ошибку: и% операций. Похоже, что все это работает в интерпретаторе, но при использовании с этим кодом я получаю ошибки «невозможно преобразовать в c-тип».

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

В последних трех строках появляется сообщение «Невозможно преобразовать в c-тип».

Ниже функция оценивает с очень высокой степенью уверенности, что число является простым. Как упоминалось выше, я использовал это, чтобы избежать создания массивных массивов.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Возможно, мне следует уточнить, вставив ошибку: и% операций. Похоже, что все это работает в интерпретаторе, но при использовании с этим кодом я получаю ошибки «невозможно преобразовать в c-тип».

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

В последних трех строках появляется сообщение «Невозможно преобразовать в c-тип».

Ниже функция оценивает с очень высокой степенью уверенности, что число является простым. Как упоминалось выше, я использовал это, чтобы избежать создания массивных массивов.

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

Возможно, мне следует уточнить, вставив ошибку: строка 19, в power_mod return (a * power_mod (a, b-1, n))% n OverflowError: Python int слишком велик для преобразования в C double

Это тип ошибки, которую я получаю при выполнении арифметических операций. Ошибки Int возникают при попытке создать невероятно большие списки, наборы и т. Д.