The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..., opennews (??), 11-Фев-19, (0) [смотреть все]

Сообщения [Сортировка по времени | RSS]


78. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +/
Сообщение от Ordu (ok), 11-Фев-19, 18:58 
И каким образом простые числа можно "генерировать"

https://en.wikipedia.org/wiki/Generating_primes
For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly chosen range of odd numbers of the desired size is sieved against a number of relatively small primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard probabilistic primality test such as the Baillie-PSW primality test or the Miller-Rabin primality test for probable primes.

Alternatively, a number of techniques exist for efficiently generating provable primes. These include generating prime numbers p for which the prime factorization of p − 1 or p + 1 is known, for example Mersenne primes, Fermat primes and their generalizations.

Берём кучку нечётных чисел из заданного диапазона, делим небольшими простыми числами, отсеваем те, что делятся. Оставшиеся проверяем вероятностными алгоритмами, доводя вероятность их простоты до значения настолько близкого к 1, насколько это практически обоснованно. Либо, есть способы генерить случайные числа специального вида, про которые возможно доказать строго, что они простые.

> их можно только вычислить единственно возможным методом?

Насчёт способа вычислить простое число я не очень понимаю, но вот способов проверки на простоту -- десятки.

Ответить | Правка | К родителю #32 | Наверх | Cообщить модератору

88. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +/
Сообщение от Sw00p aka Jerom (?), 11-Фев-19, 20:52 
Генерация обычно подразумевает случайность, но это не так, то что вы описали это вероятностная выборка в следствии постулата Бертрана, выше я описал, что имел ввиду под словом генерация.

>Насчёт способа вычислить простое число я не очень понимаю, но вот способов проверки на простоту -- десятки.

Коментом выше как раз я это разъяснил, а по поводу способов, увы они все вероятностные, кроме перебора делителей и теоремы Вильсона, о чем я выше и упомянул.

Ответить | Правка | Наверх | Cообщить модератору

91. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +1 +/
Сообщение от Ordu (ok), 11-Фев-19, 21:26 
> Генерация обычно подразумевает случайность, но это не так, то что вы описали
> это вероятностная выборка в следствии постулата Бертрана, выше я описал, что
> имел ввиду под словом генерация.
>>Насчёт способа вычислить простое число я не очень понимаю, но вот способов проверки на простоту -- десятки.
> увы они все вероятностные

Почему "увы"? Какая разница с практической точки зрения? Ну, математикам это, понятно, неприятно, но мне, как программисту, разницы нет совершенно.


Ответить | Правка | Наверх | Cообщить модератору

100. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +/
Сообщение от Sw00p aka Jerom (?), 11-Фев-19, 22:40 
>Почему "увы"?

Да потому-что, та же малая теорема Ферма - вероятностный метод, потому-что существуют так называемые числа Кармайкла (561), которые удовлетворяют сравнению Ферма, но не являются простыми на самом деле (назвали их псевдопростыми, подробно в вике по запросу "простое число").

>Какая разница с практической точки зрения?

Математики, особенно занимающиеся "чистой" её частью, практической выгоды не ищут. Та же теорема Вильсона с практической стороны - не применима, в связи с пространственной сложности алгоритма, но для "чистого математика" - это абсолютный метод проверки на простоту числа, такой же как и перебор делителей.

Ответить | Правка | Наверх | Cообщить модератору

103. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +1 +/
Сообщение от Ordu (ok), 11-Фев-19, 23:13 
>>Почему "увы"?
> существуют так называемые числа Кармайкла (561), которые удовлетворяют сравнению Ферма, но не
> являются простыми на самом деле

Да и пусть их существуют. Мне-то что с того? Ну, возьмём любую практическую задачу, например, создание ключей для RSA. Мне нужно два простых числа, я могу сгенерировать два числа, которые будут простыми. Эмм... Точнее, насколько я помню RSA, мне нужны не столько два простых числа p и q, сколько произведение pq, которое никто не сможет разложить на множители. А для этого полезно, если и p, и q будут простыми. Но, если память меня подводит, то это не суть важно. Я могу используя вероятностные тесты получить два числа, которые с вероятностью X, будут простыми, где X настолько близок к 1, насколько мне нужно. Не, я соглашусь, если бы X был бы равен единице, было бы лучше, но практически это не важно, потому что вероятность того, что вся схема сработает как надо, всё равно будет ниже единицы. Как ни крути. Либо дыра в реализации протокола/алгоритма, либо пользователь лоханётся, либо ключи уведут, либо математики найдут способ факторизации... Я могу сделать вероятность лоханутся на выборе "простых" множителей настолько низкой, что она не будет идти ни в какое сравнение со всеми остальными вероятностями проколов.

>>Какая разница с практической точки зрения?
> Математики, особенно занимающиеся "чистой" её частью, практической выгоды не ищут.

В том-то и разница. Если математики найдут практический способ факторизовывать числа, то RSA моментально кончится, и мне не будет нужно генерировать простые числа для RSA. 100% надёжный способ генерации простых чисел, таким образом, совершенно непрактичен. Хоть и с теоретической точки зрения, было бы восхитительно такой способ найти.

Ответить | Правка | Наверх | Cообщить модератору

104. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +/
Сообщение от Sw00p aka Jerom (?), 12-Фев-19, 00:29 
>Я могу сделать вероятность лоханутся на выборе "простых" множителей настолько низкой, что она не будет идти ни в какое сравнение со всеми остальными вероятностями проколов.

Вот тут я не совсем понял, если мы разлагаем число на простые множители, то мы не выбираем (или гадаем), существует ровно одно единственное разложение натурального числа на простые множители, о чем говорит "основная теорема арифметики"

>Если математики найдут практический способ факторизовывать числа, то RSA моментально кончится, и мне не будет нужно генерировать простые числа для RSA.

таки да, RSA применим, покуда не разрешена проблема факторизации.

Ответить | Правка | Наверх | Cообщить модератору

115. "NVIDIA открыла код StyleGAN, генератора лиц на основе машинн..."  +1 +/
Сообщение от Ordu (ok), 12-Фев-19, 03:30 
>>Я могу сделать вероятность лоханутся на выборе "простых" множителей настолько низкой, что она не будет идти ни в какое сравнение со всеми остальными вероятностями проколов.
> Вот тут я не совсем понял, если мы разлагаем число на простые
> множители, то мы не выбираем (или гадаем), существует ровно одно единственное
> разложение натурального числа на простые множители, о чем говорит "основная теорема
> арифметики"

Я не совсем понял, что именно непонятно. Но у меня есть предположение.

Разложение единственно, но оно мне неизвестно. Речь не о том, как дела обстоят в математике, речь о том, как они обстоят в моей голове. Если у меня есть специально подобранное число X в пару тысяч бит, то я скорее всего не знаю его разложения на множители. Я могу предположить, что разложение числа X выглядит как X. В смысле, что оно простое. Иногда я буду ошибаться. Если я возьму N таких чисел, и про каждое предположу, что оно простое, то примерно в p*N случаях, я окажусь прав, примерно в (1-p)*N случаях, я окажусь не прав. p -- это достоверность моего предположения. Эта достоверность ведёт себя как вероятность, поэтому я называю её вероятностью. Она не совсем вероятность, потому что иногда её приходится получать способами, которые математика сочла бы странными и даже вообще бы не сочла способами. Но и тем не менее она ведёт себя как вероятность, и её вполне можно скармливать в теорию игр.

Ответить | Правка | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру