wOOL's Blog

吐槽0：看毛片算法？

吐槽1：WP又被强奸了

吐槽2：大S呀，你说你诱惑我研究这个干虾米，我写出来自己都不想看第二遍。

建议去 http://docs.google.com/Doc?id=dm48v73_572gz954wdf 看，有比较好的效果

贴在这里的颜色信息和排版乱了不少

阅读更多 »

4月新番开播3周了, 原先打算看的14部作品中有3部放弃

1. 裸体环游世界

找不到片源, 汗…

2. 香格里拉

这动画, 貌似有点扯了吧, 无论画面还是剧情

3. 天堂餐馆

下了2集, 粗粗看了一下, 不合口味

剩余的11部打算全部追下去, 感觉这次4月番的质量还是蛮高的

1.女皇之刃

不解释, HKG的一句话:"肉片舍我其谁"

2.东之伊甸

女主角可爱, OP好听, 剧情有趣而且不像IG之前的作品那么涩

非常满意的一部

3.麻将少女

居然被麻将局看的我热血了, 百合萌

4.轻音乐少女

OP和ED都蛮好听的, 京都风依旧

5.机巧魔神

作画非常精致的一部动漫, 人物以MIMI见长, 剧情没新意, 但是冲着画面还是打算看了

6.潘多拉之心

剧情从第二集开始有点俗了, 但是人设比较成功, 作画比较仔细

7.Phantom

ED非常好听, 感觉比一般的黑帮片节奏慢, 但是这主要是为了刻画人物内心, 所以可以接受

打斗场面制作一般, 有邪恶镜头出现哈

8.BASQUASH

画风非常喜欢, 人物也超赞, 但是目前没看出什么明确的主线来

9.旋风管家II

算是没有比旋风管家I退步吧, 追这部主要是习惯了

10.钢之炼金术士

目前确认是漫画剧情了, 但是除了第一集, 后面连续的重制之前的部分, 还是有点没诚意

11.提亚拉之泪

勉勉强强, 作画挺认真地, 女主的性格是亮点, 这部也没看出主线来

同余, 费马小定理和RSA加密算法

今天从松鼠会上看到一篇关于这个的文章, 打算把其中关于数学的部分整理一下

预备知识1: 同余

首先是同余, 就是余数相同嘛, 这里指的是2个被除数被1个除数除, 得到的余数相等

那么牵扯到3个数字啦, 表示方法是高斯他老人家发明的

(≡是恒等号, 代表与变量无关, 比如f(x)≡0, x的取值对f(x)没有任何影响)

A ≡ B (mod C)

表示A和B在被C除的时候, 余数相同,比如

18 ≡ 25 (mod 7)

不难发现当B=0的时候表示的是A可以被C整除

18 ≡ 0 (mod 9)

而B<C的时候B就是A除以C的余数

18 ≡ 4 (mod 7)

MOD运算的一些规则可以WIKI去, 其推导还是比较简单的

预备知识2: 费马小定理

然后是费马小定理, 他指的是, a为整数, p为质数的时候, 有

a^p ≡ a (mod p)

费马小定理是欧拉函数的一个特例, 证明它的方法有很多, 这里写一个最容易理解的

首先我们可以把上式理解为a^p-a能被p整除

由a种字母的长度为p的单词有a^p种, 以由A和B这2种字母组成的长度为5的单词为例:

AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
ABAAA, ABAAB, ABABA, ABABB, ABBAA, ABBAB, ABBBA, ABBBB,
BAAAA, BAAAB, BAABA, BAABB, BABAA, BABAB, BABBA, BABBB,
BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB.

共有32种, 当我们移去其中只有1种字母组成的单词, 即AAAAA和BBBBBB, 剩余30个, 恰好可以被5整除, 为了说明这并非巧合, 我们考虑下面的陈述:

一个由若干个相同的, 长度为T的字母串组成的字符串, 它可以通过"换位"构成的全部的字符串的字符串数量为T

这里的"换位"是指将原字符串开头(或结束)的连续的部分移到字符串的结束(或开头), 例如:

