Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 22 23 24 25 26 [27] 28 29 30 31   вперед  Ctrl
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
А кто-нибудь рассматривал обратную задачу.

Имеется число, в районе 1.0Е+14, и для него применили один из известных тестов простоты.
Тест показал, что это число не является составным числом.

А что при этом покажет калькулятор по поиску составных чисел?
15 мар 19, 09:47    [21833317]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Откуда мы знаем что покажет неизвестный калькулятор?
15 мар 19, 09:51    [21833324]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Откуда мы знаем что покажет неизвестный калькулятор?
Вы же сами его рекомендовали21819124!!
15 мар 19, 09:54    [21833333]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Я тебя умоляю. Это была случайная ссылка. Вобщем вопрос твой прозвучал как лёгкий троллинг.
Разумеется мы не знаем. И не знаем ограничений калькуляторов онлайн. Подозреваю что они
везде есть.
15 мар 19, 11:21    [21833445]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
mayton
Я тебя умоляю. Это была случайная ссылка. Вобщем вопрос твой прозвучал как лёгкий троллинг.
Разумеется мы не знаем. И не знаем ограничений калькуляторов онлайн. Подозреваю что они
везде есть.
Поскольку этот калькулятор находит множитель 40637, 438241, 942899.21832486, то, скорее всего, калькулятор имеет дело с большим массивом простых чисел.

Правда величина этого массива ограничена какой-то величиной (не может быть бесконечной из-за памяти).

Поэтому было бы интересно сравнить тест на простоту и действия калькулятора.
15 мар 19, 11:35    [21833477]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Решил ещё проверить калькулятор.

Взял "его" два простых числа:11100097 и 11100041,
перемножил, получил 123211531803977

Так калькулятор "назвал" именно эти два множителя.
15 мар 19, 12:19    [21833571]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Gennadiy Usov
mayton
Я тебя умоляю. Это была случайная ссылка. Вобщем вопрос твой прозвучал как лёгкий троллинг.
Разумеется мы не знаем. И не знаем ограничений калькуляторов онлайн. Подозреваю что они
везде есть.
Поскольку этот калькулятор находит множитель 40637, 438241, 942899.21832486, то, скорее всего, калькулятор имеет дело с большим массивом простых чисел.

Правда величина этого массива ограничена какой-то величиной (не может быть бесконечной из-за памяти).

Поэтому было бы интересно сравнить тест на простоту и действия калькулятора.


Не обязательно массив простых, есть разные алгоритмы.
Для больших чисел типа 21024 нереально хранить массив всех возможных множителей (до 2512).
15 мар 19, 12:20    [21833576]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Давайте порассуждаем. Для разложения RSA у нас есть заведомо известный факт. Множителей два.
И я предполагаю что они не тривиальные. Тоесть не маленькие. В районе квадратного корня
от 2^2048. Тоесть множители a,b лежат в окрестности средней части гиперболической области
которая очерчивает всё множество на плоскости с осями a,b.
15 мар 19, 12:42    [21833607]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mayton
Давайте порассуждаем. Для разложения RSA у нас есть заведомо известный факт. Множителей два.
И я предполагаю что они не тривиальные. Тоесть не маленькие. В районе квадратного корня
от 2^2048. Тоесть множители a,b лежат в окрестности средней части гиперболической области
которая очерчивает всё множество на плоскости с осями a,b.

Допустим они по 1024 бита, т.е. 21024 - 21023 = 21023 значений. Столько не перебрать.
15 мар 19, 12:48    [21833616]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Gennadiy Usov
Поскольку этот калькулятор находит множитель 40637, 438241, 942899.21832486, то, скорее всего, калькулятор имеет дело с большим массивом простых чисел.
Правда величина этого массива ограничена какой-то величиной (не может быть бесконечной из-за памяти).
Здесь я ошибаюсь.

Нашёл время, и почитал описание калькулятора.

А там - обычное 6·k±1, то есть, и простые, и составные.
Правда, непонятно, как он отличает 5 х 7 от 35?
15 мар 19, 12:52    [21833630]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2095
kealon(Ruslan)
например, что бы получить разложение по спектрам физически достаточно использовать призму, а вот что бы сделать это алгебраически O(N*Log(N)) в самом лучшем случае

Какая связь с простыми? Перевод спектра в факторизацию имеется?
15 мар 19, 12:52    [21833631]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
Dima T
mayton
Давайте порассуждаем. Для разложения RSA у нас есть заведомо известный факт. Множителей два.
И я предполагаю что они не тривиальные. Тоесть не маленькие. В районе квадратного корня
от 2^2048. Тоесть множители a,b лежат в окрестности средней части гиперболической области
которая очерчивает всё множество на плоскости с осями a,b.

