1新定义指挥旧公式10-2.pdf

1

新定义指挥旧公式

九省联考压轴题的启示

李尚志（北京航空航天大学）

一、九省联考压轴题

2024九省联考第19题.离散对数在密码学中有重要的应用.设p是素数,集

m,m

合X{1,2,...,p1}.若u,vX,mN,记uv为uv除以p的余数,u为u



2,p2,n,

除以p的余数;设aX,1,a,a,...,a两两不同,若ab(n{0,1,...,p2}),

则称n是b的以a为底的离散对数，记为nlog(p)b.

a



(1)若p11,a2,求ap,;



(2)对m,m{0,1,...,p2},记mm为m+m除以p1的余数(当m+m

12121212



被p1整除,mm0).证明:log(p)(bc)log(p)blog(p)c,其中b,cX.

12aaa

k,k,

(3)已知nlog(p)b.对xX,k{1,2,...,p2},令ya,yxb,证明:

a12



xyyn(p2),.

21



m,mp,11,10,

解.(1)按题目定义:u是u除以p的余数.因此,a22就是：



1011,

先算21024.再除以11得余数102493×111.答案：21.

(2)记nlog(p)b,mlog(p)b,

aa