标签归档:数学

不得不说,化工版的高等代数与解析几何这本书实在是太烂了

最近学习数值线性代数,又翻出了化工版的高代与解析几何,自从学完高代这门课之后就没在碰过这书,现在翻出来一看,的确是恶心的不得了,每章都是将一点解析几何再讲一点高代,穿插着讲看不出整体结构,书的排版也不清楚,一坨一坨的文字没有重点。我们这届真是被毁了。

Advertisements

古典密码

凯撒密码(Caesar Shifts, Simple Shift)

也称凯撒移位,是最简单的加密方法之一,相传是古罗马恺撒大帝用来保护重要军情的加密系统,它是一种替代密码

加密公式:密文 = (明文 + 位移数) Mod 26

解密公式:明文 = (密文 – 位移数) Mod 26

以《数字城堡》中的一组密码为例:

HL FKZC VD LDS

只需把每个字母都按字母表中的顺序依次后移一个字母即可——A变成B,B就成了C,依此类推。因此明文为:

IM GLAD WE MET

英文字母的移位以移25位为一个循环,移26位等于没有移位。所以可以用穷举法列出所有可能的组合。

例如:phhw ph diwhu wkh wrjd sduwb

利用电脑可以方便地列出所有组合,然后从中选出有意义的话:

qiix qi ejxiv xli xske tevxc
rjjy rj fkyjw ymj ytlf ufwyd
skkz sk glzkx znk zumg vgxze
tlla tl hmaly aol avnh whyaf
ummb um inbmz bpm bwoi xizbg
vnnc vn jocna cqn cxpj yjach
wood wo kpdob dro dyqk zkbdi
xppe xp lqepc esp ezrl alcej
yqqf yq mrfqd ftq fasm bmdfk
zrrg zr nsgre gur gbtn cnegl
assh as othsf hvs hcuo dofhm
btti bt puitg iwt idvp epgin
cuuj cu qvjuh jxu jewq fqhjo
dvvk dv rwkvi kyv kfxr grikp
ewwl ew sxlwj lzw lgys hsjlq
fxxm fx tymxk max mhzt itkmr
gyyn gy uznyl nby niau julns
hzzo hz vaozm ocz ojbv kvmot
iaap ia wbpan pda pkcw lwnpu
jbbq jb xcqbo qeb qldx mxoqv
kccr kc ydrcp rfc rmey nyprw
ldds ld zesdq sgd snfz ozqsx
meet me after the toga party nffu nf bgufs uif uphb qbsuz oggv og chvgt vjg vqic rctva

可知明文为:meet me after the toga party

凯撒移位(中文版)

就是按照中文字在Unicode编码表中的顺序进行移位,可以用来加密中文的信息。

例:[中文凯撒移位]

移位后成为:[丮斈凰撓秼低]

栅栏密码(The Rail-Fence Cipher)

也称栅栏易位(Columnar Transposition),即把将要传递的信息中的字母交替排成上下两行,再将下面一行字母排在上面一行的后边,从而形成一段密码。栅栏密码是一种置换密码

例如密文:TEOGSDYUTAENNHLNETAMSHVAED

解密过程:先将密文分为两行

T E O G S D Y U T A E N N

H L N E T A M S H V A E D

再按上下上下的顺序组合成一句话

THE LONGEST DAY MUST HAVE AN END.


加密时不一定非用两栏,还是举《数字城堡》中的一个例子,密文为:

PFEE SESN RETM MFHA IRWE OOIG MEEN NRMA ENET SHAS DCNS IIAA IEER BRNK FBLE LODI

去掉空格:PFEESESNRETMMFHAIRWEOOIGMEENNRMAENETSHASDCNSIIAAIEERBRNKFBLELODI

共64个字符,以8个字符为一栏,排列成8*8的方阵(凯撒方阵):

P F E E S E S N
R E T M M F H A
I R W E O O I G
M E E N N R M A
E N E T S H A S
D C N S I I A A
I E E R B R N K
F B L E L O D I

从上向下竖着读:PRIMEDIFFERENCEBETWEENELEMENTSRESMONSIBLEFORHIROSHIMAANDNAGASAKI

插入空格:PRIME DIFFERENCE BETWEEN ELEMENTS RESMONSIBLE FOR HIROSHIMA AND NAGASAKI (广岛和长崎的原子弹轰炸的最主要区别)


栅栏密码也可以用于中文,不过比较容易破解。

明文:这是中文的栅栏密码

密文(3*3方阵):这文栏是的密中栅码

由于中文用规则的栅栏比较容易破解,所以产生了一些变体,例如道家心法密籍《天仙金丹心法》中的一段加密方法。密文如下:

○ 茫 天 : 摹 然 月 终 为 鼎 半 是 真 灭 器 轮 假 不 但 伸 净 著 定 分 泥 万 ○ 无 ○ 光 人 经 法 一 从 尘 色 返 我 权 自 法 中 妙 大 空 照 生 屈 来 好 路 形 神 海 ○ 便 还 未 归

○ 茫
天 : 摹
然 月 终 为
鼎 半 是 真 灭
器 轮 假 不 但 伸
净 著 定 分 泥 万 ○
无 ○ 光 人 经 法 一 从
尘 色 返 我 权 自 法 中 妙
大 空 照 生 屈 来 好 路 形 神
海 ○ 便 还 未 归

明文(从左至右读竖行):天然鼎器净无尘,大海茫茫月半轮。著色空摹终是假,定光返照便为真。不分人我生还灭,但泥经权屈未伸。万法自来归一法,好从中路妙形神。


利用电脑进行加密或解密,建议使用“列举加密”或“列举解密”,电脑会自动尝试一些正好匹配的栏位进行列举。

lyiroonevuclesey

4栏:
loveyousincerely

8栏:
lionvceeyroeulsy

维吉尼亚密码(Vigenère Cipher)

由于频率分析法可以有效的破解单表替换密码,法国密码学家维吉尼亚于1586年提出一种多表替换密码,即维吉尼亚密码,也称维热纳尔密码。维吉尼亚密码引入了“密钥”的概念,即根据密钥来决定用哪一行的密表来进行替换,以此来对抗字频统计。

加密算法:例如密钥的字母为[d],明文对应的字母[b]。根据字母表的顺序[d]=4,[b]=2,那么密文就是[d]+[b]-1=4+2-1=5=[e],因此加密的结果为[e]。

加密公式:密文 = (明文 + 密钥) Mod 26 – 1

解密即做此逆运算。

解密公式:明文 = [26 + (密文 – 密钥)] Mod 26 + 1

也可以用查表法来进行加密:例如密钥的字母为[d],明文对应的字母[b],在下图的表格第一行找到字母"d"(深蓝色),再在左边第一列找到字母"b"(绿色),两个字母的交叉点(b行d列)就是字母"E",所以对应的密文字母为[e]。

假如对如下明文加密:

to be or not to be that is the question

当选定“have”作为密钥时,加密过程是:密钥第一个字母为[h],明文第一个为[t],因此可以找到在h行t列中的字母[a],依此类推,得出对应关系如下:

密钥:ha ve ha veh av eh aveh av eha vehaveha

明文:to be or not to be that is the question

密文:ao wi vr isa tj fl tcea in xoe lylsomvn

Polybius密码(Polybius Cipher)

也称棋盘密码,是利用波利比奥斯方阵(Polybius Square)进行加密的密码方式,产生于公元前两世纪的希腊,相传是世界上最早的一种密码。

假设我们需要发送明文讯息 “Attack at once”, 用一套秘密混杂的字母表填满波利比奥斯方阵,像是这样:

    A D F G X
A b t a l p
D d h o z k
F q f v s n
G g j c u x
X m r e w y

i和j视为同一个字,使字母数量符合 5 × 5 格。之所以选择这五个字母,是因为它们译成摩斯密码时不容易混淆,可以降低传输错误的机率。使用这个方格,找出明文字母在这个方格的位置,再以那个字母所在的栏名称和列名称代替这个字母。可将该讯息转换成处理过的分解形式。

