Category: математика

Раз уж зашла речь про алго­ритм шиф­ро­ва­ния RSA. Его сек­рет­ность зиждет­ся, повто­рюсь, на том, что чис­ло, полу­чен­ное пере­мно­же­ни­ем доста­точ­но длин­ных про­стых чисел, уму­ча­ешь­ся рас­кла­ды­вать на мно­жи­те­ли. Неве­ря­щие могут попро­бо­вать раз­ло­жить в уме (да мож­но даже с обыч­ным каль­ку­ля­то­ром) чис­ло 7081. Если не знать, что это 73×97, то при­дёт­ся пере­би­рать про­стые чис­ла до пол­но­го поси­не­ния.

Ну, не совсем пря­мо «до пол­но­го поси­не­ния», конеч­но — нет смыс­ла пере­би­рать мно­жи­те­ли >√(7081)≈84. Но всё рав­но — про­стых чисел мень­ше 83 (а 83 — наи­боль­шее про­стое чис­ло, мень­шее 84) доволь­но мно­го.

Ну, а реаль­ная крип­то­гра­фия, конеч­но, рабо­та­ет не на четы­рёх­знач­ных чис­лах, а на чис­лах с сот­ня­ми зна­ков — что поз­во­ля­ет нам без­опас­но пере­да­вать номер кре­дит­ки при покуп­ках накле­е­чек с коти­ка­ми в ентом вашем Ёнтер­не­те.

Несколь­ко лет назад всех вдруг накры­ла кван­то­вая пани­ка. Мол, да вот при­дут кван­то­вые ком­пью­те­ры, да на них рабо­та­ет алго­ритм Шора, и все эти ваши RSA, DH, ECDH, ECDSA, и про­чие умные сло­ва — поле­тят на свал­ку исто­рии. Ну да, ну да, поле­тят, как же. Вот толь­ко шнур­ки погла­дят — и сра­зу поле­тят.

Мир крип­то­гра­фии в лице NIST (и при актив­ной под­держ­ке Мик­ро­соф­та, надо отдать им долж­ное) в шухер­ном режи­ме стан­дар­ти­зи­ро­вал кван­то­во-устой­чи­вые алго­рит­мы крип­то­гра­фии, и сей­час у нас есть то, что не лома­ет­ся даже на ентих ваших куби­тах со всей их кван­то­вой запу­тан­но­стью и про­чей непо­нят­ной про­стым смерт­ным тео­ри­ей.

А на деле мы име­ем что? А на деле в 2001 году, с огром­ной пом­пой, кван­то­вый ком­пью­тер сумел-таки нако­нец раз­ло­жить на мно­жи­те­ли… чис­ло 15. Ага, пят­на­дцать. 3×5.

С тех пор были и дру­гие демон­стра­ции — 21, 35, ещё несколь­ко акку­рат­но подо­бран­ных чисел. Ино­гда с клас­си­че­ской «помо­щью», ино­гда с зара­нее извест­ной струк­ту­рой. Это важ­ные науч­ные шаги — никто не спо­рит. Но это не «взлом тра­ди­ци­он­ной крип­то­гра­фии к соот­вет­ству­ю­щей мате­ри». Это под­твер­жде­ние тео­рии в лабо­ра­тор­ных усло­ви­ях.

Дело в том, что алго­ритм Шора для взло­ма RSA-2048 тре­бу­ет поряд­ка несколь­ких тысяч логи­че­ских куби­тов, а каж­дый логи­че­ский кубит — это тыся­чи физи­че­ских куби­тов, пото­му что кван­то­вая тео­рия — это вам не тран­зи­стор, это крайне обид­чи­вая киса, и нор­маль­но рабо­та­ет она толь­ко при тем­пе­ра­ту­ре, близ­кой к абсо­лют­но­му нулю. Совре­мен­ные кван­то­вые ком­пью­те­ры — это несколь­ко сотен физи­че­ских куби­тов без пол­но­вес­ной кор­рек­ции оши­бок. А логи­че­ских, устой­чи­вых к шуму, — в прак­ти­че­ском смыс­ле пока нет.

Кван­то­вая угро­за реаль­на. Но она инже­нер­ная, а не маги­че­ская.
Меж­ду кра­си­вой тео­ре­мой Шора и маши­ной, спо­соб­ной ломать бан­ков­скую крип­то­гра­фию, лежат деся­ти­ле­тия про­ры­вов в физи­ке и инже­не­рии. Так что отста­вить пани­ку! До кван­то­во­го апо­ка­лип­си­са ещё очень дале­ко. Може­те пока спо­кой­но про­дол­жать поку­пать свои накле­еч­ки. С коти­ка­ми.

