Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Заблокирован

Blum Blum Shub

15.10.2015, 09:32. Показов 2158. Ответов 18
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
помогите разобраться в алгоритме Blum Blum Shub пожалуйста, вот например в начале там генерируются два числа "Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4" так написано в википедии, а что значит сравнимы с 3 по модулю 4? как это вообще понимать?
0
Лучшие ответы (1)
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.10.2015, 10:21
Если число сравнимо с 3 по модулю 4, то это понимается однозначно. То есть при делении числа на 4, получается в остатке 3. Обычно говорят иначе. Два числа сравнимы по модулю третьего числа тогда и только тогда, когда их разность делится на это число.
1
Заблокирован
15.10.2015, 10:41  [ТС]
ну а дальше? вот тут вот смотрю алгоритм, что значит число взаимно простое с M? я знаю что такое простые числа, но что значит взаимно простое с M? и дальше "На каждом шаге генерации последовательности вычисляется число xi+1 = xi2 mod M." что за Xi? т.е. предыдущее число возвести в квадрат и взять остаток от деления на M? и последнее "В качестве результата возвращается последний бит числа xi." и что из этого выйдет? один бит серьезно? это же или 0 или 1, что это за генератор который генерирует только два числа? или я че то не так понял?
Миниатюры
Blum Blum Shub  
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.10.2015, 10:51
Volrajas,
Давайте по порядку. Я тоже хочу разобраться. Ну во первых числа называются взаимно простыми, если у них нет общих делителей отличных от 1. Например 24 и 35 - взаимно простые числа. Кстати простые числа всегда взаимно простые.
1
Заблокирован
15.10.2015, 10:57  [ТС]
geh, погодите я вот что подумал, а вообще откуда взять эти p и q? обычно в гпсч при инициализации подается некий seed (или берется текущее время) с которого и начинается генерация, а как тут? как из этого инициализирущего числа будут генерироваться эти p и q?
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.10.2015, 11:10
*xi+1 = xi2 mod M. (??)
Вероятно вы хотели написать следующее.
Переменная x (с индексом i+1) присваивает значение переменной x (с индексом i) возведенную в квадрат и от всего этого вычислен остаток по модулю М.

Добавлено через 7 минут
Есть два способа генерации простых чисел. Один из них создать файл простых чисел и оттуда брать готовые числа. Второй способ это генерировать целое число, которое потом проверяется простое оно или нет. Если нет, то вновь генерируется целое число и вновь проверка и тд.
0
Заблокирован
15.10.2015, 11:23  [ТС]
Цитата Сообщение от geh Посмотреть сообщение
генерировать целое число, которое потом проверяется простое оно или нет. Если нет, то вновь генерируется целое число и вновь проверка и тд.
эмм что рандомно генерировать? т.е. для генерации рандомных чисел надо генерировать рандомные числа?
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.10.2015, 11:39
Лучший ответ Сообщение было отмечено Volrajas как решение

Решение

Да. Тут выбора нет. Либо вы имеете файл прямого доступа с заранее вычисленными простыми числами. Либо числа придется определять тем или иным способом. Разумеется не все определяется рандомно. Если вы имеете число в качестве ключа, то исходя из него можно найти ближайшее к этому ключу простое число, сам ключ может быть простым числом. Но его еще надо вычислить. И никуда от этого не деться.
1
Заблокирован
15.10.2015, 12:13  [ТС]
Цитата Сообщение от geh Посмотреть сообщение
Да. Тут выбора нет. Либо вы имеете файл прямого доступа с заранее вычисленными простыми числами. Либо числа придется определять тем или иным способом. Разумеется не все определяется рандомно. Если вы имеете число в качестве ключа, то исходя из него можно найти ближайшее к этому ключу простое число, сам ключ может быть простым числом. Но его еще надо вычислить. И никуда от этого не деться.
ну файл с простыми числами это не интересно, его надо таскать за собой везде, а вот генерировать мне больше нравится, т.е. например я получаю при инициализации число и иду значит в обе стороны от него и ближайшее меньшее от инициализирущего числа простое число становится p, а большее q, так?
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
15.10.2015, 12:16
Цитата Сообщение от Volrajas Посмотреть сообщение
"На каждом шаге генерации последовательности вычисляется число xi+1 = xi2 mod M." что за Xi? т.е. предыдущее число возвести в квадрат и взять остаток от деления на M?
Да.
А формулу лучше записать с использованием псевдотэгов SUP и SUB:
xi+1 = xi2 mod M
0
Заблокирован
15.10.2015, 12:18  [ТС]
а что там с последним этапом? "В качестве результата возвращается последний бит числа xi"
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
15.10.2015, 12:25
Цитата Сообщение от Volrajas Посмотреть сообщение
и последнее "В качестве результата возвращается последний бит числа xi." и что из этого выйдет? один бит серьезно? это же или 0 или 1, что это за генератор который генерирует только два числа? или я че то не так понял?
В чём Вы видите проблему? Вы можете сгенерировать столько бит, сколько Вам нужно. Например, чтобы получить 32-битное число, повторите процедуру 32 раза.
Можно брать не 1, а log log M бит. Это несколько снизит надёжность, но не существенно.

Добавлено через 3 минуты
Цитата Сообщение от Volrajas Посмотреть сообщение
а вообще откуда взять эти p и q? обычно в гпсч при инициализации подается некий seed
Вы их выбираете один раз в начале, когда пишете свой генератор. Выбирать нужно так, чтобы они удовлетворяли описанным в вики (трём) условиям.
Если злоумышленник узнает, какие числа Вы выбрали, то он, теоретически, сможет научиться "угадывать" следующее случайное число.
1
Заблокирован
15.10.2015, 12:43  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
В чём Вы видите проблему? Вы можете сгенерировать столько бит, сколько Вам нужно. Например, чтобы получить 32-битное число, повторите процедуру 32 раза.
Можно брать не 1, а log log M бит. Это несколько снизит надёжность, но не существенно.
ааа т.е. брать от каждого сгенерированного числа по одному или log(log(M)) бит и объединять их в число сдвигами?
Цитата Сообщение от Shamil1 Посмотреть сообщение
Вы их выбираете один раз в начале, когда пишете свой генератор. Выбирать нужно так, чтобы они удовлетворяли описанным в вики (трём) условиям.
Если злоумышленник узнает, какие числа Вы выбрали, то он, теоретически, сможет научиться "угадывать" следующее случайное число.
нет уж, по моему предыдущая идея была удачнее
Цитата Сообщение от Volrajas Посмотреть сообщение
я получаю при инициализации число и иду значит в обе стороны от него и ближайшее меньшее от инициализирущего числа простое число становится p, а большее q
Добавлено через 1 минуту
кстати кто подскажет хороший быстрый способ проверить число на простоту? знаю их куча, но все же...

Добавлено через 14 минут
например
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPrime(unsigned long long value)
{
    if (value < 2)
        return false;
 
    unsigned long long value_sqrt = (unsigned long long)sqrt(value);
 
    for (int i = 2; i < value_sqrt; i++)
        if (value % i == 0)
            return false;
 
    return true;
}
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
15.10.2015, 12:58
Цитата Сообщение от Volrajas Посмотреть сообщение
по моему предыдущая идея была удачнее
Это не то место, где можно импровизировать. Скорее всего, Вы получите далеко не случайное распределение чисел. Насколько Вам понравится, если Ваш генератор будет выдавать, например, только чётные числа (упрощаю)?
0
Заблокирован
15.10.2015, 13:42  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Это не то место, где можно импровизировать. Скорее всего, Вы получите далеко не случайное распределение чисел. Насколько Вам понравится, если Ваш генератор будет выдавать, например, только чётные числа (упрощаю)?
да с чего вы взяли что будет что то подобное? мне не понравится другое, то что если брать предопределенные p и q генератор всегда (с запуска программы) будет выдавать одинаковую последовательность, вот это действительно мне не понравится
0
Эксперт функциональных языков программированияЭксперт по математике/физике
4312 / 2104 / 431
Регистрация: 19.07.2009
Сообщений: 3,195
Записей в блоге: 24
15.10.2015, 13:47
Цитата Сообщение от Shamil1 Посмотреть сообщение
А формулу лучше записать с использованием псевдотэгов SUP и SUB:
Лучше LaTeX.
Цитата Сообщение от Volrajas Посмотреть сообщение
да с чего вы взяли что будет что то подобное? мне не понравится другое, то что если брать предопределенные p и q генератор всегда (с запуска программы) будет выдавать одинаковую последовательность, вот это действительно мне не понравится
Раз Вы читаете хабру, то, вероятно, прочитали про регистр сдвигов. Там, если помните, последовательность определяется начальным состоянием регистров и полиномом, который задаёт новое состояние крайнего регистра по старым состояниям всех регистров. Вопрос: какой полином выбирается? Задаётся ли он единоразово ручками или его стоит генерировать каждый раз неким (псевдо)случайным образом? Вот константы p и q играют ту же роль в Blum Blum Shub. Как уже сказал Shamil1, эти параметры выбираются обычно единоразово, а для этого можно и файл за собой потаскать, вся же недетерминистичность, которой Вы обеспокоены, сосредоточена в выборе x0.
Цитата Сообщение от Volrajas Посмотреть сообщение
брать от каждого сгенерированного числа по одному или log(log(M)) бит и объединять их в число сдвигами?
Общая постановка проблемы ГПСЧ — нагенерировать потенциально бесконечную последовательность бит. В этом смысле речь идёт скорее о конкатенации последовательностей с каждого шага в одну большую.
0
Модератор
Эксперт функциональных языков программирования
3132 / 2279 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
15.10.2015, 14:55
1. Если мы возьмём произвольную последовательность, задаваемую рекурентной формулой, то практически всегда распределение будет далеко от случайного. Вы только что придумали свою формулу. Вероятность того, что она будет выдавать последовательность, хоть сколько-нибудь напоминающую случайную, близка к нулю.

2. Из каких-то соображений Вы хотите реализовать алгоритм ББС - далеко не самый простой и далеко не самый быстрый. Видимо, Вам нужен именно этот алгоритм. Если Вы поменяете формулу, то это будет уже совсем другой алгоритм.

з.ы. Если Вам всё равно, какой алгоритм использовать, то могу предложить простую формулу:
xi+1 = дробная_часть(105.947 * xi)
Легко реализуется и быстро работает. Случайность более-менее.
0
1 / 1 / 0
Регистрация: 15.12.2025
Сообщений: 2
15.12.2025, 10:07
В ИИ можно сгенерировать работающий проект на Java для Android Studio с использованием алгоритма Блюма Блюма Шуба.
Для этого можно ввести в Дипсик следующий запрос (представлен ниже). Проект проверялся на Android 11. В запросе можно поменять на другой

Текст запроса

Сгенерируй максимально простой Java код приложения DeepseekBlume для Android 11 для SDK 33.
Разметка в Activity_main.xml должна позволять вертикальную прокрутку экрана для просмотра всего содержимого.
Нужно запросить и получить все необходимые для работы приложения разрешения, в том числе и разрешение на чтение и запись данных

В самом верху экрана разместить поле первого EditText для ввода текста. В первом EditText в подсказку Hint написать текст: "Введите не менее 100 символов для создания ключа".

Создадим Int переменную E=2048

При вводе текста в это поле надо проверять количество введенных символов. Не разрешать вводить в это поле первого EditText больше 120 символов.
Как только количество введенных символов в поле первого EditText станет больше 100, нужно преобразовать введенный текст в Big Int число и записать его в переменную L размерности E бит, и выполнить следующие действия в пункте NN
.
Начало пункта NN

