Специально для d_integral и 2born решил перевести на русский язык статью Скотта Ааронсона Shor, I’ll do it, в которой он буквально на пальцах объясняет алгоритм Шора для быстрого нахождения простых множителей с помощью квантового компьютера. Там все основано на модулярной арифметике) Итак:
Шор, дай я попробую!
Скотт Ааронсон
В последнее время я много рассказывал о том, как квантовые алгоритмы не могут работать. Но на прошлой неделе J.R. Minkel, редактор Scientific American, попросил меня написать короткий рассказ о том, как же они тогда работают? — чтобы он мог повесить на сайте SciAm ссылочку. «Хорошо!» — ответил я, моментально забыв о ликбезов по квантовым алгоритмам, которые уже есть в сети. Итак, я поставил себе следующую задачу: объяснить алгоритм Шора, не используя ни единой треугольной скобочки, да и вообще ничего сложнее простой арифметики.
Хорошо, положим, что вы хотите взломать криптосистему RSA, чтобы ограбить парочку банков, прочитать почту своей бывшей, да мало ли для чего еще. Мы все знаем, что взлом RSA сводится в конечном итоге к нахождению множителей большого числа N. К сожалению, мы также знаем, что «попробовать все возможные множители одновременно», а затем выбрать нужный, не получится. Что бы ни говорила сотня популярных журналов, но квантовые компьютеры так не работают. Конечно, вы можете с их помощью «попробовать все возможные множители одновременно» — но когда вы измерите результат, вы получите случайный множитель, который скорее всего будет не тем, который нужен.
Почему ШОРА нет в Совнгарде — все теории | TES лор
Другими словами, если мы хотим получить быстрый алгоритм разложения на множители, мы должны обнаружить некоторую структуру, скрытую в этой задаче, некоторое математическое свойство, которое выделяет данную задачу из класса «поиск иголки в стоге сена».
К счастью, проблема разложения на множители имеет уйму особенностей. Вот одна из них: если я назову вам положительное целое число, вы можете не знать, как оно раскладывавается на простые множители, но вы можете быть уверены: это разложение единственно!
Для сравнения: если я дам вам Судоку и попрошу решить, а приори вы не будете знать, есть ли у него в точности одно решение, или 200 миллионов, или Wowсе не одного. Конечно, знание, что иголка в стоге сена строго одна, не сильно поможет нам в ее поиске! Но эта единственность — подсказка, что в проблеме поиска множителей могут быть другие приятные математические особенности, только подходи и бери! Оказывается, так оно и есть.
Мы будем использовать то свойство, что задачу разложения на множители можно свести к другой задаче, поиску периода. Самое время сделать небольшое лирическое отступление и кратко рассказать о теории чисел. Давайте рассмотрим мою любимую с 5 лет последовательность целых чисел, степени двойки.
Теперь взглянем на степени двойки «по модулю 15» (mod 15), другими словами, остаток от деления на 15 от каждого из приведенных выше чисел.
Лорхан, Пропавший Бог | TES Лор [AshKing]
2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …
Как видите, степени двойки по модулю 15 представляют собой периодическую последовательность, с периодом (т.е сколько чисел надо пройти, прежде чем она начнет повторяться), равным 4. Другой пример: возьмем степени двойки по модулю 21:
В этот раз мы получили последовательность с периодом 6.
Вы можете спросить: существует ли общее правило, способное предсказать этот период? Вдруг математики хоть что-нибудь придумали по этому поводу?
Еще как придумали — есть красивая закономерность, обнаруженная Эйлером в 1760-х. Пусть N будет произведением двух простых чисел, p и q, и рассмотрим последовательность
x mod N, x 2 mod N, x 3 mod N, x 4 mod N, .
Тогда, если x не делится ни на p, ни на q, данная последовательность будет иметь период, который делит нацело число (p-1)(q-1).
Например, если N=15, то его простые множители p=3 и q=5, значит, (p-1)(q-1)=8. И действительно, период последовательности был равен 4, что делит 8 нацело. Если N=21, то p=3 и q=7, и (p-1)(q-1)=12. Все верно: период был равен 6, что делит 12 нацело.
Теперь давайте сделаем шаг назад и подумаем, что все это значит. А значит это, что если бы мы смогли найти период последовательности
x mod N, x 2 mod N, x 3 mod N, x 4 mod N, .
то мы узнали бы кое-что о простых множителях числа N! Конкретнее, мы узнали бы делитель (p-1)(q-1). Да, это не так здорово, как узнать p и q непосредственно, но это уже кое-что. Даже больше, чем кое-что. Оказывается, мы можем узнать несколько делителей числа (p-1)(q-1), пробуя разные случайные значения x, после чего с высокой долей вероятности мы узнаем и само значение (p-1)(q-1). А зная его и проделав еще пару трюков, мы найдем сами p и q, нужные нам простые множители.
Так в чем же ложка дегтя? Ну, хотя последовательность
x mod N, x 2 mod N, x 3 mod N, x 4 mod N, .
и начнет однажды повторяться, но число шагов может быть столь же большим, как и само число N — а оно может иметь сотни и тысячи разрядов! Поэтому нахождение периода не приводит к быстрому классическому методу факторизации.
Ага, но ведь у нас есть квантовый компьютер! (Или, по крайней мере, представим, что он у нас есть.) Тогда появляется надежда. В частности, мы могли бы сделать мощнейшую квантовую супепозицию всех чисел нашей последовательности: x mod N, x 2 mod N, x 3 mod N и т.д. Тогда, может, найдется такая квантовая операция, которая найдет ее период.
Ключевой момент здесь в том, что мы больше не должны найти иголку в экспоненциально-большом стоге сена, что, как мы уже знаем, очень сложно даже для квантового компьютера. Вместо этого, мы пытаемся найти период последовательности, что есть глобальное свойство всех членов этой последовательности, вместе взятых. А это большая разница.
Смотрите: если мы взглянем на квантовые вычисления в терминах «параллельных вселенных» (а принимать ли такую точку зрения — выбор за вами), нет никакой возможности заметить одну-единственную вселенную, отличную от остальных. Такой глас вопиющего в пустыне будет заглушен мощным хором живущих неподалеку, одевающих брюки Dockers, вселенных-конформистов. Однако, мы вполне можем обнаружить общее свойство всех вселенных, вместе взятых, свойство, которое появится как результат параллельных вычислений всех участвующих вселенных.
(Заметка: для вашей же безопасности, не пытайтесь объяснить вышеизложенное популярным писателям из школы «квантовые вычисления = бесконечное распараллеливание». Они могут сдуться, как вампиры на солнечном свете)
Итак, задача Wowсе не безнадежна! Но прежде чем идея с нахождением периода заработает, нужно ответить на 2 вопроса:
1. Можно ли с помощью квантового компьютера быстро создать суперпозицию из x mod N, x 2 mod N, x 3 mod N и т.д?
2. Допустим, такая суперпозиция у нас получилась, а как же теперь узнать период?
Разберемся сначала с первым вопросом. Мы определенно можем сделать суперпозицию из всех целых чисел r, от 1 до N. Но можно ли, при данном r, быстро сосчитать x r mod N? Если r равно, скажем, 300 квадриллионам, то неужто придется помножать x на себя все 300 квадриллионов раз? Это было бы слишком медленно, и, к счастью, не требуется. Вместо этого мы можем проделать операцию под названием «повторное возведение в квадрат». Проше всего показать на примере.
Допустим, N=17, x=3 и r=14. Первый шаг — представить r как сумму степеней двойки:
Нам достаточно возводить x в квадрат, результат снова в квадрат, и еще, и еще, а потом нужные степени перемножить.
Заметим также, что все вычисления можно делать по модулю N, что позволит числам оставаться маленькими на промежуточных шагах. Получаем результат:
Хорошо, мы умеем создавать квантовую суперпозицию всех пар целых чисел (r, x r mod N), где r меняется от 1 до N. Осталось понять, как из этой суперпозиции вычленить период последовательности?
Вот мы и приходим к сути вопроса, к той части алгоритма Шора, которая целиком основана на квантовой механике. Чтобы узнать период последовательности, Шор использует штуку под названием квантовое преобразование Фурье, или QFT (Quantum Fourier Transform). Моя задача — объяснить вам QFT, не используя никакой математики. Хм.
Попробую так. Как у многих ученых-компьютерщиков, у меня есть очень странные часы. Знаете этот известный эксперимент, когда люди неделями сидели в закрытом помещении без смены дня и ночи, и в итоге переходили с цикла в 24 часа на 25-, 26- или 28-часовой день? Для меня это нормальная жизнь. Сегодня я встану в 9 утра, завтра в 11, после завтра в час дня, и так далее. Так и буду ходить по кругу, если только не помешают занятия или назначенные встречи. (Я все время так жил в Беркли.)
Вот мой вопрос. Я сказал вам, что сегодня проснулся в 5 часов вечера. Можете ли вы узнать из одного только этого факта, насколько длинный мой «день»: 25 часов, 26.3 часа или еще какой-то?
Ответ: не особенно. Можно смело предположить, что я живу не по нормальному 24-часовому циклу, иначе я бы просыпался утром, а не в 5 вечера. Но любой другой период — 25 часов, 26 часов, 28 часов — любой из них заставит мой режим плавать по суткам, так что не будет ничего удивительного увидеть меня просыпающимся в 5 вечера в какой-то конкретный день.
Теперь я попрошу вас представить, что моя комната уставлена стрелочными часами. Это очень странные часы: у одних стрелка совершает оборот за 17 часов, у других — за 26 часов, у третьих — за 24.7 часа, и таких разных часов очень много. (Для простоты, считаем, что у них есть только часовая стрелка.) И еще под каждыми часами висит картонка, а в нее воткнута канцелярская кнопка. Когда я только въехал, каждая кнопка располагалась ровно посередине картонки. Но каждый день, когда я просыпался, я первым делом двигал каждую кнопку на один сантиметр в том направлении, куда в этот момент указывала стрелка соответствующих часов.
Новый вопрос: сможете ли вы, глядя на мои канцелярские кнопки, выяснить продолжительность моего «дня»?
Я утвердаю, что это возможно. Предположим, что я живу по 26-часовому распорядку. Что произойдет с кнопкой под 24-часовыми часами? Нетрудно видеть, что она будет совершать периодическое движение: конечно, она чуть-чуть будет смещаться, но через каждые 12 дней она будет возвращаться ровно на середину поля, оттуда, откуда и начинала. Одно утро я сдвину ее вправо, во второе — вправо и вверх, в следующий раз — вверх, и так далее, и в конце концов различные сдвиги погасят друг друга.
С другой стороны — снова считая, что я живу по 26-часовому распорядку — а что произойдет с кнопкой под 26-часовыми часами? Ответ будет другим, ведь по этим часам я буду просыпаться всегда в одно и то же время! Они будут смотреть в одну сторону, поэтому я буду двигать кнопку все дальше и дальше от центра, пока она вообще не дойдет до края!
Выходит, что просто взглянув, какая из кнопок ушла дальше других от центра, вы можете узнать, по какому распорядку я живу. Т.е вы можете узнать «период» моей жизни.
И это, в общих чертах, и есть квантовое преобразование Фурье. Более строго, QFT — это линейное преобразование (а еще точнее: унитарное), отображающее один вектор комплексных чисел на другой вектор комплексных чисел. Во входном векторе каждое ненулевое число соответствует времени, когда я просыпаюсь, нули во все остальные моменты. Выходной вектор — это положения всех кнопок под моими часами (о которых можно говорить как о точках на комплексной плоскости). В итоге мы получаем линейное преобразование, которое из квантового состояния, кодирующего периодическую последовательность, получает квантовое состояние, выражающее период этой последовательности.
Можно думать обо всем этом в терминах интерференции. Я имею в виду, что ключевой момент квантовой механики, та вещь, что делает ее столь отличной от классической теории вероятности — что если обычные вероятности всегда положительны, то амплитуды в квантовой механике могут быть положительными, отрицательными и даже комплексными. И поэтому, амплитуды получения того или иного ответа могут «интерферировать деструктивно» и подавить друг друга.
Именно это и происходит в алгоритме Шора. Каждая «параллельная вселенная», соответствующая элементу последовательности, вносит свой вклад в амплитуду каждой «параллельной вселенной», соответствующей каждому возможному периоду последовательности. Уловка в том, что для всех периодов, кроме истинного, эти вклады будут указывать в разную сторону и в конце концов вычтут друг друга. Только амплитуды для «правильного» периода сложатся синфазно, т.е будут смотреть в одном направлении. И ровно поэтому, проведя измерения, мы получим правильный ответ с высокой вероятностью.
Конечно, я многое упустил в своем рассказе, вот здесь, здесь или здесь, или здесь, или здесь, или здесь, а также здесь, здесь, здесь, здесь, здесь и еще здесь вы можете найти подробности.
Источник: nabbla1.livejournal.com
Локир из Рорикстеда, не простой вор. Теория
Скоро выйдет дополнение к TESO — Skyrim, которое завершит драконий цикл Эльсвейра. А я обожаю эту часть из-за её атмосферы, и красивой, знакомой, природы. Поэтому решил перечитать и передумать пару теорий и предположений, которые могут там воплотиться. И то, что там точно может быть, это раскрытие тайны Рорикстеда. Одна из этих явных тайн — Локир.
Казалось бы, что это всего лишь случайный попутчик на казнь, о котором сразу же все забывают после того, как тот неудачливо пытался сбежать. Так совпало, что Довакин и Локир попали в ту повозку случайно. Их не должно было там быть — Как сказал сам Локир. Просто совпадение.
Вот только его жертва спасла жизнь Довакину. Не будь его, Довакина казнили бы до того, как прилетел Алдуин, и сорвал казнь. Причем, все действо действительно занимало всего пару мгновений, которые он ему выиграл. Просто ещё одно совпадение.
Локир говорит, что он из Рорикстеда. Но никто в Рорикстеде его не знает. Сам Рорикстед довольно странное место, которое стояло там ещё со второй эры, по информации из TESO. А так, считается, что оно там было чуть ли не в Мерическую эру.
Но тема не о деревне со странным культом убивающем беременных женщин ради плодородной земли, и стоящее там с древнейших времен и основано мужчиной, который давно уже должен был исчезнуть из-за старости, а о Локире. О Рорикстеде, вероятно, мы узнаем из предстоящего дополнения про Скайрим в TESO.
На реддите было предположение, что Локир являлся мужем Лунда, который умер в своей хижине заполненной злокрысами. Теория основывалась на том, что там только мужская одежда, злокрысы местный аналог кошек, и что Локир оставил свое кольцо, отравил Лунда, чтобы его душа не попала к даэдра в ритуале Рорикстеда, украл лошадь из имперского лагеря и сбежал. И что он забирает своё кольцо и шапку, если Довакин зайдет в дом Лунда и выйдет из него, так как у алтаря уже не будет кольца и шапки, а значит, Локир остался жив, и забрал своё добро.
Я проверил алтарь с кольцом. Кольцо все ещё на месте, так что вероятно, это был просто баг у написавшего статью, так как алтарь очень нестабильный, и стоит к нему близко подойти, цветочки и шапочка, которые лежат на алтаре, провалятся под него, а их довольно тяжело заметить. А сам Лунд, по словам с реддита, связан с квестом Солтхейма, и там можно узнать, что его возлюбленная поехала с ним в Скайрим, но из-за чего-то сошла с ума и умерла. Но я это не проверял, поэтому, утверждать что это правда, не могу.
Вероятно, Локир действительно жил какое-то время с Лундом, а после сбежал украв коня из имперского лагеря рядом, но все это основывается на методах исключения. Ведь Локир никогда не говорил что он украл коня. Он сказал — «Если бы не вы, я бы украл коня и рванул в Хаммерфелл.»
А теперь о паре фактов о Локире, которые не являются противоречивыми.
— О Локире в Рорикстеде никто не знает, а сам город очень странный, ибо не попадает во временные рамки, в нём творятся странные вещи, а данные о нём слишком противоречивы. Хотя это обычный маленький городок, с невероятно плодородной землей и другими странностями.
— Локир бежит в Хаммерфелл, примерно там будут происходить события 6 части.
— Локир упоминает Шора, нордский аналог Лорхана, в молитве. Он вообще единственный, кто поминает Шора в Скайриме. Да, вероятно он просто перечислял всех богов. Но почему он не вспомнил даэдра, или Талоса, а молитва началась именно с Шора, и перешла через всех богов, кто был с ним близко связан? Это странно, особенно для простого норда.
Да, считается, что Совнгард создан Шором, и Локир, вероятно, хотел туда попасть. Но в Скайриме все волнуются о Талосе, а о Шоре даже не вспоминают.
Мара, Дибелла и Кинарет считаются женами Шора, и отвечают за жизнь и любовь. А Акатош, главное божество пантеона и времени, вырвавший сердце Лорхана, последний. Ведь это Шор-Лорхан никогда не был частью основного пантеона богов Империи. И Шор и Акатош называются царями богов, Шор в начале, Акатош после того, как тот вырвал сердце Лорхана, который обманул богов, в конце. А также, Акатош дарует благословение, которое известно как драконорождённость.
— Имя Локир (Lokir) имеет любопытное происхождение с драконьего языка —
Его имя состоит из двух драконьих слова, Обманывать и Дети. Что я могу интерпретировать как Обманщик детей. И это самый любопытный момент, который подчеркивает все ранее известное. Именно Шора считают и обманщиком, в пантеоне меров, и «богом детей», в пантеоне людей. Именно поэтому, под детьми тут подразумеваются люди.
И даже интерпретация его имени как Обманщик детей, может означать именно то самое действие с Локиром.
Имя Локир созвучно со скандинавским Локи, богом обмана, на котором как раз и основывались при написании Шора.
Я проверил созвучные имена на драконьем языке, чтобы не получилось какой ошибки. Получается только
Стало ещё более жутко, так как одно совпадение — совпадение, два — случайность, а три — уже закономерность. Локин — Небесный хозяин. Что также полностью подходит Локиру.
Рорикстед был выбран не случайно, вероятно в TESO — Skyrim раскроется связь с Шором, или неким культом благостных даэдра. Правда убийство людей вряд ли происходило в домах, так как там есть только белые камни душ, книги по даэдра, да черная мантия. Но для жертвоприношений людей нужны черные камни душ, а они даже у вампиров и магов редко когда встречаются. А в Рорикстеде их вообще не водится.
А ведь получается очень хитрый план, относительно Алдуина.
Шор бог, поэтому, очевидно, он может как-то прозревать время. А Совнгард его план. Он знал об Алдуине, и его гордыне, когда он назвал себя пожирателем мира, и решил пройти ритуал последования, ритуально пройдя по действиям Алдуина, чтобы самому стать Алдуином, как это сделала Азура с неизвестным заключенным, сделав его Нереварином, воплощением Неревара.
Как пример, на драконьем камне, из Ветренного пика написано — «Здесь покоятся наши владыки, пока Алдуин не воскресит их.» Что Алдуин и делал.
Если бы не Локир, то Довакина бы казнили. Но в самый последний момент явился Алдуин, сорвал казнь, и Довакин выжил, и когда он узнал об Довакине, это заставило его нервничать, он прорвался в Совнгард, дом Шора, где он начал поедать души, чтобы стать ещё сильнее и уничтожить Довакина, и никто из героев Совнгарда не мог его победить, кроме Довакина. Но победив, душа Алдуина улетела не к Довакину, а улетела в небо.
Я читал очень много теорий о том, что Довакин не настоящий, Алдуин не настоящий, что душа улетела к Акатошу, или к кому-то ещё. Но почему-то никому не приходило в голову самое очевидное. Душа ушла к Шору, ведь он владеет этим местом. Который накажет Алдуина за присвоение имени, и за его действия относительно мироздания.
А все случилось из-за одной маленькой и крайне незаметной детальки, которая настолько мелкая, что сразу же исчезла во всех остальных событиях, с остальными маловажными персонажами. Обман людей действительно получился отличный.
Источник: se7en.ws
Шор это в скайриме
Ascended~Sleeper, Нужно разумеется, мозги чесать, благо есть обо что :3 Я сегодня подозрительно категоричен в выражениях, премного извиняюсь)))
бывает)
Для начала, следует понять, с каким именно нордическим культом соотносятся барельефы: с тотемическим (упоминается в пятисотне и кинмуне) или собственно, драконьим.
в принципе, тотемизм — это и есть драконий культ.
в общем-то, снова фигурируют девять богов (восемь + Лррхан) и их в некотором роде аватары (чёртову сову забыла). если рассматривать нордов как «острие» наступательной культуры людей на культуру меров, то получается, что боги отображены совершенно зеркально — Ауриэль превратился не в сохраняющего Акатоша, а в разрушающего Алдуина, Лорхан из «отрицательного» бога в эльфийской культуре стал «положительным» Шором, хоть и оказался «изгнан» в подземный мир.
то есть это логичное «выворачивание» культуры под народ, отзеркаливание божественных ролей.
если драконий культ (как превосходство Алдуина-Акатоша-Ауриэля) считать изначальным (не оглядываясь пока на новое возвышение Шора-Лорхана), то можно выстроить иерархию тотемов исходя из классического эльфийского пантеона.
Талморцы, щито вы сделали с бренными останками Лорхана, демоны?
Массер нечаянно кверху ногами приколотили
Ещё любопытная дискуссия на эту тему на форме elderscrolls.net есть.
ога, отличная.
автор правда местами путается, но всё равно очень много полезного, и классные скрины барельефов!
DIANA_ARTEMIS, эти граждане озадачили всех)
Sieuc, что-то там не совсем просто было. потому что взять Исграмора — он явно не драконий жрец, но правил при драконьем культе (тот был окончательно свергнут только тринадцать поколений спустя) и туум вполне себе использовал. можно предположить, что сущестWowало некое разделение на правителей-воинов и правителей-жрецов — и на каждое владение приходилось по двое где-то.
Скайрим был разделён на 8 (или 9) владений, каждое с своим жрецом
так дело не в жрецах, дело в тотемах. а те пошли ещё с Атморы.
Источник: diary.ru