PS: Для тех, кто хочет коп­нуть глуб­же в совре­мен­ные оцен­ки и архи­тек­тур­ные огра­ни­че­ния кван­то­вых устройств, см. рабо­ту 2025 года на arXiv: https://arxiv.org/pdf/2410.14397v1

В мате­ма­ти­ке суще­ству­ют т.н. про­стые чис­ла — чис­ла, кото­рые ни на что, кро­ме себя (ну и еди­ни­цы, разу­ме­ет­ся) не делят­ся. Напри­мер, 17, 23, 73 (моё люби­мое чис­ло).

По их назва­нию — «про­стые» — мож­но поду­мать, что они какие-то… про­стень­кие, неслож­ные, неза­тей­ли­вые, невзрач­ные. В общем, не самые луч­шие, есть чис­ла и покру­че. А вот в англий­ском язы­ке они не “simple numbers” как мож­но было бы поду­мать, а “prime numbers” — что име­ет реши­тель­но дру­гое зна­че­ние. Не «про­стые», а «отбор­ные», «наи­луч­шие», «пер­во­класс­ные». Вот как есть отбор­ная говя­ди­на, кото­рую в обыч­ном про­стень­ком мага­зине не уку­пишь, пото­му что она почти пол­ным соста­вом ухо­дит напря­мую в ресто­ра­ны; она так и назы­ва­ет­ся — prime beef.

И мне, надо ска­зать, такое зна­че­ние нра­вит­ся зна­чи­тель­но боль­ше, пото­му что чис­ла эти дей­стви­тель­но исклю­чи­тель­ные! Имен­но на них постро­ен, напри­мер, алго­ритм шиф­ро­ва­ния RSA. Его сила заклю­ча­ет­ся в том, что если взять два доста­точ­но длин­ных про­стых чис­ла и их пере­мно­жить, то полу­чен­ное чис­ло будет иметь ров­но два нетри­ви­аль­ных про­стых дели­те­ля (ну плюс себя само и еди­ни­цу, разу­ме­ет­ся) — а искать эти дели­те­ли при их, повто­рюсь, доста­точ­ной длине (в RSA-4096 каж­дый из мно­жи­те­лей име­ет более шести­сот деся­тич­ных цифр, а сам модуль пре­вы­ша­ет тыся­чу две­сти цифр) — тре­бу­ет аст­ро­но­ми­че­ских вычис­ли­тель­ных мощ­но­стей. На клас­си­че­ских ком­пью­те­рах эта зада­ча в обо­зри­мое вре­мя не реша­ет­ся. А вы гово­ри­те, мол, чис­ла «про­стые». Э, нет, не про­стые, а как раз самые что ни на есть отбор­ные!!

А поче­му такая раз­ни­ца в фило­со­фии? Пото­му что в рус­ском мате­ма­ти­че­ском «про­стые» — от смыс­ла «не состав­ные», а в англий­ском «prime» — от латин­ско­го primus, «пер­вый». То есть, «изна­чаль­ные», «пер­вич­ные» — пото­му что любое состав­ное чис­ло мож­но раз­ло­жить на про­стые, «пер­вич­ные» мно­жи­те­ли 🙂

Вот если видео­ро­лик длит­ся 30 минут, и ско­рость вос­про­из­ве­де­ния уве­ли­чить на 20%, како­во будет вре­мя вос­про­из­ве­де­ния роли­ка?

Инту­и­тив­но хочет­ся ска­зать, что 24 мину­ты, пото­му что 20% это ¹⁄₅, одна пятая от 30 минут это 6 минут, и 30 — 6 = 24? Да? Авот­хрен.

Уве­ли­чи­ва­ет­ся ско­рость вос­про­из­ве­де­ния, а дли­на зави­сит от неё обрат­но про­пор­ци­о­наль­но. Вре­мя = дли­на роли­ка / ско­рость. Ско­рость у нас на 20% боль­ше, зна­чит вме­сто 1.0 теперь ско­рость 1.2. ³⁰⁄₁.2 = 25 минут.

Акку­рат­нее, блин, надо.

Ока­зы­ва­ет­ся, кро­ме при­выч­ных при­зна­ков дели­мо­сти на 2, 3, 5, и 9, суще­ству­ет и при­знак дели­мо­сти на 7!

Возь­мём, напри­мер, чис­ло 203. Послед­няя циф­ра — 3. Умно­жа­ем её на 2 и вычи­та­ем из остав­ших­ся цифр, то есть из 20:

20 − 6 = 14.
14 делит­ся на 7, зна­чит и 203 делит­ся на 7: ²⁰³⁄₇ = 29.

Рабо­та­ет даже с более круп­ны­ми чис­ла­ми!

Ещё при­мер: 973. Берём послед­нюю циф­ру (3), удва­и­ва­ем и вычи­та­ем из остав­шей­ся части чис­ла:

97 − 6 = 91.
Делит­ся ли 91 на 7? Хм, не сра­зу понят­но. Повто­рим пра­ви­ло ещё раз:

9 − (1×2) = 7 — делит­ся!
Зна­чит, и 973 делит­ся на 7: ⁹⁷³⁄₇ = 139.

Мож­но при­ме­нять этот метод даже к пяти­знач­ным и далее чис­лам — рекур­сив­но!

Возь­мём 13762.

Послед­няя циф­ра — 2, удва­и­ва­ем и вычи­та­ем:
1376 − 4 = 1372.

Неяс­но? Повто­ря­ем:
137 − (2×2) = 133.

Всё ещё не оче­вид­но? Ещё раз:
13 − (3×2) = 7 — делит­ся!

Зна­чит, и 13762 раз­де­лит­ся на 7: ¹³⁷⁶²⁄₇ = 1966.

Офи­геть, нас это­му не пом­ню, что­бы учи­ли (у меня, прав­да, была язы­ко­вая шко­ла, не обыч­ная или физи­ко-мате­ма­ти­че­ская, может быть, это не сек­рет вовсе). Это моё стар­шее чадо попа­ло в школь­ную мате­ма­ти­че­скую коман­ду и теперь ездит на сорев­но­ва­ния! Недав­но уда­лось уви­деть этот при­ём у него в тет­ра­ди — понра­ви­лось жут­ко, захо­те­лось поде­лить­ся 🙂

В дет­стве у меня был про­иг­ры­ва­тель для вини­ло­вых пла­сти­нок с изме­ня­е­мой ско­ро­стью про­иг­ры­ва­ния. Обыч­ный диск на 33 обо­ро­та мож­но было запу­стить на 45 — уже полу­ча­лось смеш­но. А мож­но было зафи­га­чить аж на 78 обо­ро­тов — тогда пла­стин­ка про­иг­ры­ва­лась очень быст­ро, и всё зву­ча­ло по-муль­тяш­но­му. По баш­ке, конеч­но, надо было мне дать, что­бы пла­стин­ки не пор­тил, но что было, то про­шло. У меня сей­час тоже про­иг­ры­ва­тель пла­сти­нок есть, но такой дурью я боль­ше не маюсь. Про­сто играю пла­стин­ки и всё.

Так вот, все­гда мучал вопрос — как это ютуп­чик и про­чие сер­ви­сы видео- и аудио­кон­тен­та, типа под­ка­стов, могут убыст­рять (или замед­лять) про­иг­ры­ва­ние зву­ка без изме­не­ния его высо­ты?

Ока­за­лось, что дела­ют так:

1. Раз­би­ва­ют циф­ро­вой звук на малень­кие бло­ки в 512‑2048 байт. На часто­те дис­кре­ти­за­ции в 44.1 кило­гер­ца эти бло­ки име­ют дли­ну все­го несколь­ко мил­ли­се­кунд.
2. На каж­дом бло­ке запус­ка­ют пре­об­ра­зо­ва­ние Фурье. Для тех, кто вдруг не зна­ет — это мате­ма­ти­че­ский спо­соб раз­бить звук на инди­ви­ду­аль­ные состав­ля­ю­щие часто­ты.
3. Вос­со­зда­ют те же часто­ты, но про­сто уко­ра­чи­ва­ют или уве­ли­чи­ва­ют им дли­ну про­иг­ры­ва­ния в нуж­ное коли­че­ство раз по жела­нию поль­зо­ва­те­ля. Скле­и­ва­ют звук назад.

PROFIT!

Ну, немно­го послож­нее, конеч­но (обыч­но там не тупо дис­крет­ные бло­ки по 512 байт, а т.н. «сколь­зя­щее окно» (sliding window) раз­ме­ром в 512 байт, напри­мер, но осно­ва алго­рит­ма Phase Vocoder («фазо­вый воко­дер», что ли?) имен­но такая.

При­коль­но. Неуже­ли всё это дела­ет­ся пря­мо в бра­у­зе­ре, джа­вас­крип­том? Обал­деть. Навряд­ли на сер­ве­ре хра­нят­ся сто раз­ных вер­сий одно­го и того же видео­фай­ла.

Одна­ко, ров­но месяц назад Наци­о­наль­ный Инсти­тут Стан­дар­тов и Тех­но­ло­гий США (NIST) нако­нец-то решил, каки­ми имен­но алго­рит­ма­ми шиф­ро­ва­ния мы будем поль­зо­вать­ся для защи­ты инфор­ма­ции в пост-кван­то­вую эпо­ху.

Ска­жем, обыч­ный RSA для таких целей уже не под­хо­дит, так как вся сила RSA в том, что раз­ло­же­ние 4096-бит­но­го чис­ла на два про­стых мно­жи­те­ля — это экс­тре­маль­но ресур­со­ём­кая зада­ча, на кото­рую даже на совре­мен­ных супер­ком­пью­те­рах пона­до­бит­ся срок, срав­ни­мый с воз­рас­том наблю­да­е­мой Все­лен­ной.

Но для кван­то­вых ком­пью­те­ров суще­ству­ет алго­ритм Шора, поз­во­ля­ю­щий про­ве­сти раз­ло­же­ние на мно­жи­те­ли за суще­ствен­но мень­ший (лога­рит­ми­че­ский) срок.

А теперь Мик­ро­софт объ­явил, что пер­вый из алго­рит­мов, ML-KEM (чорт, мне нра­вит­ся это назва­ние, КЕМ!) уже встро­е­ны в стан­дарт­ную биб­лио­те­ку шиф­ро­ва­ния их ОС. ML-KEM — алго­рит­мом Шора уже не лома­ет­ся.

При­ят­но удив­лён такой про­зор­ли­во­стью и опе­ра­тив­но­стью — за месяц нари­со­вать и отте­сти­ро­вать такую ответ­ствен­ную вещь, как алго­ритм шиф­ро­ва­ния — это похваль­но. Но, конеч­но, навер­ня­ка им из НИСТа кто-нибудь свист­нул зара­нее.

Т.к. дату в фор­ма­те ММДДГГГГ обыч­но пишут толь­ко в США, спе­ци­аль­ный день кален­да­ря 3.14 полу­ча­ет­ся сугу­бо аме­ри­кан­ским.

Ну, тогда вот вам шут­ку на мате­ма­ти­че­ском англий­ском.

Объ­яс­няю, если кто недо­по­нял:

Квад­рат­ный корень из минус еди­ни­цы — это ком­плекс­ное чис­ло, кото­рое запи­сы­ва­ют бук­вой i.
Двой­ка в тре­тьей сте­пе­ни — это восемь (eight), про­из­но­сит­ся точ­но так же как сло­во ate.
Сиг­ма — это сум­ма (sum), про­из­но­сит­ся как сло­во some.
Ну и само чис­ло Пи, кото­рое в англий­ском Pi, и про­из­но­сит­ся не как Pee, а как сло­во Pie (пирог).

Так что полу­ча­ем фра­зу, кото­рая зву­чит как i ate some pie (я съел кусок пиро­га). Мате­ма­ти­че­ский кавай.

Обо­жаю такие шут­ки.

Мате­ма­тик захо­дит в забе­га­лов­ку, берёт сто­лик на дво­их. К нему под­хо­дит неопрят­ная офи­ци­ант­ка.

–Что буде­те зака­зы­вать?
–Я зака­жу биф­штекс, но я так­же хочу разыг­рать сво­е­го кол­ле­гу, кото­рый тут будет с мину­ты на мину­ту. Вот сто дол­ла­ров; когда он при­дёт, я задам вам вопрос, а вы отве­ти­те «икс в кубе поде­лить на три», хоро­шо?
–Конеч­но.

Офи­ци­ант­ка берёт день­ги и ухо­дит.

За сто­лик при­са­жи­ва­ет­ся кол­ле­га мате­ма­ти­ка.

–При­вет!
–При­вет! Слу­шай, тут такое класс­ное место, и даже обслу­жи­ва­ю­щий пер­со­нал умный. Вот смот­ри!

Мате­ма­тик оста­нав­ли­ва­ет про­хо­дя­ю­щую мимо офи­ци­ант­ку.

–Ска­жи­те мне, каков будет неопре­де­лён­ный инте­грал функ­ции икс в квад­ра­те?
–Икс в кубе поде­лить на три плюс кон­стан­та.

PS: шут­ка пре­крас­но пере­во­дит­ся на все язы­ки, матан — язык уни­вер­саль­ный.