Допустим они по 1024 бита, т.е. 21024 - 21023 = 21023 значений. Столько не перебрать.
А множители - простые числа, или ещё надо проверять?
15 мар 19, 12:54    [21833635]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Basil A. Sidorov
Basil A. Sidorov
Бесконечность, умноженная на любое конечное число так и остаётся бесконечностью.
Ограничение забыл: на любое конечное число, не равное нулю.

Ещё ограничение - любое положительное число. Иначе будет минус бесконечность. Это в другую сторону.
15 мар 19, 12:54    [21833637]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Gennadiy Usov
Dima T
пропущено...

Допустим они по 1024 бита, т.е. 21024 - 21023 = 21023 значений. Столько не перебрать.
А множители - простые числа, или ещё надо проверять?

Простые.
15 мар 19, 12:59    [21833648]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9133
alex55555
Ещё ограничение - любое положительное число. Иначе будет минус бесконечность. Это в другую сторону.
1. Я не уточнял знак;
2. Если представить плоскость комплексных чисел и сферу единичного радиуса, касающуюся начала координат плоскости, то можно отобразить все "плоскостнЫе" бесконечности на единственную точку сферы.
15 мар 19, 13:00    [21833651]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Сишники есть? Я думаю если посмотреть исходники openssl , ssh-keygen то мы там найдем
примерный вид алгоритма.

Кто может осилить это? Подробно не надо. Хотя-бы в общих чертах. Из каких блоков состоит
алгоритм и что каждый блок делает. И limitations. Разрядность там и прочее.
15 мар 19, 13:24    [21833715]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9133
Я, конечно, не копенгаген, но, вроде как, в криптографии требуются не простые, а взаимно простые числа ...
15 мар 19, 13:46    [21833760]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
alex55555
kealon(Ruslan)
например, что бы получить разложение по спектрам физически достаточно использовать призму, а вот что бы сделать это алгебраически O(N*Log(N)) в самом лучшем случае

Какая связь с простыми? Перевод спектра в факторизацию имеется?

с помощью интерференции волн можно найти довольно много решений для дискретных задач

вот только видишь, с маштабами пролетаем
15 мар 19, 13:47    [21833763]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton
Давайте порассуждаем. Для разложения RSA у нас есть заведомо известный факт. Множителей два.
И я предполагаю что они не тривиальные. Тоесть не маленькие. В районе квадратного корня
от 2^2048. Тоесть множители a,b лежат в окрестности средней части гиперболической области
которая очерчивает всё множество на плоскости с осями a,b.

ну будет размер это части не 2^2k, а 2^k

т.е. не 10^550 световых лет, 10^350 световых лет - это больше чем видимая вселенная

при этом ещё надо как-то придумать чем дискретизировать до длины Планка
15 мар 19, 13:51    [21833776]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton,

пардон

т.е. не 10^550 световых лет, 10^250 световых лет - это больше чем видимая вселенная
15 мар 19, 13:52    [21833779]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Хм.. Как эта информация нам поможет?
15 мар 19, 14:07    [21833829]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton
Хм.. Как эта информация нам поможет?
она нас сразу отсекёт делать глупости, хотя я придумал как физически разложить на множители
если бы не это НО
15 мар 19, 14:11    [21833839]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
mayton,

LC -касательная к окружности

что мы знаем из геометрии LC^2 = LA * LB

если мы поместим два когерентных источника света в точки L и O

то точки А и B высветятся за счёт интерференции

К сообщению приложен файл. Размер - 5Kb
15 мар 19, 14:21    [21833860]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1462
kealon(Ruslan)
mayton
Хм.. Как эта информация нам поможет?
она нас сразу отсекёт делать глупости, хотя я придумал как физически разложить на множители
если бы не это НО
А может надо не раскладывать на множители, а собирать множители.

Время собирать...
15 мар 19, 14:23    [21833866]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Basil A. Sidorov
Я, конечно, не копенгаген, но, вроде как, в криптографии требуются не простые, а взаимно простые числа ...

надо простые
https://ru.wikipedia.org/wiki/RSA#Алгоритм_создания_открытого_и_секретного_ключей
1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).
15 мар 19, 14:34    [21833893]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 22 23 24 25 26 [27] 28 29 30 31   вперед  Ctrl
Все форумы / Программирование Ответить