字符串ABBABBABBABB是由3个字符组成的字符串(ABB)组成的, 如果我们把开头的A移到最后, 得到BBABBABBABBA, 如果我们把开头的AB移到最后, 得到BABBABBABBAB, 加上原字符串, 我们一共有:

ABBABBABBABB
BBABBABBABBA
BABBABBABBAB

这3种就是全部的情况了, 直观上这非常容易理解(如果我们把ABB移到最后得到的还是原字符串, 此后又开始循环)

那么回到那32个单词, 我们可以把它分成2类, 一类是只有1种字母构成的, 一类则不是

于是我们有

AAAAA,BBBBB.

AAAAB, AAABA, AABAA, ABAAA, BAAAA.
AAABB, AABBA, ABBAA, BBAAA, BAAAB,
AABAB, ABABA, BABAA, ABAAB, BAABA,
AABBB, ABBBA, BBBAA, BBAAB, BAABB,
ABABB, BABBA, ABBAB, BBABA, BABAB,
ABBBB, BBBBA, BBBAB, BBABB, BABBB,

我们可以在上面的排列中观察到第二类的每一行, 都可以由第一个字符串通过"换位"生成剩下的四个

显然第二类的数量为a^p-a个, 而由于p是个质数, 所以第二类中的所有字符串都不可以再分成"相同的部分"了, 即T就是整个字符串的长度, 即等于p, 那么通过"换位"构成的字符串就有p个, 所以第二类可以分成每组p个元素的小组, 所以a^p-a可以被p整除.

正菜: RSA加密算法

呼呼, 喝口水接着敲… 在完成这同余和费马小定理得知识准备后, 可以看看RSA加密算法了

RSA的准备可以分为3个步骤:

1. 寻找2个不同的大质数, p和q, 相乘得到N, 即N=pq

2. 寻找一个质数e, 其满足1<e<(p-1)(q-1)且与(p-1)(q-1)的公约数只有1(互质)

3. 找到一个数d, 其满足d和e的乘积除以(p-1)(q-1)的余数是1, 即de ≡ 1 (mod (p-1)(q-1))

我们将(e,N)称作Public key, (d,N)称作Private key. 前者是公开的,加密时使用;后者是私密的, 在解密时使用.

为了计算方便, 我们不使用大质数, 而是取p=2, q=5, N=10, (p-1)(q-1)=4, e=3, d=7

假设需要加密的内容转换成数字后是8, 我们把它记为s

加密过程:

1. 求s^e, 即8^3, 等于512

2. 求512除以N的余数, 等于2, 2就是加密后的数字, 我们把它记为c

解密过程:

1. 求c^d, 即2^7, 等于128

2. 求128除以N的余数, 等于8, 8就是我们的密码

原理:

用数学式子表示上述加密解密过程

1. s^e ≡ c (mod N)
2. c^d ≡ s (mod N)

我们需要证明在1成立的条件下, 2是成立的

首先把1中的c代入2, 得到我们需要证明的等价式子:

(s^e)^d ≡ s (mod N) 即 s^ed ≡ s (mod N)

由de ≡ 1 (mod (p-1)(q-1))可知

de ≡ 1 (mod (p-1))和de ≡ 1 (mod (q-1))

这里很容易理解, 既然de-1可以被(p-1)(q-1)整除, 那么它也一定可以被(p-1)或(q-1)整除

现在使用逆推法来证明下式成立

s^ed ≡ s (mod p)

<= s^(k(p-1)+1) ≡ s (mod p)      —这里因为de ≡ 1 (mod (p-1))所以可令de=k(p-1)+1

<= s^kp * s^(1-k) ≡ s (mod p)

<= s^kp ≡ s^k (mod p)      —这里同乘s^(k-1)

<= (s^k)^p ≡ s^k (mod p)

<= a^p ≡ a (mod p)      —这里令a=s^k

最后一个式子恰符合费马小定理的要求: a是整数, p是质数

同样的方法可以导出s^ed ≡ s (mod q)成立

