Форум программистов, компьютерный форум, киберфорум
Криптография
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
1 / 1 / 0
Регистрация: 14.05.2020
Сообщений: 143

Шаг младенца шаг великана в Java BigInteger

05.10.2022, 18:21. Показов 453. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Сижу уже 3 день, проверял через отладку, все равно не вижу ошибки.
Для начала работы мы выбираем m=k=sqrt(p) + 1. Затем начинаем раскладывать 2 ряда:
Первый: (a,ay,a^2 * y....a^(m-1) * y) mod p
Второй: (a^m, a^2m...a^km) mod p
Затем мы ищем первое попавшиеся значение из 1 ряда во втором и записываем индексы обоих, ответом должно быть
x = im - j, так же должно выполняться равенство a^(im) = a^j * y

Вот код
Java
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
BigInteger p = new BigInteger("61");
 
    BigInteger m = p.sqrt().add(BigInteger.ONE);
    BigInteger k = p.sqrt().add(BigInteger.ONE);
 
    BigInteger a = new BigInteger("2");
    BigInteger y = new BigInteger("45");
 
    ArrayList<BigInteger> array1 = new ArrayList<>();
    ArrayList<BigInteger> array2 = new ArrayList<>();
 
    for(BigInteger i = BigInteger.ZERO; i.compareTo(m) < 0; i = i.add(BigInteger.ONE)) {
        BigInteger temp = y.multiply(a.pow(i.intValue())).mod(p);
        System.out.println(temp);
        array1.add(temp);
    }
 
    System.out.println("---------------------------------------------------------");
    System.out.println("---------------------------------------------------------");
    System.out.println("---------------------------------------------------------");
 
 
    for(BigInteger j = BigInteger.ONE; j.compareTo(k) < 0; j = j.add(BigInteger.ONE)) {
        BigInteger temp = a.pow(j.multiply(m).intValue()).mod(p);
        array2.add(temp);
        System.out.println("temp = " + temp);
        for(int h = 0; h < array1.size(); h++) {
            if(Objects.equals(array1.get(h), temp)) {
                System.out.println(a.pow(m.multiply(BigInteger.valueOf(h)).intValue()));
                System.out.println(a.pow(j.intValue()).multiply(y));
                System.out.println("h = " + h + " m = " + m + " j = " + j);
                return BigInteger.valueOf(h).multiply(m).subtract(j);
            }
            /*if(a.pow(m.multiply(BigInteger.valueOf(h)).intValue()).equals(a.pow(j.intValue()).multiply(y))) {
                System.out.println("h = " + h + " m = " + m + " j = " + j);
                return new BigInteger("-1");
            }*/
        }
    }
 
    return new BigInteger("-1");
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
05.10.2022, 18:21
Ответы с готовыми решениями:

"Шаг младенца" "шаг великана"
Используя алгоритм &quot;Шаг младенца&quot; &quot;шаг великана&quot;, решить следующее уравнение 2 в степени X mod61=45 Может кто решить? ...

Шаг младенца, шаг великана Трудоемкость
Помогите реализовать данную функцию с трудоемкостью (√P×logP). Как делать именно поиск равных шагов, не сравнивая оба массива. ...

Необходимо реализовать программу для решения сравнения вида y = a^x (mod m) методом "Шаг младенца шаг великана"
Необходимо Реализовать программу для решения сравнения вида y = a^x (mod m) методом &quot;Шаг младенца шаг великана&quot;. На входе...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
05.10.2022, 18:21
Помогаю со студенческими работами здесь

Шаг младенца, шаг великана
Подскажите, пожалуйста как решить проблему. У меня код: import math def mod(g,x,p): mod = 1; for i in range(x): ...

Шаг младенца, шаг великана
Здравствуйте, уважаемые форумчане. Начал изучать методы, основанные на дискретном логарифмировании, а именно метод &quot;Шаг младенца,...

Алгоритм "Шаг младенца, шаг великана"
Всем привет, была поставлена задача найти x: 2x mod 30203 = 24322 (ax mod p = y) Накидал код до момента нахождения общих чисел из ряда...

Метод "шаг младенца, шаг великана" (метод Шенксона)
Помогите с программной реализацией алгоритма дискретного логарифмирования методом &quot;шаг младенца, шаг великана&quot; (Шенксона) ...

Шаг компиляции, шаг компоновки, и шаг запуска
Что происходит на шаге компиляции, шаге компоновки, и шаге запуска, с переменными и функциями. что происходит при встрече в коде...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru