2017q3 Homework1 (ternary)

contributed by <Yuessiah, HexRabbit^[1]>

本文件多處地方採用超連結來補完報告，建議點開來看

Reviewed byvonchuang

• "IOTA 的加密並非基於 ECC[5]，而是使用一個基於三進制 hash function，名為 Curl"，應找出程式碼應證，而非只用引用 IOTA 在 Blog 中關於 Curl 的介紹
• "Setun: 1 tryte = 6 trits
  IOTA: 1 tryte = 3 trits
  官方用[9A-Z]表示該 tryte 位置 trits 的模樣
  Others: 1 tryte = 9 tries"，可找出程式碼應證，如iota/iri/utils/Converter.java
• 在 Radix Econemy，在描述上可再更詳盡些

關於 Radix Econemy 早有引用的文章連結了，想要更詳盡的定義直接點開看即可。
"Yuessiah"

---

Balanced Ternary

簡介

Balanced ternary 是個特別的三進制數字系統，
其一個位置稱作 trit，一個 trit 有

$(+,-,0)$ 或

$(1,T,0)$ 表示
符號

$+,1$ 代表數字

$1$
符號

$-,T$ 代表數字

$-1$
符號

$0$ 代表數字

$0$

Perhaps the prettiest number system of all… is the balanced ternary notation
— Donald Knuth, The Art of Programming

四則運算

• 加法

$+$	$T$	$0$	$1$
$T$	$T1$	$T$	$0$
$0$	$T$	$0$	$1$
$1$	$0$	$1$	$1T$

• 減法

$-$	$T$	$0$	$1$
$T$	$0$	$T$	$T1$
$0$	$1$	$0$	$T$
$1$	$1T$	$1$	$0$

• 乘法

$\times$	$T$	$0$	$1$
$T$	$1$	$0$	$T$
$0$	$0$	$0$	$0$
$1$	$T$	$0$	$1$

• 除法

$÷$	$T$	$0$	$1$
$T$	$1$	$NaN$	$T$
$0$	$0$	$NaN$	$0$
$1$	$T$	$NaN$	$1$

平衡 3 進制到 10 進制轉換

數字與中文字間記得也要用空白隔開！
課程助教

好ㄛ
Yuessiah

操作與其他整數進制系統到 10 進制一樣
例如：

$10T1=3^0\times 1+3^1\times (-1)+3^2\times 0+3^3\times 1$

10 進制到平衡 3 進制轉換

例如：

$20.6$

將整數與小數分離

$20.6=20+0.6$

• 整數部
  

  $20÷3=6...2$
  
  $6÷3=2...0$
  
  $2÷3=0...2$
  由餘數部份得知整數部為
  $001T+0000+1T00=1T1T$

• 小數部
  

  $+0.6=1-0.4$
  
  $-0.4\times 3=-1-0.2$
  
  $-0.2\times 3=-1+0.4$
  
  $+0.4\times 3=+1+0.2$
  
  $+0.2\times 3=+1-0.4$ (此後循環)
  由整數部份得知小數部為
  $1.TT11TT11TT11...$

正負數

由維基百科^[2]上知道第一位為

$1$ 為正數，若為

$T$ 則為負數

• 正數
  設一數字 A 第一位為
  $1$ 其餘為任意符號
  $(1,T,0)$，顯然其餘的符號都為
  $T$ 時，此數字 A 最小，
  設 A 的長度為
  $N＋1$，將 A 轉為十進制：
  
  $$1TTT...T=3^N\times 1＋\frac{3^N-1}{3-1}\times (-1)>0$$
• 負數
  由上述正數之證明方法，也可證明負數的表示法

使用同樣的思考方式，也能引出比大小的運算

tryte?

tryte 就如同 byte 表達的意義
1 byte 為一組 8 bits

而 1 tryte 則沒有一個統一的標準 (不過還是有這樣的詞😕

• Setun: 1 tryte = 6 trits
• IOTA: 1 tryte = 3 trits
  官方用[9A-Z]表示該 tryte 位置 trits 的模樣
• Others: 1 tryte = 9 tries

Radix Econemy

根據定義^[3]

$E(b,N)=b÷(lo{g}_{b}N＋1)$
對

$E(b,N)$ 求導得知

$b=e$ 有最小值
可得知在扣除易於表達( 2 進制)的特性，3 進制系統在資訊傳遞上是優於其他整數進制的，因為整數集合中 3 最接近 e

b3k 討論

• 突出

├───┐  每一突出代表一 3 的 n 次方, 且為正數
│   │  從正下方開始 n=0，逆時針一圈數過去，兩相鄰突出相差 1, 後數的大於前一數
└───┘  例如左圖為 3^3

• 內縮

┌┬──┐  與突出相似，但內縮為負數
│   │  例如左圖為 -3^3
└───┘

• 最大上界 3280

├─┴─┤  仔細觀察可知，一根突出的線可代表一個累加次方
┤   ├  共有 8 根，於是計算出最大上界為 (3^8-1)/2
├─┬─┤  式子意義：可類比成將 8 個位置的普通三進制數全部填 1 (i.e. 11111111)

詳細閱讀程式碼後發現有個地方不太尋常

digit[SZD] = {
	{ 32, 3 },
	{ 26, 6 },
	{ 16, 8 },
	{ 0, 6 },
	{ 6, 3 },
	{ 9, 7 },
	{ 21, 5 },
	{ 35, 7 }
};

把 len 加一加，理論上要得到 42，卻得到了 45
為了方便除錯，把 pat 裡面的值都印出來

i =  0, {-30, -108, -116}
i =  3, {-30, -108, -128}
i =  6, {-30, -108, -128}
i =  9, {-30, -108, -128}
i = 12, {-30, -108, -112}
i = 15, {10}
i = 16, {-30, -108, -126}
i = 19, {32}
i = 20, {32}
i = 21, {32}
i = 22, {-30, -108, -126}
i = 25, {10}
i = 26, {-30, -108, -108}
i = 29, {-30, -108, -128}
i = 32, {-30, -108, -128}
i = 35, {-30, -108, -128}
i = 38, {-30, -108, -104}
i = 41, {10}
---
i =  0, {-30, -108, -100}
i =  3, {-30, -108, -128}
i =  6, {-30, -108, -76}
i =  9, {-30, -108, -128}
i = 12, {-30, -108, -92}
i = 15, {10}
i = 16, {-30, -108, -92}
i = 19, {32}
i = 20, {32}
i = 21, {32}
i = 22, {-30, -108, -100}
i = 25, {10}
i = 26, {-30, -108, -100}
i = 29, {-30, -108, -128}
i = 32, {-30, -108, -84}
i = 35, {-30, -108, -128}
i = 38, {-30, -108, -92}
i = 41, {10}
---
i =  0, {-30, -108, -116}
i =  3, {-30, -108, -84}
i =  6, {-30, -108, -84}
i =  9, {-30, -108, -84}
i = 12, {-30, -108, -112}
i = 15, {10}
i = 16, {-30, -108, -100}
i = 19, {32}
i = 20, {32}
i = 21, {32}
i = 22, {-30, -108, -92}
i = 25, {10}
i = 26, {-30, -108, -108}
i = 29, {-30, -108, -76}
i = 32, {-30, -108, -76}
i = 35, {-30, -108, -76}
i = 38, {-30, -108, -104}
i = 41, {10}

可以發現digit[2]有些小問題
如果 len 為 8，那麼在/* Show the result. */會把i = 22後前兩個字元也複製下，
len 改成 5 或許比較合理。

不過因為/* Show the result. */這邊是從 0 到 SZD-1，貌似結果上不會產生問題(?

1. 換個角度思考，給定的 k3b 程式需要做哪些更動，才符合期望呢？
2. 如果我們需要大於 (十進位的) 3280 當作新的合法輸入範圍，該修改哪些程式段落呢？

jserv

實際用途

IOTA^[4] 的安全性

IOTA 的加密並非基於 ECC^[5]，而是使用一個基於三進制 hash function，名為 Curl
Curl 可以防止量子電腦^[6]破解密碼。

As IOTA was the first distributed ledger project that took the inevitable threat of scalable quantum computers seriously, we had to move away from standard elliptic curve cryptography. A few months later NSA validated our concerns by announcing official concern over the ‘quantum threat’. Since then there has been numerous quantum leaps in quantum computing, further validating this engineering decision we made. Beyond this concern we also had to follow a path that is optimized for the future landscape of Internet of Things. Curl is a new kind of hash function optimized precisely for these two things, it is based on well-studied sponge construction invented by the Keccak creators (SHA-3) and strictly conforms to all requirements described in their official paper. ^[7]

1. Curl hash function 已過時，請改用 Kerl
2. 論述不足以涵蓋數值系統和 Keccak 特性

jserv

---

1. 本共筆是與HexRabbit共同研究得以撰寫而成 ↩︎

2. Wikipedia/ Balanced ternary ↩︎

3. 数学趣谈 三生万物/ Radix Economy ↩︎

4. iotachina.com/ IOTA介绍 ↩︎

5. Wikipedia/ Elliptic-curve cryptography
   ↩︎

6. Wikipedia/ Quantum computing
   ↩︎

7. blog.iota.org/ The Transparency Compendium
   ↩︎