分类： 未分类

国内运行coder的坑

https://github.com/coder/coder

git clone && cd coder

在docker-compose.yaml中给postgres增加privileged: true，防止数据库出错

export CODER_ACCESS_URL=http://YOUR_IP:7080

docker-compose up

启动后注册

找个客户端安装coder的cli后按https://coder.com/docs/coder-oss/latest/templates创建模板

先用bare测试，执行coder template create后会报错

bare的模板上传后会报错，进容器

ps aux 可以看到执行了 /tmp/coder-cache/terraform init -no-color -input=false

通过ps aux获取PID后执行 ls -hal $PID/cwd

可以看到在provisionerd开头的文件夹下有客户端上传的文件，趁着失败之前复制走好手动测试

可以看到国内的网络执行terraform init一定会卡，fuck

参考这些尝试中

https://cloud.tencent.com/developer/article/1987762

https://developer.aliyun.com/article/713099

https://developer.aliyun.com/article/723935

 

coder实现了terraform的provider，来管理自己的资源

https://github.com/coder/terraform-provider-coder

20220731lamda表达式中的方法调用识别

psi过滤直接用JavaRecursiveElementVisitor过滤PsiMethodCallExpression会发现只识别到了collect的调用

因为JavaRecursiveElementVisitor的逻辑是当一个节点满足要求后，下一个继续的节点是nextSibing

因此需要增加特殊逻辑，当第一层PsiMethodCallExpression被匹配到后，需要递归在PsiReferenceExpression继续寻找，需要把PsiReferenceExpression+PsiReferenceParameterList中的lamda表达式以及其中的方法调用和方法引用都找出来，这里只写方法调用，方法引用也是一样的套路

 

不知道jetbrains有没有类似的工具类做这种深度搜索，代码太多了懒得看，就先这么写着，附语义树如下

完整代码，更新中

20220721数据库基础-谓词逻辑转写sql

20220721数据库原理
同事在学数据库，问我这个题，重新总结下我上学时候的经典套路
这个套路针对任意存在性和任意性判定的sql编写或集合运算，当时数据库老师疯狂改题目条件，导致sql毫无规律且从字面含义上难以正向理解运算逻辑。为了考试以不变应万变总结了这个套路，核心思想是不要纠结于最终sql的语法表达，而是通过逻辑化简来确保集合元素的正确性，化简后再转写成sql
主要运用集合论、关系代数基础以及离散数学的谓词逻辑，这些应该是我要做sql自动生成和优化的理论基础
题目经典的三张表如下
学生表s(sid,sname)
课程表c(cid,cname)
选课关系表sc(scid,sid,cid)
求至少学过lz同学学过所有课程的同学的学号
编写过程如下
首先做形式化表达和逻辑化简,原则：逻辑取反极可能少，尽可能使用存在性判断
谓词逻辑定义f(x,y) = 学生x选择了课程y
{x|对任意y,f(lz,y)->f(x,y)}
–逆否命题
{x|!(存在y,!(f(lz,y) -> f(x,y)))}
–蕴含等值 p->q === !p||q
{x|!(存在y,!(!f(lz,y) || f(x,y)))}
{x|对任意x,!(存在y,!(!f(lz,y) || f(x,y)))}
–等价替换
{x|!(存在y,(f(lz,y) && !f(x,y)))}
{x|对任意x,!(存在y,(f(lz,y) && !f(x,y)))}
–对任意x
select sc.sid from sc where 1=1
— f(x,y)
exists (
    select * from sc where sc.sid = x and sc.cid = y
)
— f(lz,y)
exists (
    select * from sc where sc.sid = ‘lz’ and sc.cid = y
)
— 存在y, (f(lz,y) && !f(x,y))
exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
    select sc1.cid from sc sc1 where exists (
        select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid –f(lz,y)
    )
    and not exists ( –!f(x,y)
        select * from sc sc3 where sc3.sid = x and sc3.cid = sc1.cid
    )
)
— 对任意x, 取x = sc0.sid
select * from sc sc0 where not exists (
    select sc1.cid from sc sc1 where exists (
        select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid
    )
    and not exists (
        select * from sc sc3 where sc3.sid = sc0.sid and sc3.cid = sc1.cid
    )
)
— 从来没有人告诉我存在这样一个化简的过程，这个方法多年间也未曾见到有人和我讲过，以上中间过程我翻遍了互联网也没找到。这是我上学时候应对考试用的通解套路，工作后好久没这么详细的写过sql转写了，简单的业务都是直接写sql结果而快忘却了正确的通解解法
— 在exists内select sc1.cid和select *是一样的，判定结果只看行数，但语义完全不一样，如果是从谓词逻辑转来的不应该都是*
— 另外，从exists子句转为where子句是容易的，反过来理论上也一样，但网上的所谓教程根本不会讲这个是怎么来的
— 因子句存在永真式sc1.cid = sc1.cid 且 存在性判定可由where条件代替一次子查询
— 所以接下来才是你在网上轻易看到的答案格式，也就是课本或老师PPT给的的答案
exists (– y sc1.cid
    select sc1.cid from sc sc1 where sc1.sid = ‘lz’ and sc1.cid = sc1.cid –f(lz,y)
    and not exists ( — !f(x,y)
        select * from sc sc2 where sc2.sid = x and sc2.cid = sc1.cid
    )
)
–投影输出结果
select sc0.sid from sc sc0 where not exists (
     select sc1.cid from sc sc1 where sc1.sid = ‘lz’ and not exists (
        select * from sc sc2 where sc2.cid = sc1.cid and sc0.sid = sc2.sid
    )
)
–等价答案
— {x|对任意x,!(存在y,!(!f(lz,y) || f(x,y)))}
exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
    select sc1.cid from sc sc1 where not(
        not exists (
            select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid –f(lz,y)
        )
        or
        exists ( –f(x,y)
            select * from sc sc3 where sc3.sid = x and sc3.cid = sc1.cid
        )
    )
)
— 对任意x, 取x = sc0.sid
select * from sc sc0 where not (
    exists (– 存在y, 取y = sc1.cid  看作是定值，但要注意给表加别名
        select sc1.cid from sc sc1 where not (
            not exists (
                select * from sc sc2 where sc2.sid = ‘lz’ and sc2.cid = sc1.cid — f(lz,y)
            )
            or
            exists ( — f(x,y)
                select * from sc sc3 where sc3.sid = sc0.sid and sc3.cid = sc1.cid
            )
        )
    )
)
— 投影输出略
— 语义分析
sc0.sid = sc2.sid的子查询条件字面意义上是扫描了sc的每一行来分别做两次集合的存在性判定
第1行数据执行
id sid cid
sc0 1 lz 1
select sc0.sid from sc sc0 where not exists (
    select * from sc sc1 where sc1.sid = ‘lz’ and not exists (
        select * from sc sc2 where sc2.cid = 1 and ‘lz’ = sc2.sid
    )
)
select sc0.sid from sc sc0 where not exists (
    select * from sc sc1 where sc1.sid = ‘lz’ and not true
)
select sc0.sid from sc sc0 where not exists (
    empty
)
select sc0.sid from sc sc0 where true
1 lz 1输出
CREATE DATABASE test;
use test;
CREATE TABLE sc (
    id int(11) PRIMARY KEY NOT NULL AUTO_INCREMENT,
    sid varchar(255),
    cid varchar(255)
);
INSERT INTO sc(sid,cid) VALUES
('lz', '1'),
('lz', '2'),
('a', '1'),
('b', '2'),
('c', '1'),
('c', '2'),
('c', '3')
;
SELECT * FROM sc;
+----+------+------+
| id | sid  | cid  |
+----+------+------+
|  1 | lz   | 1    |
|  2 | lz   | 2    |
|  3 | a    | 1    |
|  4 | b    | 2    |
|  5 | c    | 1    |
|  6 | c    | 2    |
|  7 | c    | 3    |
+----+------+------+
7 rows in set (0.00 sec)

20220628编译原理读书笔记

 

 

 

 

20220628编译原理读书笔记

2.5 上下文无关文法及其语法树

给定文法G=(Vn,Vt,P,S)
语法树又称推导树，定义：
1.每个节点都有一个标记属于V
2.根节点是S
3.若一个节点n至少有一个它自己除外的子孙A，则A肯定属于Vn
4.若节点n的直接子孙从左到右为n1,n2,…n，则n=>n1,n2,…n是P中的产生式

推导过程不唯一
若每一步都是对左部最左的Vn替换则称为最左推导，反之是最右推导
形式语言中最右推导被叫做规范推导，所得句型叫规范句型或最右句型

若一个文法存在多个语法树，则称这个文法是二义的
判定给定的上下文无关文法是否是二义的，或它是否产生一个先天二义的语言，这两个问题递归不可解

2.6 句型分析

自顶向下、自底向上

3 词法分析

虽然词法和语法可以同时放到文法描述里，但一半实现时候都是独立做词法分析

常见分类
标识符、字母数字、整数、运算符、等号、界符

正则表达式可以方便的描述词法规则，且正则表达式和正规文法都能定义语言，且有时候表达更加方便

如
A->xB,B->y => A = xy
A->xA|y => A = x*y
A->x, A->y => A = x|y

3.4 有穷自动机

确定的有穷自动机DFA,不确定的有穷自动机NFA
M=(K,M,f,S,Z)
K:有穷状态集
M:有穷字母表
f:转换函数，是K和M的笛卡尔积到K上的映像，用来定义状态转换条件
S:唯一的初态
Z:终态集合，是K的真子集

这里歪个楼，画状态转换图一定要有这几个元素，工作这么久很少见有人完全画对。初始要有一个箭头指向S，Z上的元素要有双层圈标记，每个线段代表转换规则，线上要有M元素的标记

NFA区别就是转换函数在特定状态上可以不唯一
NFA有算法可以转DFA，核心思想是构造确定性的子集

DFA化简，计算入度为0的状态可删除、计算等价状态合并多余的状态

3.5 正则表达式和有穷自动机的等价性

结论是等价，证明略，因此用正则表达式可以直接描述状态机，状态机的实现可由特定算法自动生成结构完整

3.6 正规文法和有穷自动机的等价性

结论是等价的，证明略，经过前面的铺垫，为自动化打下了良好的理论基础

3.7 词法分析器的自动构造工具

这可能是正常途径下接触到的第一个元编程吧。。。。
由前面的铺垫可知，既然等价，那就可以直接用程序生成程序，人工提供规则即可

这里歪个楼介绍下正则表达式基础，其实如果你手写练习过一些正规文法的生成式，就知道正则表达式多简洁了。因为这个概念是数学集合论的，因此正则表达式的写法也和集合闭包几乎一样，掌握基础并不困难

r* 匹配r的星闭包，r出现0次到多次
r+ 匹配r的正闭包，r出现1次到多次
r? 匹配r的任选，r出现0次或1次
r{n} 匹配r的n次幂，r出现n次
r{m,n} 匹配r的m到n次幂，r出现m次到n次闭区间
r{m,} 匹配r的m次幂以上，r出现m次以上闭区间
rs 匹配r和s的连接
r|s 匹配r和s的并集
其余写法均为简写，常见的就这几个

借助lex描述文件可以目标结构的c语言代码，完成词法分析器的自动生成
类似的工具不唯一，可以看看antlr

第4章到第6章都是语法分析的各种方法，有点懒得看了，总之结果是个语法树
我关心的是第7章语法制导的语义计算
也许是明天继续？
mark当前68页

 

20220622编译原理读书笔记

 

 

 

20220622编译原理读书笔记

1.引论

基础知识和概念，不细说
编译程序的定义：语言翻译程序
编译程序的功能：源语言程序翻译为目标语言的等价程序的程序（按这个定义是不是能算元程序了hhhh生成程序的程序）

编译过程：
词法分析：源程序->单词（符号、单词符号、token）序列
语法分析：token序列->语法树
语义分析：语法树->语义树、图 这个阶段才有类型检查
中间代码生成：就是字面意思
代码优化：无效代码删除、优化
目标代码生成：翻译到目标语言

前端：到中间代码之前的部分，与目标语言和平台无关
后端：中间代码到目标代码的部分，与源语言和平台无关
编译过程可以是一遍或多遍扫描源码完成

解释执行和编译执行
解释执行不需要完整的源码，编译执行需要完整编译后才能运行

EBNF：扩展的巴克斯范式

练习题
else没有匹配的if，语法分析阶段检查
数组下标越界，语义分析阶段检查或代码生成阶段，甚至运行时才知道
使用的函数没有定义，语义分析阶段检查
数中出现非数字字符，词法分析阶段检查

2.文法和语言

程序设计语言是记号系统，完整定义包含语法和语义

语法只定义怎么写，不管含义例如a=b+c是合法的表达式，但如果c未定义，语法检查是检查不出来的
语义分为
静态语义：类型匹配检查，在满足语法限定的情况下，什么样的写法是合法的
动态语义：变量作用域检查，表明程序要做什么

文法：用来定义语法的工具
语义：目前（书上说没有，实际不知道）没有公认的形式系统可以用来自动构造正确的编译系统
形式语义学：这个可以再查查资料，对这个比较好奇，这本书居然不讲

文法：用有穷规则集合表示句子的无穷集合，描述语言的语言，所以也叫元语言
规则：左侧符号=>右侧符号序列，=>表示使用左侧符号可以产生右侧符号

字母表：符号组成的集合，所以也叫符号集，这里的符号层次就是字母、数字、标点之类的类型，不是token.符号这个词的含义在不同语境下会容易混淆，因此尽量避免，一般意思是token
符号串：有穷的符号序列，允许为空

表示法
若符号串x中有m个符号，则|x|=m
连接，x=臻臻,y=真厉害,xy=臻臻真厉害
方幂，x=臻ab,x^0=空,x^2=臻ab臻ab
符号串集合:乘积定义为两个集合元素的连接运算，区分先
对字母表C，C的闭包表示C上有穷长串的集合，也就是C^0∪C^1...C^n
排除C^0后的集合称为正闭包

2.3 形式定义

规则又称重写规则、产生式、生成式
写作A::=B或A=>B，A是左部，B是右部

文法G定义为(Vn,Vt,P,S)
Vn:非终结符(语法实体、变量)集合, 这里的符说的是抽象定义，也就是终结符有限集的划分
Vt:终结符集合，注意这里的符是字母那个层次的
P:规则集
S:识别符、开始符

因此这里的文法主要是词法分析使用，最终Vn的闭包将作为产物给语法分析（上学时候就糊涂，希望这次没说错

2.4 文法类型

文法G定义为(Vn,Vt,P,S), 产生式为a=>b
0型:a和b均属于V=Vn∪Vt的闭包 且a至少含有一个非终结符
特性：递归可枚举、能力等价于图灵机
1型：上下文有关，除S->空以外，|b|>=|a|。
另一种描述 aBc=>aDc(D不为空)，更能描述上下文，仅B出现在ac这种上下文时才能替换成D
2型：上下文无关，a是非终结符，b属于V的闭包
另一种描述 A=>B,A属于Vn，也就是取代A的时候无需关心A的上下文
3型：正规文法，产生式形如A=>aB或A=>a，A,B属于Vn，a属于Vt的闭包

定义限制是逐层增加的，因此满足3型的一定满足2、1、0
上下文无关说的是生成式看起来上下文无关，所以实际上上下文无关文法都是上下文有关的hhhh

例如C → a b 这条规则将一个单独的非终端符 C 变换为两个连续的终端符 “a b”
“a b” 这个序列能出现在什么位置是由右部出现 C 的其他规则决定的，只能出现在特定的上下文中，因此是上下文有关的。

明天继续2.5语法树
往后翻了翻终于知道为啥上学的时候糊涂了，第二章讲完了文法，第三章退回到词法了，所以概念理解上很容易乱
mark当前26页

 

20220621现代密码学读书笔记

 

 

 

20220621现代密码学读书笔记

4.2 公钥密码体制基本概念

公钥密码之前的基础操作是代换和置换
公钥密码使用数学函数

4.2.1 原理

使用两个密钥分离加密和解密能力，一个公钥一个私钥
加密：公钥加密私钥解密
认证：私钥加密(签名)，公钥解密(验签)

4.2.2 算法要求

1.接收方B产生密钥对在计算上是容易的
2.发送方A用接收方B的公钥对消息m加密产生密文c=encrypt(pkb,m)在计算上是容易的,其中pkb为B的公钥
3.接收方B用私钥对c解密成m=decrypt(skb,c)在计算上是容易的,其中skb为B的私钥
4.敌人由pkb计算skb在计算上是不可行的
5.敌人由c和pkb恢复明文m在计算上是不可行的
6.加解密次序可交换 这条虽然有用但不是强制要求

单向陷门函数是一簇可逆函数y=fk(x)，满足:
1.当已知k和x时，计算y容易
2.当已知k和y时，计算x容易
3.当已知y但未知k时，求x是不可行的

4.2.3 攻击方法

穷举
可能字攻击：若传递数据长度可穷举则穷举明文对比密文

4.3 RSA 算法

4.3.1 算法描述

1.选取保密大质数p,q
2.计算n=q * q, f(n) = (p-1)(q-1) 其中fn是欧拉函数
3.选取整数e，满足1 < e < f(n)且gcd(f(n),e)=1
4.计算d, 满足d * e === 1 mod f(n),d是e在模f(n)下的逆元
5.{e,n}作为公钥,{d,n}作为私钥

加密过程为计算c === m^e mod n
解密过程为计算m === c^d mod n

因构造的e和d互质，且n为素数，由之前的数学铺垫可知在模n下有
c === m^e -> c^d === m ^ ed === m ^(k*f(n) + 1) === m
说实话最后一步略绕，但懒得分析了。。。总之这是数学规律

4.3.2 RSA的计算问题

加解密过程因大指数的幂次容易越界，因此可以用模运算性质缩小计算规模
平方和快速算法优化，x^16 == x^2 ^2 ^2 ^2，减小为4次乘法
pqed的计算均有技巧，此处略

4.3.3 中国剩余定理加速

通过中国剩余定理可代换中间结果，快速计算明文

4.3.4 RSA安全性

假定的是分解大质数是困难的问题，但随着算力的增强，这个速度在逐渐的被计算机暴力的解决
但密钥长度足够大的话目前的计算机还无法快速计算完成

4.4 背包密码

给出一组正整数ai，和一个整数s，求解ai中的子集的和为s
同理，已知ai子集好求s，但已知s难以反向求ai

4.5 Rabin密码

RSA的难度普遍认为和分解大质数相等，但实际上知识小于或等于大质数分解
而Rabin可被证明难度等价于分解大指数

1.对于同一密文可能有两个以上对应的明文
2.修改RSA中的e=2

密钥产生, 大质数p,q满足p===q===3mod4, n = p * q,n为公钥,pq为密钥
加密，c === m ^ 2 mod n
解密，求解x ^ 2 === c mod n ，套中国剩余定理的结论

4.6 NTRU公钥密码

基于整系数多项式的环，在环上的系数相关运算封闭且有数学规律

4.7 椭圆曲线

4.7.1 连续域

ECC是Elliptic Curve Cryptography的简写
定义在椭圆曲线方程上的运算
无穷远定义为O，定义为单位元
加法逆元定义为P2=-P1关于X轴对称，因此当P1P2共线时P1+P2==O
加法定义Q+R：QR为横坐标不同的两点，做直线QR交f(x)于P1(当切线时取P1=Q=R)
因Q+R+P1=O，因此Q+R=-P1，也就是关于P1沿x轴翻转后的点
切线特殊情况：也就是Q的倍数运算,直接取在Q的切线上的交点沿x轴翻转后的点

4.7.2 离散域

椭圆曲线方程的系数取于GF(p)，其中p为大质数

4.7.3 点数

计算离散域方程的线上有多少离散点，有公式

4.7.4 明文消息嵌入椭圆曲线

对任意m计算mk+j，直到x^3 + ax + bmodp是平方根，即得到(x,sqrt(x^3 + ax + b))
解密只需要x/30向下取整即可

4.7.5 椭圆曲线上的密码

椭圆曲线上的困难问题,群上的点和特殊运算构成Abel群Ep(a,b)
考虑Q=kP，已知k和P的情况下，也就算点P的切线与fx的交点关于x轴翻转易求，k是多次也迭代易求
反之已知PQ则难以确定k

注意：这个离散对数困难问题可应用于任何基于有限域离散对数原理的密码体制

DF密钥交换协议
GElGamal密码体制

4.8基于身份的密码体制

不是我关心的内容，略

明天不继续了。。。到此为止已经解决了我对ECC和RSA的疑惑了，后续内容有缘再见了hhhh
mark当前117页
实在是太南了，我宁愿去看概率论和AI基础也不想看离散数学了，因此离散数学那本书我放弃了
下一本书是编译原理。。。。

 

20220616现代密码学读书笔记

 

 

20220616现代密码学读书笔记

4.1.9 离散对数

如果a的阶m等于φ(n)，则称a为n的本原根（生成元）
若p是质数，a是p的本原根，则a, a*a, a*a*a,...a^(p-1)的结果是1~(p-1)之间互不相同的所有值，因此对任意的1<=b<=p-1都存在唯一的1<=i<=p-1使得b===a^i mod p。
称i为模p下以a为底的指标，记为i=ind(a,p,b)，也就是离散对数

性质 ind(a,p,1)=0, ind(a,p,a)=1
显然易证：a^0 mod p == 1 mod p == 1, a^1 mod p == a

若a^z === a^q mod p 则z===q mod φ(p)

4.1.10 平方剩余

n是正整数,a是整数,满足gcd(a,n)=1,称a是模n的平方剩余，反之若x * x === a mod n有解则称为非平方剩余

显然若p是质数则模p的平方剩余个数为(p-1)/2, 且与模p的非平凡剩余相等。
若a是模p的平方剩余则a的两个平方根0<=x1<=(p-1)/2, (p-1)/2+1<=x2<=(p-1),且x1或x2之一也是模p的平方剩余

legendre函数定义
p是质数,a是整数
若a被p整除,p|a则legendre(a,p)=0
若a是模p的平方剩余则legendre(a,p)=1
若a是模p的非平方剩余则legendre(a,p)=-1

公式 legendre(a,p) === a^((p-1)/2) mod p
性质,当p是奇素数且a,b都不能被p整除时
a === b mod p 则 legendre(a,p) = legendre(b,p)
legendre(a*b,p) = legendre(a,p) * legendre(b,p)
legendre(a*a,p) = 1
legendre(a+p,p) = legendre(a,p)

设n是正整数,当n表示为质因子的幂乘积的形式p1^a1 * p2^a2 * ... pk^ak时
定义Jacobi(a,n) = legendre(a,p1) ^ a1 * legendre(a,p2) ^ a2 * legendre(a,pk) ^ ak

jacobi性质如下
当n是正合数,a,b与n互质时
a === b mod n 则 jacobi(a,n) = jacobi(b,n)
jacobi(a*b,n) = jacobi(a,n) * jacobi(b,n)
jacobi(a*b*b,n) = jacobi(a,n)
jacobi(a+n,n) = jacobi(a,n)
jacobi(1,n)=1, jacobi(-1,n)=(-1)^((n-1)/2), jacobi(2,n)=(-1)^((n^2-1)/8)

当m,n为大于2的奇数时
jacobi(m,n) = -1 ^ (((m-1)(n-1))/4) * jacobi(n,m)
易得当m===n===3 mod 4时 jacobi(m,n) = -jacobi(n,m)
否则jacobi(m,n)=jacobi(n,m)

综上所述计算jacobi不需要质因式分解,所以当计算legendre时可以先当作jacobi计算，如果有必要，计算jacobi(m,n)时可以通过m mod n 代替m，利用mn交换位置可以减小其中的一个数

jacobi和legendre的本质区别就是jacobi不表示平方剩余方程是否有解

设n为两个大质数p * q的积
由上面的结论可知1 ~ p-1的一半是模p的平方剩余，集合记为P,另一半记为NP
由上面的结论可知1 ~ q-1的一半是模q的平方剩余，集合记为Q,另一半记为NQ
而n的平方剩余a必须同时满足n是模p的平方剩余且a是模q的平方剩余, a属于P∩Q
所以与n互质小于n的a，有一半满足jacobi(a,n)=1记为c，另一半满足jacobi(a,n)=-1记为d
c可能属于P∩Q或NP∩NQ，d可能属于P∩NQ或NP∩Q
同理c中也有一半满足jacobi(a,p)=jacobi(a,q)=1的 a属于P∩Q 这些a就是n的平方剩余
c中剩下一半满足jacobi(a,p)=jacobi(a,q)=-1的 a属于NP∩NQ 这些a不是n的平方剩余

综上当p===q===3 mod 4 时,
由中国剩余定理可快速求出 x === y,-y mod p, x === z, -z mod q
反过来若已知四个中两个不同的根，就可快速的分解大整数n
jacobi(y,n) = -jacobi(z,n) 证明略

4.1.11 计算复杂度

这个数据结构里提过了，这里不赘述
若算法时间复杂度为多项式复杂度，就说这个算法是有效的，反之如果是指数复杂度则称之为无效

若问题存在多项式复杂度的算法可解，则称问题为P问题，也称之为计算可行的
NP问题是指可在多项式复杂度是时间内验证问题的一个解
问题若可在多项式时间内求解则一定可在多项式时间内验证，反之不行，因此P是NP的子集
NP问题中有一部分可以证明比其他问题困难，称之为NPC问题

下周继续第四章公钥密码，数学铺垫终于结束了，后面是公钥密码体制。现在回想起来好像当时听蔡老师没讲多久，自己看居然要这么久Orz
mark当前92页