明文:A T T A C K A T O N C E

密文:AF AD AD AF GF DX AF AD DF FX GF XF

A,D,F,G,X也可以用数字1,2,3,4,5来代替,这样密文就成了:

13 12 12 13 43 25 13 12 23 35 43 53

ADFGX/ADFGVX密码(ADFGX/ADFGVX Cipher)

ADFGX

1918年,第一次世界大战将要结束时,法军截获了一份德军电报,电文中的所有单词都由A、D、F、G、X五个字母拼成,因此被称为ADFGX密码。ADFGX密码是1918年3月由德军上校Fritz Nebel发明的,是结合了Polybius密码置换密码的双重加密方案。A、D、F、G、X即Polybius方阵中的前5个字母。

明文:A T T A C K A T O N C E

经过Polybius变换:AF AD AD AF GF DX AF AD DF FX GF XF

下一步,利用一个移位密钥加密。假设密钥是“CARGO”,将之写在新格子的第一列。再将上一阶段的密码文一列一列写进新方格里。

C A R G O
_________
A F A D A
D A F G F
D X A F A
D D F F X
G F X F X

最后,密钥按照字母表顺序“ACGOR”排序,再按照此顺序依次抄下每个字母下面的整列讯息,形成新密文。如下:

FAXDF ADDDG DGFFF AFAXX AFAFX

在实际应用中,移位密钥通常有两打字符那么长,且分解密钥和移位密钥都是每天更换的。

ADFGVX

在1918年6月,再加入一个字V┏洹1涑梢?×6格共36个字符加密。这使得所有英文字母(不再将I和J视为同一个字)以及数字0到9都可混合使用。这次增改是因为以原来的加密法发送含有大量数字的简短信息有问题。

乘法密码(Multiplication Cipher)

乘法密码也是一种简单的替代密码,与凯撒密码相似,凯撒密码用的是加法,而乘法密码用的自然是乘法。这种方法形成的加密信息保密性比较低。

加密公式:密文 = (明文 * 乘数) Mod 26

对于乘数密码,只有当乘数与26互质时,加密之后才会有唯一的解,因此乘数只可能有如下11种的选择:

乘数 = 3,5,7,9,11,15,17,19,21,23,25

仿射密码希尔密码因为都用到了乘法,所以乘数也受到相同的局限。

仿射密码(Affine Shift)

仿射密码就是凯撒密码乘法密码的结合。

加密公式:密文 = (明文 * 乘数 + 位移数) Mod 26

希尔密码(Hill Cipher)

希尔密码就是矩阵乘法密码,运用基本矩阵论原理的替换密码。每个字母当作26进制数字:A=0, B=1, C=2… 一串字母当成n维向量,跟一个n×n的密钥矩阵相乘,再将得出的结果模26。希尔密码的优点是完全隐藏了字符的频率信息,弱点是容易被已知明文攻击击破。

加密

例如:密钥矩阵

1 3

0 2

明文:HI THERE

去空格,2个字母一组,根据字母表顺序换成矩阵数值如下,末尾的E为填充字元:

HI TH ER EE

8 20 5 5

9 8 18 5

HI 经过矩阵运算转换为 IS,具体算法参考下面的说明:

|1 3| 8 e1*8+3*9=35 MOD26=9 =I

|0 2| 9 e0*8+2*9=18 MOD26=18=S

用同样的方法把“HI THERE”转换为密文“IS RPGJTJ”,注意明文中的两个E分别变为密文中的G和T。

解密

解密时,必须先算出密钥的逆矩阵,然后再根据加密的过程做逆运算。

逆矩阵算法公式:
|A B| = 1/(AD-BC) * | D -B|
|C D|                 |-C    A|

例如密钥矩阵=
|1 7|
|0 3|
AD-BC=1*3-0*7=3 3*X=1 mod26 所以 X=9
因此
|1 7| 的逆矩阵为: 9 * |3 -7|
|0 3|                  |0    1|

假设密文为“FOAOESWO”

FO AO ES WO
6    1    5 23
15 15 19 15

9* |3 -7| | 6| = 9*(3*6-7*15)=-783 mod26 = 23=W
     |0    1| |15| = 9*(0*6+1*15)= 135 mod26 = 5 =E

所以密文“FOAOESWO”的明文为“WEREDONE”

Playfair密码(Playfair Cipher)

Playfair将明文中的双字母组合作为一个单元对待,并将这些单元转换为双字母组合。加密后的字符出现的频率在一定程度上被均匀化。

5*5变换矩阵(I或J视为同一字符):

C I P H E
R A B D F
G K L M N
O Q S T U
V W X Y Z

加密规则:按成对字母加密

  1. 相同对中的字母加分隔符(如x)

  2. ballon -> ba lx lo on

  3. 同行取右边:he->ec

  4. 同列取下边:dm->mt

  5. 其他取交叉:kt->mq    od->tr

例如:ballon -> ba lx lo on -> db sp gs ug

摩斯电码

摩斯电码(摩尔斯电码)是一种发报用的信号代码,是一种替代密码,用(Dot)和(Dash)的组合来表示各个英文字母或标点。

国际标准摩斯电码表

1

*—-

A

*-

N

-*

[.]

*-*-*-

2

**—

B

-***

O

[,]

–**–

3

***–

C

-*-*

P

*–*

[:]

—***

4

****-

D

-**

Q

–*-

[‘]

*—-*

5

*****

E

*

R

*-*

[?]

**–**

6

-****

F

**-*

S

***

[-]

-****-

7

–***

G

–*

T

[()]

-*–*-

8

—**

H

****

U

**-

[@]

*–*-*

9

—-*

I

**

V

***-

[—]

-***-

0

—–

J

*—

W

*–

分数线

-**-*

K

-*-

X

-**-

L

*-**

Y

-*–

终了[\r]

***-*-

M

Z

–**

始信[\n]

-*-*-

例:Hello (斜线代表字母之间的间隔)

****/*/*-**/*-**/—/

置换密码(Transposition Cipher)

也称易位密码

windows 下dev c++安装gsl的方法

GNU数学函数库gsl在windows下的移植
1.gsl在dev-c++下的移植:
(1)下载gsl-1.8.exe:
 http://gnuwin32.sourceforge.net/packages/gsl.htm
(2)安装gsl,安装后在安装目录下将有如下目录
\contrib\gsl-1.8 一些说明文件
\bin 二进制文件
     libgsl.dll             gsl的动态链接库(基于gcc的正式版本)
     libgsl_d.dll           gsl的动态链接库(基于gcc的调试版本)
     libgslcblas.dll        cblas的动态链接库(基于gcc的正式版本)
     libgslcblas_d.dll      cblas的动态链接库(基于gcc的调试版本)
     gsl-histogram.exe      用于计算数据直方图的程序
     gsl-randist.exe        用于生成服从指定分布数据的程序
\lib 库文件
     libgsl.a                gsl的静态链接库(基于gcc的正式版本)
     libgsl_d.a              gsl的静态链接库(基于gcc的调试版本)
     libgslcblas.a           cblas的静态链接库(基于gcc的正式版本)
     libgslcblas_d.a         cblas的静态链接库(基于gcc的调试版本)
     libgsl_dll.a            libgsl.dll的gcc输入库
     libgsl_d_dll.a          libgsl_d.dll的gcc输入库
     libgslcblas_dll.a       libgslcblas.dll的gcc输入库
     libgslcblas_d_dll.a     libgslcblas_d.dll的gcc输入库
     libgsl.def              输出libgsl.dll的定义
     libgslcblas.def         输出libgslcblas.dll的定义
\doc 有关文档
\info
\man1
\man3
     各种格式的gsl帮助文件
