Одед Регев (; ) — израильско-американский учёный, теоретик информатики и математик. Лауреат премии Гёделя. Профессор информатики в Курантовском институте при Нью-Йоркском университетеFaculty listing , Courant Institute of Mathematical Sciences, accessed 2019-06-25.. Наиболее известен своими работами в области решётчатой криптографии, в частности постановкой задачи обучения с ошибками (LWE), криптоанализом схем и NTRUSign, а также разработкой нового квантового алгоритма по факторизации чисел, превосходящего по эффективности алгоритм Шора.
Биография В 1995 году Одед Регев получил степень бакалавра наук. В 1997 году получил степень магистра наук и доктора философии. В 2001 году защитил докторскую диссертацию в Тель-Авивском университете на тему «Планирование и балансировка нагрузки», его научным руководителем был School of Computer Science Thesis Repository , Tel-Aviv University, accessed 2019-06-25.https://www.aftau.org/2013-redesign/pages/tau/spotlights/blavatnik-school-of-computer-science#alumniSay. http://primage.tau.ac.il/libraries/theses/exeng/free/1509397_abe.pdf. . До перехода в Курантовский институт, в котором он работает сейчас, Одед преподавал в Тель-Авивском университете и Высшей нормальной школе Парижа.
Научная работа Регев проделал обширную работу в теории решёток и криптографии. Стал известен после постановки задачи обучения с ошибками (), за которую получил премию Гёделя.
Работа Регева положила начало революции в криптографии, как в теории, так и на практике. С теоретической точки зрения LWE послужил простой и в то же время универсальной основой практически для любого типа криптографических объектов, которые только можно вообразить, а также для многих из них, которые до недавнего времени были немыслимы и которые до сих пор не имеют известных конструкций без LWE. С практической точки зрения LWE и его прямые потомки лежат в основе нескольких эффективных реальных криптосистем.
Другими влиятельными работами Регева являются криптоанализ схем и NTRUSign в совместной работе с Фонгом К. Нгуеном, за которые они получили награду на Eurocrypt в 2006 году, а также постановка проблемы кольцевого обучения с ошибками для постквантовой криптографии в совместной работе с Крисом Пейкертом и Вадимом Любашевским и доказательство обратной теоремы Минковского о выпуклом теле и исследование её приложений в совместных работах со своим учеником Ноем Стивенсом-Давидовицем и его бывшим постдоком Дэниелом Дадушем.
Помимо работ по криптографии, Регев также внёс вклад во многие другие области теоретической информатики и математики, такие как квантовые вычисления, коммуникационная сложность, сложность аппроксимации, , комбинаторика, теория вероятностей и снижение размерности. Недавно он также заинтересовался вопросами биологии, в частности сплайсингом РНК.
Регев — заместитель главного редактора журнала «Теория вычислений», а также соучредитель и организатор серии онлайн-семинаров TCS+List of editors , Theory of Computing, accessed 2019-06-25..
Алгоритм Регева В августе 2023 года Регев опубликовал новый квантовый алгоритм по факторизации чисел, превосходящий по эффективности алгоритм Шора.
Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией. Ему удалось обобщить алгоритм на произвольное количество измерений, а не только на два, в результате чего для факторизации чисел квантовому компьютеру требуется гораздо меньше логических шагов. Специалисты по квантовыми вычислениями отмечают, что удивительно и неожиданно, что спустя 30 лет кто-то смог качественно улучшить алгоритм Шора.
Алгоритм Регева использует квантовых вентилей, что более эффективно, чем в алгоритме Шора, в котором используется квантовых вентилей, хотя для реализации алгоритма Регева потребуется больше кубитов квантовой памяти , в то время как в алгоритме Шора их используется .
Позже был предложен вариант оптимизации алгоритма Регева, в котором было показано, что можно уменьшить пространство используемой квантовой памяти примерно до того же уровня, что и в алгоритме Шора.
Награды и премии Премия Криля (2005)http://www.wolffund.org.il/index.php?dir=site&page=winners&cs=565 Премия Eurocrypt (2006) Премия Гёделя (2018) (2019) Серебряный профессор (2022)
Примечания
Ссылки Сайт Регева .
Категория:Учёные в области информатики Израиля Категория:Математики Израиля Категория:Криптографы Израиля Категория:Сильверовские профессора Категория:Преподаватели Нью-Йоркского университета Категория:Выпускники Тель-Авивского университета Категория:Лауреаты премии Гёделя Категория:Simons Investigators Категория:Математики США