[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]

[Burichan] [Foliant] [Futaba] [Greenhell] [Gurochan] [Photon] - [Home] [Manage] [Archive]

[Return]
Posting mode: Reply
Leave these fields empty (spam trap):
Name
Link
Subject
Comment
File
Verification
Password (for post and file deletion)
  • Supported file types are: GIF, JPG, PDF, PNG
  • Maximum file size allowed is 20480 KB.
  • Images greater than 200x200 pixels will be thumbnailed.

File: 1385221681931.jpg -(148641 B, 461x576) Thumbnail displayed, click image for full size.
148641 No.99624  

Суп, анон. Вот читал статью про Bitcoin и криптографию и не смог понять. Сама статья вот: https://self-evident.org/?p=976
В ней криптография объясняется на примере криптофункции Рабина. Если я правильно понял, то она работает так:

Предположим, я создал сообщение X и закодировал его большой цифрой Y. Правила кодирования всем известны и раскодировать Y может любой желающий. Но чтобы подтвердить, что Y - действительно создан мной - я применяю криптофункцию Рабина.

Выглядит она так: f(x) = square(x) | mod n
Где n = p*q, p и q = это простые числа (prime numbers).
n - мой публичный ключ, p и q - приватный ключ.

То есть, допустим, если p и q = 3 и 7 соответственно, а x, предположим, равен 12, то ф-ия будет выглядеть так:

f(12) = (12*12) / (3*7) = 144/21 = 6,857142857
Берем остаток 857142857 - это и есть результат работы этой функции.

Так вот, предположим, что мой y = 18. Тогда, чтобы подтвердить, что y создан мной, я беру и подбираю такой x для своей криптофункции, который после возведения в квадрат и деления на n оставит остаток, который и будет равняться моему сообщению y, то есть 18. Однако математики говорят, что, мол, если n - это произведение двух простых чисел, то быстро подобрать такой x можно, только зная p и q, то есть мой приватный ключ. Это доказано в т.н. Chinese Remainder Theorem. То есть другой человек не сможет найти число, квадрат которого после деления на мой публичный ключ n оставляет заранее заданный остаток, поэтому, даже если он знает, что f(x) = square(x) | mod n, знает y и знает n, то он не сможет подобрать x и не сможет подтвердить, что он создал Y.

Но вот чего я не могу понять:
Если мой n - 21, а y = 18, то чтобы найти x, я ведь могу просто умножить n, скажем, на 4, прибавить к нему остаток 18 и из полученного извлечь корень:

x = (4*21)+18 = 102
102/21 = 4 + 18 в остатке

Корень из 102 - и есть искомый x. Итак, ЧЯДН?

>> No.99625  

>>99624
Тебе нужно целое число, а sqrt(102) - нецелое.

>> No.99626  
File: 1385223077531.jpg -(160950 B, 963x640) Thumbnail displayed, click image for full size.
160950

>>99624

> Корень из 102 - и есть искомый x. Итак, ЧЯДН?

sqrt(102)=10.0995 в то время как у тебя x=12

>> No.99627  
File: 1385224279981.jpg -(34804 B, 300x390) Thumbnail displayed, click image for full size.
34804

>>99625
>>99626
То есть в этом и есть вся сложность нахождения X? Разве сложно будет найти подходящее число, корень у которого - целый?

>> No.99628  
File: 1385225529895.jpg -(224543 B, 600x1022) Thumbnail displayed, click image for full size.
224543

>>99627
Попробуй повторить свой опыт например для x=100500 p=3221 q=3229

>> No.99629  
> f(12) = (12*12) / (3*7) = 144/21 = 6,857142857
> Берем остаток 857142857 - это и есть результат работы этой функции.

Это не остаток от деления, это дробная часть.

> Однако математики говорят, что, мол, если n - это произведение двух простых чисел, то быстро подобрать такой x можно, только зная p и q, то есть мой приватный ключ. Это доказано в т.н. Chinese Remainder Theorem.

