Генерация длинных простых чисел в Python

Question

Хорошо, так что в основном у меня возникла эта проблема, и я искал ее в Интернете, и переполнение стека. В новом обновлении Python 3.0 нет кода, который делает это при переполнении стека и многих других сайтах, так что, как и в моем первом посте, я хочувнести свой вклад в стекопотоки, потому что я наконец-то нашел решение

, поэтому сначала вы хотите

import random
from math import floor
from math import sqrt

Это важно, потому что вы увидите, что мне понадобятся эти конкретные лакомства позже

Во-первых, давайте создадим функцию, которая проверяет, проверяет или проверяет, является ли что-то простым или нет.

def pkf(n):
if n%2==0:
    return False
else:
    if sqrt(n)-floor(sqrt(n))==0:
        return False
    else:
        for i in range(3,floor(sqrt(n)-1),2): 
            if n%i==0: 
                return False
        if n<=2:
            return False 
        else: return True

Итак, позвольте мне разбить это и объяснить шаг за шагом, как и почему это работает с максимальной оптимизацией.1012 *

Смысл в том, чтобы начать с того, что если вход делится на два, мы можем быстро списать его, вероятно, будет около 50% входных данных, и я использую структуру if else для дальнейшей оптимизации, поэтому мы не будемдолжны пройти через дополнительный код, когда ввод уже недействителен

if sqrt(n)-floor(sqrt(n))==0:

Если есть идеальный квадратный корень, мы можемограничить простую возможность

для i в диапазоне (3, этаж (sqrt (n) -1), 2): если n% i == 0: вернуть False

Начнем с 3, хотя 1 и 2 простые, они не того размера, который нам нужен. Поскольку мы отфильтровали все четные числа, все не простые нечетные числа при наличии округленного вниз квадратного корня, если существует какой-либо фактор, он существует между его квадратным корнем и ниже

Мы заканчиваем с округленным вниз квадратным корнем вмененного числа, опять же для оптимизации, все. Затем мы переходим с шагом 2, потому что мы начали с 3, что было нечетным, исключая половину необходимых вычислений

            if n<=2:
            return False 
        else: return True

Все, что меньше и включая 2, является техническим простым числом, однако это не шкала чисел, которые мы хотим, это может быть включено в начале, однако это дополнительная вычислительная мощность, очень маловероятно, что ваше минимальное значение установлено в 0, особенно если оно используется дляшифрование

полный код до сих пор

def pkf(n):
if n%2==0: #if it is devisable by two we can quickly write it off and I use an if else structure for optumisation
    return False
else:
    if sqrt(n)-floor(sqrt(n))==0:
        return False
    else:
        for i in range(3,floor(sqrt(n)-1),2): 
            if n%i==0: 
                return False
        if n<=2:
            return False 
        else: return True

Хорошо, теперь нам нужно 2 переменные, минимальное и максимальное значение для простого числа, Для enшифрование больших чисел лучше

mini=1e7
mx=1e11

Я использовал эти имена переменных для минимума и максимума соответственно, потому что мне лень набирать полные имена переменных, а max и min - параметры python, чтобы невсе закончилось хорошо

def genPrime():
    n=random.randint(mini,mx)
    while not pkf(n):
        n=random.randint(mini,mx)
    print(n)

В любом случае это поможет вам быстро выборочно использовать грубую силу с высокой оптимизацией, вот полный код

import random
from math import floor
from math import sqrt

mini=1e7
mx=1e11

def pkf(n):
    if n%2==0: #if it is devisable by two we can quickly write it off and I use an if else structure for optumisation
        return False
    else:
        if sqrt(n)-floor(sqrt(n))==0:
            return False
        else:
            for i in range(3,floor(sqrt(n)-1),2): 
                if n%i==0: 
                    return False
        if n<=2:
            return False 
        else: return True
def genPrime():
    n=random.randint(mini,mx)
    while not pkf(n):
        n=random.randint(mini,mx)
    print(n)
genPrime()

Спасибо за чтение моей статьи, я надеюсьчтобы сделать еще несколько из них, потому что я понимаю борьбу, я знаю, как stackoverflow печально известен тем, что забирает сообщения новых пользователей, но если они этого не делают, я надеюсь создать пошаговую инструкцию о том, как построить шифрование RSA на данный момент, так чточто вы, ребята, не должны волноваться, хотя я знаю, что получить хорошее оборудование, поэтому я делаю это доступным для вас, ребята, Счастливого кодирования!