Как получить исключительно большие простые числа с помощью кода Python - PullRequest
Новая
       9

Как получить исключительно большие простые числа с помощью кода Python

1 голос
/ 29 марта 2019

Я написал программу для поиска двух больших простых чисел, которые используются в ключе RSA. Это просто вызов КТФ. Проблема, с которой я сталкиваюсь, состоит в том, что число показывается в степени 10, что мне не нужно. Я хочу, чтобы результат был в полной числовой форме (не в десятичной степени, но может быть в десятичной).

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

Код: 

 import math

    n = 456378902858290907415273676326459758501863587455889046415299414290812776158851091008643992243505529957417209835882169153356466939122622249355759661863573516345589069208441886191855002128064647429111920432377907516007825359999


    s=str(math.sqrt(n))
    print (s)
    s=math.ceil(s)
    print(s)

    k=(s*s)-n

    print(k)
    k=math.ceil(k)
    j=math.sqrt(k)
    print(j)

    p= (s-j)
    q= (s+j)
    print("p = " , p)
    print("q = " , q)

    i = p*q

    l = n-i
    print(l)

В этом результате 0 из л. Но p и q, которые мне требуются, в огромных количествах и (2.136302629426752e + 112) в степени 10 формы.

1 Ответ

0 голосов
/ 30 марта 2019

Желаю вам удачи с факторингом.Он составной и не имеет очень маленьких факторов, и при этом он не тривиален с Ферма.Но это не относится к делу.

Установите gmpy2 (например, pip install gmpy2).

Теперь вы можете написать что-то вроде: 

from gmpy2 import mpz, isqrt, is_square
n = mpz('19297732862995346424713322001009')
a = isqrt(n)
while True:
  a += 1
  b2 = a*a - n
  if is_square(b2):
    break
print(n,"=",a-isqrt(b2),"*",a+isqrt(b2))

Что занимает 104-битПример ввода и применяет метод Ферма и находит фактор довольно быстро.Теоретически мы должны сначала добавить тест на простоту, чтобы не вращаться вечно, если дано простое число.

...