Python: требуется решение для высокой точности (генерирует простые числа) - PullRequest
Новая
       41

Python: требуется решение для высокой точности (генерирует простые числа)

0 голосов
/ 04 мая 2018

в данный момент я пытаюсь реализовать функцию generate_random_prime () - из алгоритма, показанного в FIPS186-4 из NIST (Приложение B3.2.1), см. здесь .

Но с шагом 4.4 кажется большой проблемой (если p

, чтобы показать соответствующую часть и проблему моего кода, см. Этот пример: 

import os
from decimal import Decimal
import math

for i in range(100):
    nlen = 2048 #my key-size should be 2048bit
    p = int.from_bytes(os.urandom(int(2048/2/8)), byteorder = "little") #see Ann1 and Ann2

    print(p < Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)

Ann1: 2048/2/8 из-за байтов Ann2: я знаю, что os.urandom не лучший генератор - позже я буду использовать одобренный ... для фазы тестирования это должно быть приемлемо, я думаю ...

Результат всегда "True" - поэтому алгоритм никогда не покинет шаг 4.4.

Я думаю, что проблема Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1), потому что результат этого - Decimal('2.542322012307292741109308792E+308'). Преобразовать в int через int(Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)), результат будет 

254232201230729274110930879200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Округлено! - Это причина всегда истинного результата? Я думаю, что в этом случае никогда не будет возможно получить р меньше Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1)

Как я могу решить эту проблему?

__ редактировать: нашли ошибку: Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2))) - 1) должно быть Decimal(math.sqrt(2))*(Decimal(2**(int(2048/2-1)))), поэтому результат должен быть Decimal('1.271161006153646370554654396E+308') вместо Decimal('2.542322012307292741109308791E+308')

1 Ответ

0 голосов
/ 04 мая 2018

Вы постоянно конвертируете между числами с плавающей точкой, целыми числами и Decimal. Откажитесь от использования float; это включает в себя не использование функций, которые выдают значения float, такие как math.sqrt().

Придерживайтесь Decimal объектов вместо этого, и конвертируйте только окончательное значение в целое число: 

int(Decimal(2).sqrt() * 2 ** ((nlen // 2) - 1))

Обратите внимание на использование //, чтобы использовать целочисленное деление, а не истинное деление (снова производит числа с плавающей запятой).

...