欧拉函数的一些性质(1).pdf

《欧拉函数的一些性质(1).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、飞’年第期通信保密总第期欧拉函数的一些性质少李武传冲·西安电子科技大学应用数学系西安摘要数论中存在着许多难题,很多密码体制就是以这些难题为安淦性基础的。在这些密码体制中,欧拉函数起着重要作用。本文给出了欧拉函数的一些重要而有趣吻性质,这些性质可对密码的设计与分析起指导作用。【关键词欧拉函数公钥密码体制七,,七,,心,,,”由于数论中存在许多人们多年来一直未能解决的难题‘’』,许多建立在这些难题几‘’的密码体制被提出来了著名的公钥密码体制和数字签名方案就是建立在大整数的素因子分解这一难题上的。在这些密码体制中,欧接函数对于体制的安全性起着至关重要的作用。为此

2、,我们在本文中给出有关欧拉函数的一些有趣的性质,供密码体制的设·训和分析者参考。本文于年月日收到。定义设是正榷数,的欧拉函数功定义为不大于的与互素的正整数的个数。根据定义,不难得到下述性质性质设刀是素数,则‘‘’功一性质设,,,则功功功性质设一川川二,争,,,⋯,,为不同的素数,则‘‘’”势一一一一—,—一性质“点功一以几性质是人们比较熟悉的,它们可川来计算某个整数的欧拉函数值。为了进一步讨论欧拉函数值的性质,先给出一引理对任意素数刀,有,二证明二因是素数,故存在榷数使一一,,从而一一勿一·。,,。,,一切在与川必有一个是偶数这就证明了勿另一方而因一,而牛

3、夕,一,一,因,一故必有即此得。或三性质功功‘证明利月】性质可以得到性质设为不含「再囚子的奇数,且冬,则。三一“,功功其,,,,表示所含有的不同素因子个数。‘,,。证明设一则日又根据引理,‘‘功一功八,子一自子一夕三一夕盆一月一功功尸‘一一,一刀‘,里‘忿一’,二一故得功功三一·功性质价二证明根据定义和性质容易证得。下而对公钥密码体制‘,的欧拉函数作进一步讨论。性质设一,与为大的两个不相同的素数,则功价‘,。。,一价及可证明根据性质功一价下而只需证明功山,。,性质得功一价功一功一一一因一一及一祁是偶数,故只需证明它们中至少有一个含有。事实,若勿一或一,则。

4、,,,,结论成立否则夕一必可写为“因此一一、,。。伏即有一综我们就证明恒等式推论设一,与为大的两不同素数,则必存在整数,使功几一证明结合性质与性质可以证得。性质设,与为两个不同的素数,则有’,一‘一勿。‘一‘万万证明经验证可得。设,并令,记‘一’一“一‘万万我们得到下而的重要性质,它可川来判别体制中真正的欧拉函数值。山性质知仅当任才,才有可能是的欧拉函数值。·’。二,」一性质创设与为两不同的索数刀一与都分别有一个大的素因子夕与叮、,满足,沪,,则对任意‘,一价的充分必要条件是二参考文献,一,一一’,,·,亏,,一