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

@xXapokalypsesXx · Регистрация: 25.10.2015

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста решить задачу.

Алгоритм Гордона для генерации сильно простого числа:
1. Сгенерировать два больших простых числа s и t одной длины.
2. Выбрать число i₀. Найти первое простое число в последовательности 2it + 1, где i = i₀, i = i + 1. Обозначить это число r = 2it + 1.
3. Вычислить p₀ = 2 (s^r-2 mod r) s - 1.
4. Выбрать число j₀. Найти первое простое число в последовательности p₀ + 2jrs, где j = j₀, j = j + 1. Обозначить это число p = p₀ + 2jrs.
5. Вернуть p.

Реализовал все пункты, кроме 2 и 4.
В втором пункте нужно найти число r.
В четвертом пункте нужно найти число p.
Возможно в обеих пунктах нужно использовать циклы, но я пока не понимаю как их правильно написать, чтобы вычислить числа r и p.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Пункт 1
s = 78479 # Сгенерированное число s
t = 86399 # Сгенерированное число t
 
# Пункт 2
i0 = 3 # Выбранное число i0
r = None # Проблема здесь
 
# Пункт 3
p0 = 2 * (pow(s, r - 2) % r) * s - 1 # Вычисленное число p0
 
# Пункт 4
j0 = 9 # Выбранное число j0
p = None # Проблема здесь
 
# Пункт 5
print(p) # Вывод числа p

@Conlon · 22.02.2021, 02:35

Для тех кто зайдет в 21 году!

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util import number
 
 
def getStrongPrime(N):
    s = number.getPrime((N // 2) - 8)
    t = number.getPrime((N // 2) - 8)
    i = 1
 
    while True:
        r = 2 * i * t + 1
        i += 1
        if number.isPrime(r, 20):
            break
 
    z = pow(s, (r - 2), r)
    pstar = 2 * z * s - 1
    k = 1
    p = 2 * r * s + pstar
    while p.bit_length() <= N:
        k = k * 2
        p = 2 * k * r * s + pstar
 
    while not number.isPrime(p, 20):
        k = k + 1
        p = 2 * k * r * s + 1
 
    list = [p, r]
    return list

N - нужная битовая длина

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем