F
По какой формуле обычно генерируют большие простые числа?
Size: a a a
2021 January 15
FR
По какой формуле обычно генерируют большие простые числа?
Почему-то я уверен, что формулы как таковой нет (см. проблему распределения простых чисел), но есть вероятностные алгоритмы проверки их простоты: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B.
БГ
БГ
Почему-то я уверен, что формулы как таковой нет (см. проблему распределения простых чисел), но есть вероятностные алгоритмы проверки их простоты: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B.
Если мне не изменяет память то есть алгоритм проверки на простоту который работает за O(n*log(n))
F
Там была формула, вроде Эйлера
SS
Если мне не изменяет память то есть алгоритм проверки на простоту который работает за O(n*log(n))
Тест Ферма, если уже мне не изменяет память, работает за O(K*log(n)*log(n))
F
А не проще просто взять таблицу готовых чисел и умножать?
Мне просто интересно как на практике
Мне просто интересно как на практике
SS
Но ведь вопрос был именно по БОЛЬШИМ простым числам
AL
А не проще просто взять таблицу готовых чисел и умножать?
Мне просто интересно как на практике
Мне просто интересно как на практике
Ты имеешь ввиду? П p_i + 1? Где p это простые числа.
F
Ну да, умножать много раз)
/* */ не помню точно, возможно да
/* */ не помню точно, возможно да
F
Там ещё +1 оказывается
F
Либо хранить пару больших чисел и потом с низ генерить
F
Мне 256 бит максимум, для кривых
Для рса вообще и по 4096 делают и по 16к где-то видел
Для рса вообще и по 4096 делают и по 16к где-то видел
AL
Ты делаешь произведение из всех простых чисел до какого-то n, потом + 1. Согласно главной теоремы арифметики 100% будет простое число.
AL
Либо хранить пару больших чисел и потом с низ генерить
А как?
F
А как?
Найти где-то, надо посмотреть как в пакетах это делается, либо взять готовый.
Но стало интересно как там делают это.
Оно работает очень быстро, это не считается проблемой, значит там есть тривиальное решение.
Но стало интересно как там делают это.
Оно работает очень быстро, это не считается проблемой, значит там есть тривиальное решение.
FR
Мне 256 бит максимум, для кривых
Для рса вообще и по 4096 делают и по 16к где-то видел
Для рса вообще и по 4096 делают и по 16к где-то видел
может я Вам программу для генерирования дам?
FR
Найти где-то, надо посмотреть как в пакетах это делается, либо взять готовый.
Но стало интересно как там делают это.
Оно работает очень быстро, это не считается проблемой, значит там есть тривиальное решение.
Но стало интересно как там делают это.
Оно работает очень быстро, это не считается проблемой, значит там есть тривиальное решение.
Сначала берётся случайное нечётное натуральное, а потом уже проверяется на простоту вероятностными тестами. Если тест провален, число увеличивается на 2 или 4 в зависимости на какую цифру оно оканчивается.
F
Сначала берётся случайное нечётное натуральное, а потом уже проверяется на простоту вероятностными тестами. Если тест провален, число увеличивается на 2 или 4 в зависимости на какую цифру оно оканчивается.
Надо очень большое число мне кажется сразу
F
А может реально подбором это делается?)