\include\gsl 头文件
     gsl include files
     其中使用到的主要有bin,lib,include\gsl下的文件
 (3)设置dev-c++编译环境,有两种方式:
 一、这种最简单,将gsl安装目录下的bin下libgsl.dll,libgslcblas.dll复制到dev-c++安装目录下的bin目录下;lib下libgsl.a,libgslcblas.a复制到dev-c++安装目录下的lib目录下;include下的整个gsl文件夹复制到dev-c++安装目录下的include目录下。打开dev-c++,工具-编译选项-编译器,选上“在连接器命令行加入如下命令”,加入-lgsl -lgslcblas(即在连接时连上libgsl.a,libgslcblas.a,gcc可以自动识别前缀lib和后缀.a)
  #i nclude <stdio.h>
  #i nclude <gsl/gsl_sf_bessel.h>
int main(void)
  {
    double x = 5.0;
    double y = gsl_sf_bessel_J0(x);
    printf("J0(%g) = %.18en", x, y);
    system("pause");
    return 0;
  }移植
 可以正常运行。
 二、打开dev-c++,工具-编译选项-目录,分别将gsl安装目录下的lib,include加入到库和头文件的路径中。最后,在编译器选项中,选中“在连接器命令行加入如下命令”,加入-lgsl -lgslcblas,即可以正常使用gsl。
—————————————————————-
事实证明第一种方法比第二种可靠:)

介绍个数学库gsl(GNU Scientific Library)

转载:

1.主页
http://www.gnu.org/software/gsl/

2.下载源码及manual
ftp://ftp.gnu.org/gnu/gsl/gsl-1.7.tar.gz
http://www.gnu.org/software/gsl/manual/gsl-ref.ps.gz

3.编译安装
(我用的是FC4)
./configure –diable-shared
make
make install

4.测试
4.1写个testgsl.c:
#include &lt;stdio.h&gt;
#include &lt;gsl/gsl_sf_bessel.h&gt;

int main(void)
{
  double x = 5.0;
  double y = gsl_sf_bessel_J0(x);
  printf("J0(%g) = %.18e\n",x,y);
  return 0;
}

4.2编译
gcc  -Wall -c testgsl.c

4.3链接
gcc -o testgsl testgsl.o -lgsl -lgslcbas -lm

4.4运行
./testgsl
输出:
J0(5) = -1.775967713143382920e-01

5.补充
5.1关键是platform independent及 distributed under the terms of the GPL
5.2更多内容看manual
5.3gsl的插件看主页
5.4在windows下的应用看
http://www.hebl.name/zh/archives/gsl-win32/#more-111

常用数学软件介绍

MathCAD

   MathCAD是由MathSoft公司推出的一种交互式数值系统。该软件定位于向广大教师、学生、工程人员提供一个兼备文字处理、数学和图形能力的集成工作环境使他们能方便地准备教案、完成作业和准备科学分析报告。Mathcad在对待数值计算、符号分析、文字处理、图形能力的开发上,不以专业水准为追求,而尽力集各种功能为一体。需讲究精度、速度、算法稳定性的数值计算问题和需经复杂推理的符号运算问题,都不是Mathcad所致力解决的目标。在输入一个数学公式、方程组、矩阵之后,计算机能直接给出结果,而无须去考虑中间计算过程。最令人激动的是在加入软件包自带的Maple插件后能直接支持符号运算。你可以在计算机上输入数学公式、符号和等式等,很容易地算出代数、积分、三角以及很多科技领域中的复杂表达式的值,并可显示数学表格和图形,通过对图形结果的分析,使我们对问题的理解更加形象。
   Mathcad的用户主要针对具备应用数学知识但并不要求具有较多的计算机知识的用户,如工程研究人员、学生等。

Matlab

   MATLAB是一个高性能的科技计算软件,广泛应用于数学计算、算法开发、数学建模、系统仿真、数据分析处理及可视化、科学和工程绘图、应用系统开发, 包括建立用户界面。当前它的使用范围涵盖了工业、电子、医疗、建筑等各领域。
   MATLAB是英文Matrix Laboratory(矩阵实验室)的缩写,最早是由C.Moler用Fortran语言编写的,用来方便地调用LINPACK和EISPACK矩阵代数软件包的程序。后来他创立了MATHWORKS公司,对MATLAB作了大量的、坚持不懈的改进。现在MATLAB已经更新至6.5版,MATLAB提供的工具箱已覆盖信号处理、系统控制、统计计算、优化计算、神经网络、小波分析、偏微分方程、模糊逻辑、动态系统模拟、系统辨识和符号运算等领域。

