僕の「分割加算」の冒頭を読んでくれた方に

76 Res.　50.14967002 MONA　4 Fav.

1 ：izuna五段(IWU)：2019/07/10 04:15:53 (5年前) 0.02288888MONA/3人

公開鍵暗号の演算の高速化の方法「分割加算」を考えました。
このURLの「はじめに」を読んでいただけた方に１モナを進呈します。
https://icf.hatenablog.com/entry/2018/09/26/122020
１人１回、50人まで。
９行の簡単な説明文なので、カテゴリを、バラマキにしてみました。
「読んだ」とかで、構いません。バラマキのカテゴリなので。
感想でもいいです。よろしくお願いします。

2 ：izuna五段(---)：2019/07/10 04:24:14 (5年前) 0MONA/0人

冒頭読んで、わからないけど、もう少し知りたい人へ

10進2桁の加算、例えば28+16。
1桁の加算器だと2回演算することになります。
1桁目、8+6 = 14
2桁目、2+1 = 3 と1桁目の桁上がりで 44になります。

1桁の加算器を2個で並列に1回加算すると、桁上がりがうまくいかず、34になってしまって、並列化できません。

ところが「分割加算」を使えば、1桁の加算器、2個並列の１回加算で正しい44を計算できて、高速に演算できます。

RSA 2048bitでは43個(86個)の演算器が並列に動作します。普通にやれば43回が1回で計算できるのです。

3 ：izuna五段(---)：2019/07/10 04:31:20 (5年前) 0MONA/0人

>> 2
> 普通にやれば43回が1回で計算できるのです。

1桁の加算器を直列に43個、並べて1回にすれば、演算時間は1桁の加算器1回の時間の43倍よりも、かなり小さい時間で演算できます。

4 ：目指せ北海道三段錬士(---)：2019/07/10 05:50:59 (5年前) 1MONA/1人

新型の高速ASICが作れるってことですか？

5 ：izuna五段(---)：2019/07/10 07:23:19 (5年前) 0MONA/0人

>>4
> 新型の高速ASICが作れるってことですか？

作ることも可能です。ただASICは初期コストが高いのでFPGAがいいかと思っています。FPGAでも演算のコアな部分は、ほぼDSPで、構成されるので、それなりに高速だと思います。

6 ：Kixi二段(---)：2019/07/10 07:40:12 (5年前) 1MONA/1人

読みました！
逐次実行する桁の大きな加算を、並列動作させて高速化しようといった試みでしょうか？(よく分かっていない)

7 ：空白初段(---)：2019/07/10 10:57:13 (5年前) 1MONA/1人

読みました

8 ：滅師五段(---)：2019/07/10 11:02:38 (5年前) 1MONA/1人

おじちゃんさっぱり分からない

9 ：名々四段教士(---)：2019/07/10 11:12:56 (5年前) 1MONA/1人

読みましたが、自分には難しすぎて...

10 ：アグレッシブ乞食四段範士(---)：2019/07/10 11:57:34 (5年前) 1MONA/1人

少しは内容わかるかなと思って読んだが本当にサッパリで自分の知識不足を痛感＼(^o^)／

11 ：おぴょぴょ鯖男五段錬士(---)：2019/07/10 12:39:24 (5年前) 1MONA/1人

読んだよー（　´∀｀）
（む…難しい。。）

12 ：ミスターモナコ2.9五段教士(---)：2019/07/10 13:01:53 (5年前) 1MONA/1人

読みましたー

13 ：名無し初段錬士(---)：2019/07/10 13:19:42 (5年前) 1MONA/1人

読みました

14 ：スモーキー初段(---)：2019/07/10 13:37:35 (5年前) 1MONA/1人

読みました。
難しいですね。

15 ：名無し三段(---)：2019/07/10 13:57:50 (5年前) 1MONA/1人

読みました
前提知識足りなさ過ぎて申し訳ない

16 ：METATOPIA三段(---)：2019/07/10 14:59:17 (5年前) 1MONA/1人

読みました!!
わかりませんでした!!

17 ：タンヤオ九段範士(---)：2019/07/10 15:30:19 (5年前) 1MONA/1人

読んでみました
モンゴメリ法は昔少しかじって挫折しました
概要は掴めましたが、詳しいところまでは…
勉強します

18 ：なむやん七段教士(---)：2019/07/10 18:52:24 (5年前) 1MONA/1人

読んだ、けどわからなかったのが本音

19 ：銀太郎三段(---)：2019/07/10 19:21:07 (5年前) 1MONA/1人

読んでみた。
Fラン文系の私には「モンゴメリ乗算」から既に解らなかったので色々ググった（笑）
ちょっとだけお勉強になりました。

20 ：caffeine中毒六段教士(---)：2019/07/10 19:40:42 (5年前) 1MONA/1人