Proof or GTFO. Уж хотя бы на анонимной борде можно не пиздеть о том, чего не знаешь. Китайская теорема не об этом, а сложность разложения на множители — гипотеза.

> Корень из 102 - и есть искомый x. Итак, ЧЯДН?

Извлечение корня по модулю составного числа эквивалентно задаче разложения его на множители.

>> No.99630  

Китайская теорема об остатках позволяет *ускорить* вычисления при знании разложения, но не факт, что без разложения нельзя построить такой же быстрый (асимптотически) алгоритм. Это открытая проблема.

>>99629-кун

>> No.99631  
File: 1385235379064.jpg -(0 B, 300x390) Thumbnail displayed, click image for full size.

>>99629
>>99630
ОК, понял. Ты, наверное, все правильно говоришь. Только интересно насчет статуса гипотезы:
1) Мне кажется, что всем кажется, что действительно невозможно найти быстрый алгоритм размножения. Насколько я знаю, никто над этой проблемой даже не работает.

2) Теоретически, существует ли способ доказать, что создание такого алгоритма невозможно? Если нет, то не возникает ли проблемы с фальсифицируемостью? Если не возникает, то как долго предположение о возможности создания такого алгоритма будет оставаться открытой, а не закрытой проблемой, если, скажем, в течение следующих 1000 лет не будет никакого прогресса в этом вопросе?

>> No.99632  

>>99631

> Мне кажется, что всем кажется, что действительно невозможно найти быстрый алгоритм размножения. Насколько я знаю, никто над этой проблемой даже не работает.

Ничего нового практически нет: http://scholar.google.com/scholar?q=integer+factorization

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

> Теоретически, существует ли способ доказать, что создание такого алгоритма невозможно?

Возможно, что не существует. Логика неполна, так что все может быть, о доказательстве возможности доказательства мне ничего не известно.

> Если нет, то не возникает ли проблемы с фальсифицируемостью?

define фальсивицируемость

> Если не возникает, то как долго предположение о возможности создания такого алгоритма будет оставаться открытой, а не закрытой проблемой, если, скажем, в течение следующих 1000 лет не будет никакого прогресса в этом вопросе?

Задача будет оставаться открытой, пока не будет решена, очевидно же.

>> No.99633  

>>99632
s/фальсивицируемость/фальсифицируемость/

>> No.99638  

>>99632
Из википедии:
Фальсифици́руемость (принципиальная опровержимость утверждения, опроверга́емость, крите́рий По́ппера) — критерий научности эмпирической теории, сформулированный К. Р. Поппером в 1935 году[1]. Теория удовлетворяет критерию Поппера (является фальсифицируемой и, соответственно, научной) в том случае, если существует методологическая возможность её опровержения путём постановки того или иного эксперимента, даже если такой эксперимент ещё не был поставлен.

Я так понимаю, сюда она не применяется.

>Логика неполна

Это ты о теореме Гёделя? Если да, то я до нее пока не добрался, но из нее как-то следует, что мы не можем заранее узнать возможность или невозможность тех или иных вещей в математике?

>> No.99645  

>>99638

> критерий научности эмпирической теории
> эмпирической теории
> Я так понимаю, сюда она не применяется.

Именно так.

> Это ты о теореме Гёделя? Если да, то я до нее пока не добрался, но из нее как-то следует, что мы не можем заранее узнать возможность или невозможность тех или иных вещей в математике?

Теорема вообще об аксиоматике теории чисел. Теорию сложности алгоритмов может быть можно как-то переформулировать и без нее, хотя будет заметно сложнее (это же нужно пределы и вообще весь матан задать аксиоматически). Но пока не доказано обратное, возможно, что утверждение о возможности создания алгоритма полиномиальной сложности нельзя ни доказать, ни опровергнуть (т.е. создать алгоритм), тогда у нас будет вечно висеть открытая проблема. Или кто-нибудь докажет, что утверждение ни доказать, ни опровергнуть нельзя, но это тоже может никогда не случиться.

>> No.100755  

Математика вообще неправильная.

Она не работает.

На каком принципе построены все эти числа? Что такое вообще идея четырёх — стульев, пенисов, дыр, животных? Общее между ними только то, что мы четыре раза подряд дёрнем взглядом, рассматривая их. Математика построена на чередованиях и разрывах, точках и тире. А мир — не такой. Он плавный. Поэтому до конца числа Пи никто никак добраться не может.

Правда, один пьяный мужик в подворотне мне рассказывал, что существует ещё подраздел математики, который занимается «континуумами», но в этом я ничего не понимаю.

>> No.100756  

>>100755

>А мир — не такой. Он плавный.

Есть аргументы в пользу того что в физике вещественные числа не существуют ни в каком виде.
Простой аргумент: в вещественном числе можно записать бесконечное количество информации, а количество информации которое может храниться в конечном объёме пространства ограничено пределом Бекенштейна.
Подробнее читай у Хайтина: http://www.cs.auckland.ac.nz/~chaitin/olympia.pdf‎

>> No.100763  

>>100756
А кто сказал, что оно ограничено? Может оно и на самом деле бесконечно.

>> No.100764  

>>100755
Нихуя не понял. Может ты пытался сказать, что пространство и время - не дискретны? Но тогда как раз не было бы иррациональных чисел. Любую величину можно было бы выразить точным значением. А иррациональные числа - это как раз то, что существует между квантами пространства.
А может быть и нет. I have no idea what I'm saying.

>>100756
Покажи мне пространство, в котором хранится больше информации, чем оно может вместить. Соснул? А вещественные числа-то между тем существуют. Попробуй убрать из квантовой физики ту же pi, посмотрим, что у тебя получится.

>> No.100768  
File: 1388320214111.jpg -(195295 B, 1062x1500) Thumbnail displayed, click image for full size.
195295

Существует предельная точность, дальше которой даже в теории нельзя измерить теми способами, которыми мы определяем положение частиц. Учитывая, что способы измерения имеют ту же природу, вполне уместно предположить квантование пространства. С другой стороны, это может оказаться ограничем модели, и формализм описания мира потребует переработки

>> No.100780  
File: 1388346998307.gif -(11971 B, 250x242) Thumbnail displayed, click image for full size.
11971

>>100768
Да ты охуел мою Куристиину в таком виде постить.
Я тебя вычислю по IP, мудак.

>> No.100781  

>>100780
Опасно такие штуки писать. Какой-нибудь мудак решит тебя зотролить и напостит хардкора

>> No.100782  

Или в этом и состоит твой хитрый план, чтобы кто-то искал и постил для тебя, а ты только дрочил? Больной извращенец, как ты можешь хотеть такого с Куристиной??

>> No.100879  
File: 1388721498398.jpg -(1864808 B, 1954x5096) Thumbnail displayed, click image for full size.
1864808

>>100780 >>100782
Без "-тина"

>> No.101009  

>>100764
А какое значение имеет число pi в физике? Именно в самой физике, если исключить его математический смысл?

>> No.101013  

>>101009
А какое значение имеет буква "е" в общении? Именно в самом общении, если исключить ее лингвистический смысл?

>> No.101014  

>>101013
Буква "е" — обозначение конкретного звука, в то время как pi — обозначение всего лишь математической абстракции, реально нигде не существующей.

>> No.101018  

>>101014
Современная физика -- обозначение всего лишь математической абстракции, реально нигде не существующей.

>> No.101087  
> большой цифрой

Дальше не читал.

>> No.101192  

>>101018
This.

>> No.103325  

>>99631

>размножения

разложения

*быстрофикс [spoiler]через 5 месяцев[/spoiler]



Delete Post []
Password

[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]