数论理论介绍

数论理论介绍第1页，课件共26页，创作于2023年2月本讲介绍数论的概念及在galois域中计算的概念第2页，课件共26页，创作于2023年2月1.数论介绍数论概念:研究“离散数字集合”运算是“+”,“×”例:整数:5+9=14;5×3=5+5+5=15

多项式:x2+1+x=x2+x+1;x×x2+1=x3+x

第3页，课件共26页，创作于2023年2月运算概念运算:模数运算模多项式运算进一步运算:指数运算,逆运算理解公钥算法的基础第4页，课件共26页，创作于2023年2月2.整除对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子记作b|a

例1,2,3,4,6,8,12,24整除24

第5页，课件共26页，创作于2023年2月3.素数与不可约多项式素数:只有因子1和自身1是一个平凡素数例2,3,5,7是素数,4,6,8,9,10不是素多项式或不可约多项式irreducible:不可写成其他因式的乘积

x2+x=x×x+1是非不可约多项式;x3+x+1是不可约多项式第6页，课件共26页，创作于2023年2月4.一些素数200以内的素数:

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199第7页，课件共26页，创作于2023年2月5.素数分解(PrimeFactorisation)

把整数n写成素数的成绩分解整数要比乘法困难整数n的素数分解是把它写素数的乘积eg.91=7×13;3600=24×32×52

第8页，课件共26页，创作于2023年2月6.整数互素整数a,b互素是指它们没有除1之外的其它因子8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子

第9页，课件共26页，创作于2023年2月8.模算式除法取余运算同余(congruence)fora=bmodn

如果a,b除以n,余数相同eg.100=34mod11

b叫做a模n的剩余通常0<=b<=n-1

eg.-12mod7=-5mod7=2mod7=9mod7可以进行整数运算第10页，课件共26页，创作于2023年2月9.,模运算举例-21-20-19-18-17-16–15-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456

78910111213141516171819202122232425262728293031323334第11页，课件共26页，创作于2023年2月10.模算术运算加法a+bmodn

减法a-bmodn=a+(-b)modn

第12页，课件共26页，创作于2023年2月11.乘法\除法乘法a.bmodn

重复加法除法

a/bmodn

乘以b的逆元:a/b=a.b-1modn

如果n是素数,b-1modn存在s.tb.b-1=1modn

例.2.3=1mod5hence4/2=4.3=2mod5

第13页，课件共26页，创作于2023年2月12模递归运算模递归运算是“模除求余”例.r=amodn计算a=d.n+r

33mod7=4.7+5;得数是5

通常,r取正数例-18mod7=-3.7+3;答案是3

a+/-bmodn=[amodn+/-bmodn]modn

第14页，课件共26页，创作于2023年2月13.运算法则类似于正常算术运算:结合律:(a+b)+c=a+(b+c)modn

交换律分配律(a+b).c=(a.c)+(b.c)modn

加法单位元\乘法单位元0+w=wmodn

1×w=wmodn

乘法运算类同

第15页，课件共26页，创作于2023年2月14群.环.域群的定义:一些数字组成的集合一个加法运算，运算结果属于此集合（封闭性）服从结合律。有单位元，逆元如果是可交换的，则成为abelian群第16页，课件共26页，创作于2023年2月15。环环:abelian群，及一个乘法运算：满足结合律与加法的分配律如果加法满足交换律,则称交换环例：整数modN（foranyN）第17页，课件共26页，创作于2023年2月16。域域：abelian加群环abelian乘群(ignoring0)例：integersmodP（P为素数）第18页，课件共26页，创作于2023年2月17。Galois域如果n是素数p

则模运算modulop形成GaloisFieldmodulop

记为：GF(p)

第19页，课件共26页，创作于2023年2月18。GF(p)中的指数运算许多加密运算需要指数运算b=aemodp

重复乘法运算eg.75=7.7.7.7.7

一个好的方法是不是平方和乘法第20页，课件共26页，创作于2023年2月19。平方、乘法运算计算指数的快速有效算法思想：重复平方运算计算最终结果的乘法运算第21页，课件共26页，创作于2023年2月20。平方乘法运算例75=74.7=3.7=10mod11;3129mod11=4

·

letbase=a,result=1·

foreachbitei(LSBtoMSB)ofexponent

·

ifei=0then·

squarebasemodp·

ifei=1then·

multiplyresultbybasemodp·

squarebasemodp(exceptforMSB)·

atendtherequiredanswerisresult第22页，课件共26页，创作于2023年2月21。平方乘法举例75=74.7=3.7=10mod11

baseresexp(5=1012)71nitialise7.7=49=51.7=7result=resultxbase,squarebase)5.5=25=30(squarebase)3.3=97.3=21=101(result=resultxbase,squarebase)第23页，课件共26页，创作于2023年2月22。GF(p)中的离散对数指数的逆问题是寻找整数模p的离散对数即：求x使得ax=bmodp

eg.x=log34mod?(iexst.3x=4mod?)无解eg.x=log23mod13=4（利用连续实验）计算指数相对容易，求离散对数一般很难可以证明若p素数,则总存在离散对数（foranyb!=0）a的连续指数可以生成群（thegroupmodp）a叫做一个本原根（aprimitiveroot）较困难的问题第24页，课