由于p和q是两个不同的质数, s^ed – s可以被p整除, 也可以被q整除, 那么必定可以被pq(即N)整除

s^ed – s ≡ 0 (mod pq) 即 s^ed – s ≡ 0 (mod N) 即 s^ed ≡ s (mod N)

Q.E.D.

为什么那个是RSA比较安全的:

对于解密者而言, (d,N)是已知的, 所以可以通过简单的计算由c得到s. 而c即便在传递过程中被窃取人获得, 但是计算d的过程需要(p-1)(q-1), 显然还需要独立地知道p和q才可以, 而p和q是一个超级大数的唯一的2个质因子, 将2个大数相乘是简单的, 但是分解它们我们还没有找到暴力枚举外的合适的方法, 或许量子计算机可以处理这个问题可以, 但是, 它还没出现

~/.vimrc


set fileencoding=utf-8
//here is encoding of file
set fileencodings=ucs-bom,gb18030,utf-8,default
//here is the list for try


From http://vim.dindinx.net/orig/html/options.txt.php

Moved my anime list form Douban to Anime-Planet

刚刚在虚拟机中利用ARCH的FTP_ISO把GENTOO安装到EXT4分区中，步骤之后整理

贴个图。。。

灰常有兴趣滴：

裸体环游世界365天
网络播放，每集5分钟，貌似很有趣滴
女皇之刃 流浪的战士
2009年4月2日 早晨8点 AT-X （周四）
这。。。HKG在第一集的片头提到：肉片舍我其谁，那是相当的恰当
第一集就肉肉露露，MM摇摇
声U阵容有 川澄綾子 能登麻美子 平野綾 釘宮理恵 — 这是何等的。。。。哈喇子
机巧魔神
2009年4月2日 早晨09:30 （周四）
看介绍应该是一部轻松搞笑的片子，海报给我魔法学院WA的感觉
BASQUASH
2009年4月3日 凌晨01:25 （周五）
看动新的介绍，蛮喜欢它的画面的，而且设定比较有趣
MF系列的监督河森正治应该能保证质量
轻音乐少女
2009年4月3日 凌晨01:59 （周五）
这部作品还没透露的时候曾经被怀疑是凉宫2，京都呀京都，你的坑何时填呢？
不过看海报蛮喜欢那只LOLI的
而且这个题材之前没有看过，尝试一下～
旋风管家第二期
2009年4月4日 凌晨01:23 （周六）
这。。。我不没有钉宫病，我没有钉宫病。没有。。。没有
钢炼金术师
2009年4月5日 下午5点 （周日）
据说是根据原作漫画来的，虽然漫画我没有追，但是钢炼在我看过的260余部动漫中至少是前10%级别的
仍旧由骨头社这个动漫界的暴雪承担制作，放心～
天才麻将少女
2009年4月6日 凌晨2点 （周一）
竹刀是可以拍动画滴，麻将也可以
以包子脸的名义——胡～

有点兴趣滴：
潘朵拉之心
2009年4月3日 凌晨01:30 TBS （周五）
海报：男人，女人和小受～
Phantom～Requiem for the Phantom～
2009年4月2日 凌晨01:30 （周四）
感觉剧情比较黑暗，然后很久没看比较黑暗的剧情的动画了
留意一下
香格里拉
2009年4月6日 凌晨01:15 （周一）
GONZO的作品，被那个MM吸引了一下下
提亚拉之泪/Tears to Tiara
2009年4月6日 凌晨01:30 （周一）
感觉剧情和设定有些俗，但是画面从海报上看还是灰常有爱的
天堂餐馆
2009年4月9日 凌晨02:08 （周四）
《道子与哈金》收了，还没看，这部也有点兴趣
东之伊甸
2009年4月10日 凌晨01:30 （周五）
只是冲着Production I.G去的

——————————–
除掉钢炼和机巧魔神，全部都是深夜档
女皇之刃虽然不是深夜档，但是。。。
难道？
嘛萨咔？
我真的邪恶了？