読ませて頂きました。
補足のおかげで原文だけを読むよりは多少は理解出来たと思います。

21 ：无三段(---)：2019/07/10 19:43:31 (5年前) 1MONA/1人

読みました

22 ：名無し初段(---)：2019/07/10 20:00:15 (5年前) 1MONA/1人

読みました！

23 ：ひやむぎ三段錬士(---)：2019/07/10 21:56:46 (5年前) 1MONA/1人

読みました。
専門的でさっぱりわからない…

24 ：名無し初段(---)：2019/07/10 23:06:53 (5年前) 1MONA/1人

読みました！
私には難しすぎます…

25 ：名有り三段(---)：2019/07/11 05:52:35 (5年前) 1MONA/1人

意味不明な公式が出ましたが読みました！

26 ：名無し四段(---)：2019/07/11 05:59:00 (5年前) 1MONA/1人

読みました！(ここの感想で少し分かるくらい....

27 ：NNSH五段(---)：2019/07/11 06:04:35 (5年前) 1MONA/1人

読みました！
ID表示にした方がいいのでは？

28 ：名無し初段(---)：2019/07/11 08:38:22 (5年前) 1MONA/1人

読ませて頂きました！

29 ：名無し四段教士(---)：2019/07/11 10:23:11 (5年前) 1MONA/1人

文系人間ですが読ませて頂きました。

30 ：なな二段(---)：2019/07/11 12:24:01 (5年前) 1MONA/1人

読みました!
難しい。。

31 ：short hair初段(---)：2019/07/11 13:19:32 (5年前) 1MONA/1人

読みました！

32 ：izuna五段(IWU)：2019/07/11 13:26:22 (5年前) 0MONA/0人

登録タグに、僕が国産仮想通貨のNANASHIでお金を集めて持ち逃げしたみたいな書き込みがあったので、削除させていただきました。

僕はNANASHIとは関係ありません。

33 ：ぽん酢二段(VCR)：2019/07/11 13:36:11 (5年前) 1MONA/1人

読みました！
難しいのでイラストを交えて説明してはいかがでしょうか？

34 ：名有り四段錬士(EKS)：2019/07/11 14:53:52 (5年前) 1MONA/1人

読みました。でも難しい・・久しぶりにΣをみたぞ～

35 ：名無し初段錬士(RXR)：2019/07/11 15:13:02 (5年前) 1MONA/1人

読みました！
ただ、頭が痛くなりました(〃ω〃)

36 ：がんばる親父三段教士(RPX)：2019/07/11 16:48:50 (5年前) 1MONA/1人

読みました。
が、とても難しくまったくわかりませんでした。すいません。
うまくいくとどんな未来が待っているのでしょうか？

37 ：ゴミクソヒモ野郎五段範士(BZD)：2019/07/11 17:19:30 (5年前) 1MONA/1人

内容が難しいですが、読みました

38 ：名無し初段(NVO)：2019/07/11 18:18:09 (5年前) 1MONA/1人

読みました！
(全くわからない…)

39 ：ナナスィ八段教士(QJL)：2019/07/11 18:58:40 (5年前) 1MONA/1人

最後まで読みました
最後までわかりませんでした

40 ：izuna五段(IWU)：2019/07/11 19:16:00 (5年前) 0MONA/0人

>>36
> うまくいくとどんな未来が待っているのでしょうか？

「うまくいくと」ですね。RSA暗号の延命して常時httpsにかかるコストが世界的に下がる。

ビットコインの技術的な動向とか知らないのですが、もし仮にECDSAが256bitから1024bitになって性能が必要になれば、この分割加算が役に立つことがあるかも。僕の知る範囲内に、そうなりそうな気配は、今のところないので、、、

大きな数を使う新しい公開鍵暗号の発明の実現を用意にするとか。

この国に高度な暗号実装技術があることよる効果、、、とか。

41 ：izuna五段(IWU)：2019/07/11 19:17:54 (5年前) 0MONA/0人

RSAを高速化する方法として、モンゴメリ乗算の高基数型と低基数型があります。高基数型は乗算器をパイプライン化して高い周波数を出せるため高速です。ただ乗算器にデータを途切れなく流し込んでRSAの演算結果にできる制御論理が大きくなりやすい。実装環境毎の依存性も大きく開発コストが大きいといったデメリットがあります。一方、低基数型のICF3-F(分割加算)はパイプラインはないものの、データのローカリティが高く作りやすい。実装環境毎の依存性が小さく開発コストが小さい。鍵長に比例した演算ゲートを投入することで性能を上げることができる。デメリットは高基数型と比較して乗算器の周波数を上げられないため性能が出にくい。
楕円暗号のように鍵長が小さいうちは高基数型が有利ですが、RSAのように鍵長が長くなってくれば低基数型になってくるかもしれない。高基数は演算器の効率は高いのですが、制御論理も大きくなってしまうため、演算器の性能だけでなく、RSA署名１演算の全工程ができる実装で比較しなければいけません。

42 ：眠いよ六段錬士(VUK)：2019/07/11 20:22:52 (5年前) 1MONA/1人

よく分からないですが未来に役に立つものだということは分かります！
読みました、、

43 ：ABC三段(QPY)：2019/07/11 20:28:10 (5年前) 1MONA/1人

読みましたが.....難しい

44 ：名無し二段(QPY)：2019/07/11 20:30:06 (5年前) 1MONA/1人

読みましたがΣとは何でしょうか？

45 ：名無し二段(COK)：2019/07/11 20:39:33 (5年前) 1MONA/1人

GPUよりは高速化できそうですか？

46 ：mao二段(VSY)：2019/07/11 20:41:35 (5年前) 1MONA/1人

読みました,monacoinを配布する意図はなんでしょうか()＾＾

47 ：名無し二段(DHJ)：2019/07/11 20:43:31 (5年前) 1MONA/1人

読みました、タグ変更禁止にしてみては？

48 ：mona隊二段(EQF)：2019/07/11 20:50:17 (5年前) 1MONA/1人

読んだお

49 ：izuna五段(IWU)：2019/07/11 20:52:07 (5年前) 0MONA/0人

>>44
> 読みましたがΣとは何でしょうか？

高校で文科系の数学でも、恐らく習うΣです。
証明は受験科目に数学ある文科系学科の方でも理解できるのではと思っています。

「分割加算」以外の高速化の論文にはRNS(Redundant Number System)とかRNS(Residue Number System)が、多数ありますが、それらより、アルゴリズムレベルで高速かと。論文からRSA署名１演算の全体の計算方法が読み取りにくいことが多いので、わからないところはあります。

これらの論文では乗法が定義されていたり、2bitの冗長性を定義するものがあります。各桁で余算をしているように見えるものもあります。僕の分割加算では、そういう演算は不要です。累積加算のレジスタ１つを1bitの冗長性で表現して、普通の乗算結果を累積加算しています。

50 ：名無し二段(XRJ)：2019/07/11 20:55:51 (5年前) 1MONA/1人

>>1さん

>>43 と　>>44　は同一人物ですよ....
一応読ませていただきました！

51 ：izuna五段(IWU)：2019/07/11 21:05:09 (5年前) 0MONA/0人

>>45
> GPUよりは高速化できそうですか？

GPUとの比較では、高性能というよりは、低レイテンシとか、低消費電力とか、DDRメモリ無しでいいとか、コスパが、違います。

この分割加算はGPUにも実装できます。どのくらいの性能になるのかは、わかりませんが、FPGAのほうが有利だと予測しています。

僕はGPUのプログラミングも経験があるので、後で、やってみることは、できると思っています。

52 ：ひで！三段範士(DRN)：2019/07/11 21:09:59 (5年前) 1MONA/1人

モンゴメリ定山渓！！！
難しいですね！

53 ：izuna五段(IWU)：2019/07/11 21:11:35 (5年前) 0MONA/0人

>>46
> 読みました,monacoinを配布する意図はなんでしょうか()＾＾

バラマキと言っておきながら、読ませているあたりとか。
スレが荒れないように、荒れ止め、とか。

54 ：ナナシ初段(DGA)：2019/07/11 21:16:22 (5年前) 1MONA/1人

読みました！！！

55 ：yamaja三段錬士(FXS)：2019/07/11 22:16:21 (5年前) 1MONA/1人

読みました!!! う〜ん私にはよく分からないでした! 難しいですね。

56 ：X+Y=MONA五段教士(IGJ)：2019/07/11 23:58:11 (5年前) 1MONA/1人

読みました！！
１文字も修正なしとはね～

57 ：RALLY三段錬士(SJH)：2019/07/11 23:58:52 (5年前) 1MONA/1人

読ませていただきました!

すごく難しくて私にはちんぷんかんぷんですが

こういう所から新しいものが生まれるんだろうなぁと感じました。

izuna五段様が新しい物をいつか世に生み出して世の中が便利に

鳴る事を願っております(*'ω'*)

58 ：名無し初段(BGG)：2019/07/12 01:05:48 (5年前) 1MONA/1人

読みました。
申し訳ないですが分かりませんでした

59 ：mix二段(XRJ)：2019/07/12 05:26:27 (5年前) 1.02525MONA/2人

読みましたー

60 ：ん、、？二段(GEE)：2019/07/12 05:27:57 (5年前) 1MONA/1人

読ませていただきました。

61 ：目指せ北海道三段錬士(OLP)：2019/07/12 05:43:01 (5年前) 0MONA/0人

とりあえず、量子コンピュータのシミュレーションに突っ込んでみたらどうでしょう？

62 ：のりりん二段錬士(BHJ)：2019/07/12 06:55:32 (5年前) 0MONA/0人

確かに、その通りかと。

63 ：名無し初段(QLN)：2019/07/12 07:21:30 (5年前) 0MONA/0人

読みました

64 ：izuna五段(IWU)：2019/07/12 07:42:45 (5年前) 0MONA/0人

>>61
> とりあえず、量子コンピュータのシミュレーションに突っ込んでみたらどうでしょう？

量子コンピュータによる暗号解読についてシミュレーションしてみるということでしょうか。

量子コンピュータについてニュースで読む程度ですが、次のニュースによれば、RSA 2048bitよりも、ビットコインのほうが、少ないqubitで解読できるようです。ノイズなどの問題でqubitの数を増やすことが難しいらしく、だとすれば、RSA 2048bitよりもビットコインが先に崩壊します。

https://news.mynavi.jp/article/20181228-sc18_qubit/

qubitの数を増やすのが難しい場合、RSAの鍵長を長くすれば安全が保てる。

仮に解読されたとしても、一般に公開されない可能性が大きい。新しい公開鍵暗号へ移行するコストで、各国の税金が持たない。大国の諜報機関も、そのほうが都合がいい。

65 ：izuna五段(IWU)：2019/07/12 07:53:37 (5年前) 0.00114114MONA/1人

>>64　続き

現実あり得そうな範囲で、僕に都合のいいことを考えるなら

将来、量子コンピュータに解読されない、大きな数を使った公開鍵暗号が発明され、最も低コストな公開鍵暗号となれば、うまくいけば永遠に「分割加算」が人類で使われる。

「分割加算」はGPUにも実装できるアルゴリズムで、特に、とてつもなく長い鍵長の演算ができるので、GPUを段階的なアクセラレータとして使えるメリットから、そういった新しい公開鍵暗号は、できるのかもしれない。

66 ：izuna五段(IWU)：2019/07/12 07:55:03 (5年前) 0MONA/0人

*************************************************
*************************************************
*************************************************
>>60 の方で50人となりました。
これで締め切らせていただきます。
お付き合いいただいたみなさん、AskMona管理の方々、ありがとうございました。
*************************************************
*************************************************
*************************************************

67 ：目指せ北海道三段錬士(IMJ)：2019/07/12 09:40:43 (5年前) 0MONA/0人

>>64
僕もまったく専門ではないのですが、qbitは複数の状態を持つことができるため、qbitを並べることで、とんでもない桁数のRSA演算ができるんじゃないかという感じ。ただそう感じただけなので、実現可能性どうこうはやってみないと分からないです。

68 ：izuna五段(IWU)：2019/07/12 10:37:01 (5年前) 0.00039MONA/1人

>>67
「とんでもない桁数のRSA演算」は、解読演算と解釈します。

ニュースで調べるだけでも、
qubitは、あまり長い時間、安定しない。
同時に解読できるだけのqbitを並べるのは、現時点では、難しい。

「とんでもない桁数のRSA演算」は、RSA演算と解釈します。
例えできても、量子コンピューターを使うより、FPGA/GPUを使ったほうが、圧倒的に安そうです。

69 ：izuna五段(IWU)：2019/08/12 23:27:56 (5年前) 0MONA/0人

ブログ書きました。

「わかりやすいICF3-Fのモンゴメリ乗算器の説明」

https://icf.hatenablog.com/entry/2019/08/12/230403

70 ：名無し二級(ZIA)：2019/08/15 11:35:32 (5年前) 0.1MONA/1人

読んだけどさっぱりわからん

71 ：zakuzaku三段錬士(AMZ)：2019/08/19 11:54:52 (5年前) 0MONA/0人

読んでみました
数式が何かもよく判りません
これが今後の仮想通貨に良い影響を
与えてくれることを願います

72 ：短歌ちゃん二段(VFR)：2019/08/22 01:02:10 (5年前) 0MONA/0人

読んだけど難しい

73 ：ずっき二級(SUO)：2019/08/22 21:10:17 (5年前) 0MONA/0人

読みみました。

74 ：ゴーヤ太郎二段(NOE)：2019/09/04 20:53:40 (5年前) 0MONA/0人

読みました！
難しくて分からなかったです。

75 ：名無し初段(RBC)：2019/09/10 18:16:39 (5年前) 0MONA/0人

読みました！
(全くわからない…)

76 ：タカシ二段錬士(VKH)：2019/11/16 17:34:07 (5年前) 0MONA/0人

こんばんは！
沢尻エリカです。

お気に入り

新規登録してMONAをもらえた

本サイトはAsk Mona 3.0に移行しましたが、登録すると昔のAsk Monaで遊ぶことができます。