Проверить наличие файла xor.txt в папке Download смартфона. Если файл xor.txt существует - удалить его.
Нужно проверить в папке Download смартфона наличие текстового файла digital.bbs в формате JSON
Если файла digital.bbs в папке Download НЕТ, то выполнить лействия в пункте 1. Если в папке Download есть файл digital.bbs то пункт 1 не выполнять, а прочитать значения чисел P, Q, L из файла digital.bbs

Начало пункта 1.
Приложение должно вычислить два простых Big Int числа P и Q размерности E бит, удовлетворяющих условию, что каждое из них при делении на 4 даёт остаток 3
На экране приложения должны располагаться несколько TextView
В один TextView необходимо написать число P
Во второй TextView необходимо написать число Q
Необходимо вычислить число M=P*Q
Выбираем случайное Big Int число L размерности E бит, взаимно простое с M
Создать в папке Download смартфона текстовый файл digital.bbs и записать в него вычисленные значения чисел P, Q, L в формате JSON
Конец пункта 1.

Необходимо вычислить число M=P*Q

Вычисляем Big Int число K = L*L (т.е. как L в степени 2)

Находим Big Int число H=K mod M
В третий TextView необходимо записать Big Int число H

Далее создадим функцию DigCreate, которую используем E раз.
Создадим Big Int переменную NumRnd, с которой будем производить битовые операции.

Функция DigCreate делает E раз следующее:

Начало пункта 2.
- вычислим число N=(H*H) mod M
- из числа N выберем самый младший бит (бит чётности)
- в числе NumRnd сделаем сдвиг битов влево на одну позицию. При этом самый старший бит (самый правый) отбрасывается
- запишем значение из младшего бита числа N в младший бит числа NumRnd
- присвоим значение числа N числу H
- повторим действия, начиная с пункта 2.

После этого в числе NumRnd должны быть заполнены все биты.

Напишем число NumRnd в четвёртый TextView

Далее с числом NumRnd нужно произвести битовые операции.
1. Запомнить значение младшего бита (бита чётности)
2. Сдвинуть все биты числа NumRnd на один бит вправо
3. Записать запомненный в пункте1 бит чётности в самый старший (правый) бит числа NumRnd

Написать число NumRnd в пятый TextView

Конец пункта NN

Ниже пятого TextView разместить поле второго EditText для ввода текста пользователем. В втором EditText в подсказку Hint написать текст: "Введите текст для обработки. Только буквы. Не более 200 символов".
В java коде в MainActivity.java написать комментарий:"В это поле EditText вводить только буквы. Цифры писать словами. Всего не более 200 символов"

Ограничить количество вводимых символов в поле второго EditText - не более 200 символов.

Ниже второго EditText разместить кнопку с надписью "XOR". Рядом с кнопкой "XOR" разместить кнопку "XOR2". Создать BigInt переменную ResultText

Ниже кнопок разместить шестой TextView. В шестом TextView в подсказку Hint написать текст: "Преобразованный в число введенный текст".

При нажатии на кнопку "XOR" :
- сначала преобразовать текст, введённый в поле второго EditText в BigInt число и записать в переменную EnText и в шестой TextView.
- затем выполнить бинарную операцию XOR между числами NumRnd и EnText
- очистить поле второго EditText

Ниже шестого TextView разместить седьмой TextView. В седьмом TextView в подсказку Hint написать текст: "Восстановленный текст".
Записать полученный результат в текстовый файл xor.txt в папку Download смартфона, в переменную ResultText и так же поместить результат операции XOR в поле второго EditText

При нажатии на кнопку "XOR2" нужно сделать следующее:
- очистить поле второго EditText
- произвести бинарную операцию XOR между числами NumRnd и ResultText и записать в поле второго EditText. Преобразовать этот результат в текст и записать в седьмой TextView
0
15.12.2025, 12:49

Не по теме:

Mysterious Light, вот тема где (давно) нужна Ваша помощь

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Ниже машинный перевод статьи The Thinkpad X220 Tablet is the best budget school laptop period . Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы,. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru