Loading AI tools
Из Википедии, свободной энциклопедии
Одед Регев (ивр. עודד רגב ; род. 1978) — израильско-американский учёный, теоретик информатики и математик. Лауреат премии Гёделя. Профессор информатики в Курантовском институте при Нью-Йоркском университете[2]. Наиболее известен своими работами в области решётчатой криптографии, в частности постановкой задачи обучения с ошибками (LWE), криптоанализом схем GGH[англ.] и NTRUSign, а также разработкой нового квантового алгоритма по факторизации чисел, превосходящего по эффективности алгоритм Шора .
Одед Регев | |
---|---|
Дата рождения | 1978 |
Род деятельности | математик |
Место работы | |
Альма-матер | |
Научный руководитель | Йоси Азар[нем.] |
Награды и премии |
В 1995 году Одед Регев получил степень бакалавра наук. В 1997 году получил степень магистра наук и доктора философии. В 2001 году защитил докторскую диссертацию в Тель-Авивском университете на тему «Планирование и балансировка нагрузки», его научным руководителем был Йоси Азар[нем.][3][4][5]. До перехода в Курантовский институт, в котором он работает сейчас, Одед преподавал в Тель-Авивском университете и Высшей нормальной школе Парижа[6].
Регев проделал обширную работу в теории решёток и криптографии. Стал известен после постановки задачи обучения с ошибками (англ. Learning with errors, LWE), за которую получил премию Гёделя[7].
Работа Регева положила начало революции в криптографии, как в теории, так и на практике. С теоретической точки зрения LWE послужил простой и в то же время универсальной основой практически для любого типа криптографических объектов, которые только можно вообразить, а также для многих из них, которые до недавнего времени были немыслимы и которые до сих пор не имеют известных конструкций без LWE. С практической точки зрения LWE и его прямые потомки лежат в основе нескольких эффективных реальных криптосистем.
Другими влиятельными работами Регева являются криптоанализ схем GGH[англ.] и NTRUSign в совместной работе с Фонгом К. Нгуеном, за которые они получили награду на Eurocrypt в 2006 году, а также постановка проблемы кольцевого обучения с ошибками[англ.] для постквантовой криптографии в совместной работе с Крисом Пейкертом и Вадимом Любашевским и доказательство обратной теоремы Минковского о выпуклом теле и исследование её приложений в совместных работах со своим учеником Ноем Стивенсом-Давидовицем и его бывшим постдоком Дэниелом Дадушем[8][9][10][11][12].
Помимо работ по криптографии, Регев также внёс вклад во многие другие области теоретической информатики и математики, такие как квантовые вычисления, коммуникационная сложность, сложность аппроксимации, онлайн-алгоритмы[англ.], комбинаторика, теория вероятностей и снижение размерности. Недавно он также заинтересовался вопросами биологии, в частности сплайсингом РНК[13][14].
Регев — заместитель главного редактора журнала «Теория вычислений», а также соучредитель и организатор серии онлайн-семинаров TCS+[15][16].
В августе 2023 года Регев опубликовал новый квантовый алгоритм по факторизации чисел, превосходящий по эффективности алгоритм Шора[17][18][19].
Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией. Ему удалось обобщить алгоритм на произвольное количество измерений, а не только на два, в результате чего для факторизации чисел квантовому компьютеру требуется гораздо меньше логических шагов. Специалисты по квантовыми вычислениями отмечают, что удивительно и неожиданно, что спустя 30 лет кто-то смог качественно улучшить алгоритм Шора[17][18][19].
Алгоритм Регева использует квантовых вентилей, что более эффективно, чем в алгоритме Шора, в котором используется квантовых вентилей, хотя для реализации алгоритма Регева требуется потребуется больше кубитов квантовой памяти , в то время как а алгоритме Шора их используется .
Позже был предложен вариант оптимизации алгоритма Регева, в котором было показано, что можно уменьшить пространство используемой квантовой памяти примерно до того же уровня, что и в алгоритме Шора[20].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.