Mathematica
   Mathematica是由美国Wolfram公司研究开发的一个数学软件,它提供了与Mathcad和Matlab这两个著名数学软件同样强大的功能,能够完成符号运算、数学图形绘制甚至动画制作等多种操作。
   Mathematica是目前比较流行的符号运算软件之一,它不仅可以完成微积分、线性代数及数学各个分支公式推演中的符号演算,而且可以数值求解非线性方程、优化等问题。它不仅是数学建模的得力助手,也是大学数学教育和科学研究不可或缺的工具。

Maple

   Maple是加拿大滑铁卢大学(University of Waterloo)和Waterloo Maple Software公司注册的一套为微积分、线性代数和微分方程等高等数学使用的软件包。它是当今世界上最优秀的几个数学软件之一,它以良好的使用环境、强有力的符号计算、高精度的数值计算、灵活的图形显示和高效的编程功能,为越来越 多的教师、学生和科研人员所喜爱,并成为他们进行数学处理的工具。
   Maple软件适用于解决微积分、解析几何、线性代数、微分方程、计算方法、概率统计等数学分支中的常见计算问题。
   Maple采用字符行输入方式,输入时需要按照规定的格式输入,虽然与常见的数学格式不同,但灵活方式,也很容易理解。输出则可以显字符方式和图形方式,产生的图形结果可以很方便地剪贴到Windows应用程序内。

SCILAB

SCILAB是以法国国立信息与自动化研究院(INRIA)的科学家为主体共同开发的“开放源码”科学自由软件。SCILAB与MATLAB的起源相同,都源自Cleve Moler与1980年开发的程序。因此它们二者个功能类似,而且大部分的指令、语法等也都类似。
SCILAB是一种解释性语言,能运行与Linux、Windows以及UNIX等操作系统下。用户可以从SCILAB主页下载最新的安装版本进行安装使用。
SCILAB 为用户提供优秀的计算和开放式编程环境:包含多种容易操作的数据结构;一个作为广泛计算基础的合理有效的基本函数集;一个开放式编程环境,新的函数能很容易的被添加。Intersci是一个有用的发布工具,通过它能建立接口,添加新的函数和工具箱。例如可以添加新的Fortran和C代码到SCILAB 中。
SCILAB还包括一些应用于不同科学计算领域的工具箱,如数学建模、信号处理、网络分析、决策优化、线形与非线形等多个方面。安装文件中就包含有多个常用工具箱:Scicos(图形化动态模拟仿真器)、Signal(信号处理工具箱)、 Control(控制工具箱)和Metanet(图形和网络工具箱)等。

Leonhard Euler 我心目中最伟大的数学家

把拉格朗日点说成欧拉点_-_
把柯西定理说成欧拉定理_-_
最近到底是怎么了_-_
Euler, Leonhard (1707-1783)
Swiss mathematician who was tutored by Johann Bernoulli. He worked at the Petersburg Academy and Berlin Academy of Science. He had a phenomenal memory, and once did a calculation in his head to settle an argument between students whose computations differed in the fiftieth decimal place. Euler lost sight in his right eye in 1735, and in his left eye in 1766. Nevertheless, aided by his phenomenal memory (and having practiced writing on a large slate when his sight was failing him), he continued to publish his results by dictating them. Euler was the most prolific mathematical writer of all times finding time (even with his 13 children) to publish over 800 papers in his lifetime. He won the Paris Academy Prize 12 times. When asked for an explanation why his memoirs flowed so easily in such huge quantities, Euler is reported to have replied that his pencil seemed to surpass him in intelligence. François Arago said of him "He calculated just as men breathe, as eagles sustain themselves in the air" (Beckmann 1971, p. 143; Boyer 1968, p. 482).

附:Nineteen Proofs of Euler’s Formula: V-E+F=2