IT в России и мире в реалиях мирового кризиса

1,268,162 7,776
 

Explorer-2000
 
canada
Слушатель
Карма: -76.02
Регистрация: 29.12.2015
Сообщений: 3,761
Читатели: 1

Аккаунт заблокирован
Цитата: Поверонов от 14.11.2019 09:06:41Этого не знаю точно. Вот нашел 
Еще раз о поиске простых чисел\n\nТам есть ссылка на
[url=file:///home/vlad/download/[Vasilenko_O._N.]_Teoretiko-chislovuee_algoritmue_(BookFi).pdf]Теоретико-числовые алгоритмы в криптографии Василенко О. Н.[/url]

Ну так упрощение поиска простых чисел как раз помогает в криптографииПодмигивающий, а так в RSA надо наоборот разложить составное число на простые, в книге Василенко как раз описаны такие алгоритмы, но среди них нет волшебных полиномов находящих все простые числа т.к. это ничего не даёт
  • +0.00 / 0
Поверонов
 
Слушатель
Карма: +37.12
Регистрация: 05.06.2010
Сообщений: 18,863
Читатели: 7
Цитата: Explorer-2000 от 15.11.2019 05:51:22Ну так упрощение поиска простых чисел как раз помогает в криптографииПодмигивающий, а так в RSA надо наоборот разложить составное число на простые, в книге Василенко как раз описаны такие алгоритмы, но среди них нет волшебных полиномов находящих все простые числа т.к. это ничего не даёт

криптостойкость шифров оценивается временем необходимом ( по мнению  оценщиков ) для их взлома на самых быстрых современных суперкомпьютерах. При этом время вычисляется по числу необходимых операций ( по мнению оценщиков ), так что если число необходимых операций вдруг оказывается на порядки меньше ( чем представлялось оценщикам ) то и криптостойкость падает на те же порядки.
В частности с появлением квантовых компьютеров сейчас пересматриваются криптостойкости всех шифров уже относительно них.
PS. Да паника была напрасной - конструктивного алгоритма построения такого полинома пока не обнаружили ( или не опубликовали Улыбающийся ), но потенциально такая возможность сохраняется и все криптостойкости пришлось пересматривать.
В частности DES превратился в 3DES
Отредактировано: Поверонов - 15 ноя 2019 08:52:58
  • +0.00 / 0
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: TAU от 13.11.2019 01:44:15Отборный бред, наверное, грибочки? Или травы хватило?\n\n
По поводу применения... Модула-2 в российском космосе \n\n
Ну и, чтобы "добить" - стандарт
Приятного чтения!

Это не стандарт, а говнопособие для студентов. Стандарт, это когда ANSI, ISO/IEC или ГОСТ. Все остальное – мусор.
  • -0.03 / 1
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: GrinF от 13.11.2019 01:50:34Ты камерад шутишь неудачно? Полином любой  любым степени любого числа переменных над конечным полем имеет конечное множество значений, а множество простых чисел как известно со времён Пифагора бесконечно...это во первых
Во вторых...как можно за полиномиальное время по длине сгенерировать множество число элементов которого O(2^l/l), l -длина строки описывающее простое число....а пространственная сложность любого полинома никакая O(l)....

Что такое "конечный полином"?
  • +0.00 / 0
GrinF
 
Слушатель
Карма: +72.26
Регистрация: 15.02.2018
Сообщений: 6,177
Читатели: 3
Цитата: Поверонов от 15.11.2019 08:48:47криптостойкость шифров оценивается временем необходимом ( по мнению  оценщиков ) для их взлома на самых быстрых современных суперкомпьютерах. При этом время вычисляется по числу необходимых операций ( по мнению оценщиков ), так что если число необходимых операций вдруг оказывается на порядки меньше ( чем представлялось оценщикам ) то и криптостойкость падает на те же порядки.
В частности с появлением квантовых компьютеров сейчас пересматриваются криптостойкости всех шифров уже относительно них.
PS. Да паника была напрасной - конструктивного алгоритма построения такого полинома пока не обнаружили ( или не опубликовали Улыбающийся ), но потенциально такая возможность сохраняется и все криптостойкости пришлось пересматривать.
В частности DES превратился в 3DES

Если касательно полинома многих переменных то он преведен мною выше...Положительные значения  ограничения полинома на множество 26-ок натуральных чисел будут давать все множества простых чисел...Только вот по виду сразу видно что положительные числа будут крайне редки в море отрицательных чисел - поэтому с практической точки зрения это все тот же перебор (причем вероятно намного менее эффективный чем решето эратосфена). Многочлена принимающего только все множество простых чисел не существует, причем доказывается этот факт элементарно. 
  • +0.00 / 0
GrinF
 
Слушатель
Карма: +72.26
Регистрация: 15.02.2018
Сообщений: 6,177
Читатели: 3
Цитата: adolfus от 15.11.2019 09:05:13Что такое "конечный полином"?

Есть конечно порожденные кольца полиномов например К[x], K[x,y]...А бывают и бесконечно K[x,y,....], так что каждый представитель содержит только конечное число переменных...
  • +0.00 / 0
Senya
 
russia
55 лет
Слушатель
Карма: +322.33
Регистрация: 20.11.2008
Сообщений: 26,851
Читатели: 51

Глобальный Модератор
Цитата: Поверонов от 15.11.2019 08:48:47PS. Да паника была напрасной - конструктивного алгоритма построения такого полинома пока не обнаружили ( или не опубликовали Улыбающийся ), но потенциально такая возможность сохраняется и все криптостойкости пришлось пересматривать.
В частности DES превратился в 3DES

Ни малейшей связи. DES изначально обладал предельно коротким ключом в 56 бит. Дифференциальным криптоанализом определялся последний 16-битный подключ, после чего оставшиеся 40 бит находились перебором. Поэтому стойкость DES считалась 2^40, что слишком мало (ну и известно задолго до того, как слова такие изобрели, как "квантовый компьютер").. Утроение в режиме шифрование-расшифрование-шифрование было сделано с одной стороны чтобы избежать атак типа "встреча посередине", а с другой чтобы на одном шифровальном устройстве выполнять как одинарное, так и тройное шифрование в зависимости от абонента. В первом случае просто все три ключа задаются одинаковыми.
"Иван Грозный помещает на рабочий стол полученный от хана ярлык."(с) Не моё.
  • +0.08 / 5
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: aeroplane от 13.11.2019 10:52:47Историю с коментарием "Леха, леха ты могуч" в коде MS-Words не помним.
Поинтересуйтесь, кто написал Лисп для Автокадов и ВижуалЛисп для нынешних Автокадов. Правильно - его зовут Петр Петров.

С автокадом знаком. В 1991 г. на фабрике специально конструкторам купили дв компа с i386+387 на борту и +8М в сиппах (планки с одним рядом штырьков). Я лично на них устанавливл официальную 10-ую версию вместе с автошейдом и автолиспом.

Лирическое отступление
Вот что-то я не помню, чтобы в мануале на автолисп слово "Петров" хоть где-то встретилось. Я думаю, что если этот Петров и принимал какое-то участие, то он к России никакого отношения не имел. Собственно, до лета 1993 года, до замены советских денег на российские никакой России не было и никаких российских программистов тоже. Это раз.
А вот два поинтересноее. Петров это получил образование в СССР, потому он не может считаться российским программистом. Возможно, русский, как и Боширов. Вот, например, Ю.А. Гагарин – ни разу не Российский, но русский.
Цитата: aeroplane от 13.11.2019 10:52:47Любой иностранный САПР без участия российских программистов.

Не знаю ни одного иностранного САПРа, в разработке которого бы официально принимали участие компании с чисто российской юрисдикцией.
Например, берем Siemenx NX, якобы в ядре которого имеется российское участие, и фильтруем софт через strings. Да нет там даже следа российского.
  • -0.08 / 3
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: aeroplane от 13.11.2019 12:24:40Линейное программирование? Не-а, не слышали.

У меня этого линейного программирования в аспирантуре целый курс был. Назывался, ЕМНИП, "Методы оптимизации". От программирования там только слово "программирование". Давайте таки отделять дискретную математику, так любимую многими, от реального практического производства программных средств и обеспечения.
  • +0.00 / 0
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: Senya от 15.11.2019 13:27:10Ни малейшей связи. DES изначально обладал предельно коротким ключом в 56 бит. Дифференциальным криптоанализом определялся последний 16-битный подключ, после чего оставшиеся 40 бит находились перебором. Поэтому стойкость DES считалась 2^40, что слишком мало (ну и известно задолго до того, как слова такие изобрели, как "квантовый компьютер").. Утроение в режиме шифрование-расшифрование-шифрование было сделано с одной стороны чтобы избежать атак типа "встреча посередине", а с другой чтобы на одном шифровальном устройстве выполнять как одинарное, так и тройное шифрование в зависимости от абонента. В первом случае просто все три ключа задаются одинаковыми.

Одна из причин – утроение длины ключа. Специально на исследование того, является или не является DES групповой операцией, Г-деп выделил бабки и в 90-х любой поиск (altavicta. netscape и даже gofer) по слову DES только и выдавал, что "Is the DES a group?". Вот только была заковыка – в DES, похоже, нет бэкдора, поэтому Triple DES был быстро выпилен в пользу "более надежных шифров".
  • +0.03 / 1
Поверонов
 
Слушатель
Карма: +37.12
Регистрация: 05.06.2010
Сообщений: 18,863
Читатели: 7
Цитата: Senya от 15.11.2019 13:27:10Ни малейшей связи. DES изначально обладал предельно коротким ключом в 56 бит. Дифференциальным криптоанализом определялся последний 16-битный подключ, после чего оставшиеся 40 бит находились перебором. Поэтому стойкость DES считалась 2^40, что слишком мало (ну и известно задолго до того, как слова такие изобрели, как "квантовый компьютер").. Утроение в режиме шифрование-расшифрование-шифрование было сделано с одной стороны чтобы избежать атак типа "встреча посередине", а с другой чтобы на одном шифровальном устройстве выполнять как одинарное, так и тройное шифрование в зависимости от абонента. В первом случае просто все три ключа задаются одинаковыми.

Да конечно 3DES был введен лет 30 назад когда о квантовых компьютерах только фантасты писали. Упомянул как иллюстрацию того что с ростом быстродействия процессоров приходится пересматривать шифры. 
  • +0.00 / 0
adolfus
 
Слушатель
Карма: +21.87
Регистрация: 12.02.2010
Сообщений: 11,201
Читатели: 2
Цитата: Поверонов от 15.11.2019 21:37:20Да конечно 3DES был введен лет 30 назад когда о квантовых компьютерах только фантасты писали. Упомянул как иллюстрацию того что с ростом быстродействия процессоров приходится пересматривать шифры.

В крипроанализе есть мнение (шутошное, скорее), что нет смыла прямо сейчас брут-форсить шифртекст, поскольку производительность криптоаналитических средств растет гораздо быстрее, чем линейно, поэтому, если начать процесс попозже, но с помощью более продвинутых средств, результат можно получить раньше. 
  • +0.00 / 0
GrinF
 
Слушатель
Карма: +72.26
Регистрация: 15.02.2018
Сообщений: 6,177
Читатели: 3
Цитата: adolfus от 15.11.2019 22:08:43В крипроанализе есть мнение (шутошное, скорее), что нет смыла прямо сейчас брут-форсить шифртекст, поскольку производительность криптоаналитических средств растет гораздо быстрее, чем линейно, поэтому, если начать процесс попозже, но с помощью более продвинутых средств, результат можно получить раньше.

Что-то это мнение похоже на очередную городскую легенду... Оно конечн  есть RSA взлавыемый  в теории квантовым компом.. но при приближении к практике оказывается что достичь такое разрешение по фазе фурье-преобразования на современном и перспективном железе не возможно...На афтершоке правда встречал уникума символа который мне на голубом глазу доказывал шо достаточно 100 аудит что бы взломать клбюч на 1024кубита...правда алгоритм не привел, исключительно свой рейтинг оказывал...так шо все кто пользуется RSA, DSA и не экономит на генерации ключей могут спать спокойно
  • +0.00 / 0
Senya
 
russia
55 лет
Слушатель
Карма: +322.33
Регистрация: 20.11.2008
Сообщений: 26,851
Читатели: 51

Глобальный Модератор
Цитата: adolfus от 15.11.2019 21:35:08Вот только была заковыка – в DES, похоже, нет бэкдора, поэтому Triple DES был быстро выпилен в пользу "более надежных шифров".

Изобретение надёжного симметричного шифра с бэкдором (за исключением по слухам практикуемых ограничений пространства ключей в некоторых изделиях) произвело бы в криптографии переворот, сравнимый с изобретением дифференциального исчисления в математике. Все до сих пор продемонстрированные уязвимости относятся к дефектам проектирования. Причем для конторы любого уровня эти ошибки могут быть детсадовскими, как в штатовских SHA, которую пришлось срочно допиливать до SHA-1 из за банального недосмотра.
"Иван Грозный помещает на рабочий стол полученный от хана ярлык."(с) Не моё.
  • +0.13 / 10
Senya
 
russia
55 лет
Слушатель
Карма: +322.33
Регистрация: 20.11.2008
Сообщений: 26,851
Читатели: 51

Глобальный Модератор
Цитата: Поверонов от 15.11.2019 21:37:20с ростом быстродействия процессоров приходится пересматривать шифры.

Приходилось. Ни 2^128, ни даже 2^112 не станут доступны для перебора.
"Иван Грозный помещает на рабочий стол полученный от хана ярлык."(с) Не моё.
  • +0.08 / 6
aeroplane
 
russia
52 года
Слушатель
Карма: +4.50
Регистрация: 06.02.2010
Сообщений: 2,369
Читатели: 0
Цитата: adolfus от 15.11.2019 20:27:21С автокадом знаком. В 1991 г. на фабрике специально конструкторам купили дв компа с i386+387 на борту и +8М в сиппах (планки с одним рядом штырьков). Я лично на них устанавливл официальную 10-ую версию вместе с автошейдом и автолиспом.
Лирическое отступление
Вот что-то я не помню, чтобы в мануале на автолисп слово "Петров" хоть где-то встретилось. Я думаю, что если этот Петров и принимал какое-то участие, то он к России никакого отношения не имел.


Зато Петр Петров работал в "слегка" закрытом НИИ по созданию САПРа для весьма специфического машиностроения.
В 89-м на территории АЗЛК познакомился с тогдашним Автокадом. И все заверте....

Цитата: adolfus от 15.11.2019 20:27:21Собственно, до лета 1993 года, до замены советских денег на российские никакой России не было и никаких российских программистов тоже. Это раз.


Россия правоприемница СССР, соответственно советские программисты стали российскими.

Цитата: adolfus от 15.11.2019 20:27:21А вот два поинтересноее. Петров это получил образование в СССР, потому он не может считаться российским программистом. Возможно, русский, как и Боширов. Вот, например, Ю.А. Гагарин – ни разу не Российский, но русский.




Цитата: adolfus от 15.11.2019 20:27:21Не знаю ни одного иностранного САПРа, в разработке которого бы официально принимали участие компании с чисто российской юрисдикцией.


Берем фирму "Ледас" (Новосибирск), и смотрим кто юзает ее разработки.
Конечно, американские фирмы, участие российских (советских) программистов скрывают путем покупки авторских
прав на разработки и потом пишут, что авторские права на модуль ХХХ приналежат фирме такой-то, а об разработчиках ни слова.

Цитата: adolfus от 15.11.2019 20:27:21Например, берем Siemenx NX, якобы в ядре которого имеется российское участие, и фильтруем софт через strings. Да нет там даже следа российского.

А как strings  отнесется к тексту - "Debily, b..." - правильно, скажет, что это чисто английское выражение.Улыбающийся
  • +0.09 / 4
aeroplane
 
russia
52 года
Слушатель
Карма: +4.50
Регистрация: 06.02.2010
Сообщений: 2,369
Читатели: 0
Цитата: GrinF от 14.11.2019 14:50:10а теперь камерад Очевидность не нарисуете на бис точно такую же формулу (при чем эффективно вычислимую - то есть с небольшой пространственной сложностью) для простых чисел? А то мы тут томимся...

Формулы у меня нет, но есть алгоритм - сложность которого возрастает в SQRT(O) раз. Лет так 20 назад написал.
Правда кассеты с той программой уже давно нет.  Разрядности Спектрума к сожалению хватало на полтора часа работы,
потом наступало переполнения разрядности. 
  • +0.00 / 0
Slav Rus
 
russia
Самара
62 года
Слушатель
Карма: +1,031.88
Регистрация: 25.01.2016
Сообщений: 9,253
Читатели: 15

Модератор раздела

18.11.2019
Один из самых титулованных программистов планеты, аспирант ИТМО Геннадий Короткевич выиграл соревнования программистов Topcoder Open 2019, которые ежегодно проводятся в Хьюстоне. Об этом в понедельник, 18 ноября, сообщили «Фонтанке» в ИТМО.

Короткевич впервые в истории чемпионата, где соревнуются профессионалы по разработке и дизайну со всего мира, выиграл сразу в двух из шести направлений соревнований – Algorithm и Marathon.

До очной схватки лучших из лучших в Хьюстоне участники соревнований прошли онлайн-этапы. 

Особенностью трека Marathon, где Короткевич около 10 часов бился с 11 сильнейшими программистами мира, является решение задач, ответы на которые не знает никто.
«Программисты должны решить оптимизационные задачи. В каждом раунде дается одна задача, правильное решение которой неизвестно даже ее автору. Участнику предстоит написать программу, находящую наиболее эффективный ответ за отведенное время», – уточнили в пресс-службе ИТМО.

В треке Algorithm участники мерялись силами в «классическом» спортивном программировании, используя языки Java, C#, C++ или Python. Эта битва, выигранная Короткевичем, длилась полтора часа.
«Гена у нас человек уникальный! Большая победа. Никто и никогда не выигрывал сразу два трека этого чемпионата. Красного угла с его портетом у нас в ИТМО пока нет, но мы его поздравляем тепло внутри коллектива», – рассказали в пресс-службе этой кузницы лучших программистов мира.

Помимо объятий коллег Геннадий Короткевич получил по 10 000 долларов за победу в каждом из двух треков Topcoder Open.

25-летний аспирант Университета ИТМО является двукратным победителем чемпионата мира по программированию ICPC. Впервые он стал триумфатором в 19 лет в 2013 году, а затем в 2015 году в составе «команды чемпионов ИТМО». В 2014 году Короткевич стал победителем ЧМ по программированию, собрав первенство во всех номинациях так называемого «большого программного шлема». В 2015 году студент ИТМО выиграл чемпионат по программированию Google. В октябре 2019 года  петербуржец в третий раз победил на Facebook Hacker Cup.

https://www.fontanka.ru/2019/11/18/062/
Мы смеялись в глаза врагу… Хоть нас было всего двадцать восемь

Делай, что должно, и будь что будет.
  • +0.14 / 9
GrinF
 
Слушатель
Карма: +72.26
Регистрация: 15.02.2018
Сообщений: 6,177
Читатели: 3
Цитата: aeroplane от 18.11.2019 15:36:43Формулы у меня нет, но есть алгоритм - сложность которого возрастает в SQRT(O) раз. Лет так 20 назад написал.
Правда кассеты с той программой уже давно нет.  Разрядности Спектрума к сожалению хватало на полтора часа работы,
потом наступало переполнения разрядности.

что бы это значило? Не поясните... Обычно временная сложность меряется как некоторая функция от длины строки представляющих данные... То есть если длина ввода  l  бит - то алгоритм сложности O(l^n)  - означаете что сложность растет как некоторая степень длины...Таковые например алгоритмы умножения матриц или алгоритм Евклида... А если сложность О(2^l) - то алгоритм переборный.  Из гипотезы Римана известно, что количество простых чисел меньших N имеет асимптотику  p(N)= N/logN... Если N длину l то количество простых чисел ~O(2^l/l)... Теперя пошли далее ...Там выше упоминался  детерминированный тест на простоту Аргавала он имеет сложность O(l^8)... Если вы нашли тест O(l^0.5) - то вам надо бросать фигней здесь на форуме заниматься и отправлять анкеты во все спецслужбы, и все офисы всех крупнейших софтверных производителей... Так какаова же сложность вашего алгоритма ... приведенный мной полином  - как и любой другой следующий из доказательсва 10 проблемы гильберта  - является переборным (то есть временную сложность O(2^l)) и имеет линейную простраственную сложность (требования к памяти в зависимости от длины ввода)
  • +0.04 / 2
aeroplane
 
russia
52 года
Слушатель
Карма: +4.50
Регистрация: 06.02.2010
Сообщений: 2,369
Читатели: 0
Цитата: GrinF от 19.11.2019 00:41:37то вам надо бросать фигней здесь на форуме заниматься и отправлять анкеты во все спецслужбы, и все офисы всех крупнейших софтверных производителей...

Вы будете смеяться, но я был оператором формализованного ввода в одном богоугодном заведении. Строит глазки
  • +0.00 / 0
Сейчас на ветке: 4, Модераторов: 0, Пользователей: 0, Гостей: 2, Ботов: 2