近世代數思想方法在數論中的應用

(6頁)

本資源提供全文預覽，點擊全文預覽即可全文預覽,如果喜歡文檔就下載吧，查找使用更方便哦！

9.9 積分

近世代數思想方法在數論中的應用2007年5月第26卷第5期綿陽師范學院JournalofMianyangNormalUniversityMay.,2007V01.26NO.5近世代數思想方法在數論中的應用張清,唐再良(綿陽師范學院數學與信息科學系，四川綿陽621000)摘要:討論了近世代數思想方法在證明初等數論定理和素數判斷中的應用,介紹了 素數判斷的多項式時間方法.關鍵詞:群;環;模;數論;素數中圖分類號:0156.2文獻標識碼:A文章編1672-612x(2007)05-0012-031引言數論一度被認為是漂亮的但卻沒什么大用處的純數學學科?30多年來，電子計算 機的產生與發展，給科學技術帶來無比巨大的變革，這使數論有了非常廣泛的盲接應用途徑?例如在近 20年來發展起來的高維數值積分的數論網格法的研究中，數論的成果被廣泛應用?其中，有關數論算法 的廣泛使用，部分是因為基于大素數的密碼系統的發明?數論更是數學研究的重要內容之一?數論知識在 計算機科學,通訊及商業等領域都有著重要的應用.數論的問題以其抽象且難度大而著稱，眾所周知，抽象也是近世代數的最大特點.近世代數不僅在數學屮占有及其重要的地位,而且在其它學科中也有廣泛的應用，如理論物理，計算 機學科等?其研究的方法和觀點，對其他學科產牛了越來越大的影響.同時近世代數思想方法多年以來也一 直都被用到數論問題的處理中，特別是用到費爾馬最后定理的處理.下面我們通過幾個初等數論定理的 處理來介紹近世代數思想方法在初等數論中的運用.2群論思想在數論定理證明中的應用群論是代數學中最古老最豐富的分支之一，群論思想在近代物理，近代化學，數字 通信,系統工程等許多領域都有重要應用，同時群的思想方法也促進了數學科學本身的發展.下面我們 通過幾個初等數論的定理處理來介紹群論思想方法在數論中的應用.定理1 (Fermat)設P是一個素數且口是一個不能被P整除的自然數，那么 lmodp.證明:考慮modP的非零剩余類組成的乘法群G二{1,2,???,P — 1}.對于口是一個不 能被P整除的自然數,口?二(口)一= 1.所以口一 E1 moap.推論:設P是素數且口是自然數，那么=amodp.證明:如果P整除口，那么;amodp.如果P不整除口，那么由定理1可得?;lmodp.以 上兩種情況都可以得到一 amodp.定理2(Euler)設n>l是自然數且口是與n互素的整數,那么口;lmodn.證明:考慮modn的剩余類屮單位元作成的群G={Igcd(x,n)=l}.則G的階為(n).對 于任意與n互素的整數口,1-1=()1.所以)=lmodn.收稿日期:2007-04-27作者簡介:張清(1976 —)，男，碩士，研究方向:代數與符號計算.第5期張清等:近世代數思想方法在數論中的應用？13?定理3(Wilson)設P是素數，那么(P — 1)!~ 1 [email?protected]{1,2,…,P — 1}.因為s 1 modp當且 僅當(一l)(+l)sOmodp當且僅當s± 1 modp,所以對于任意的H± 1,H?.所以(p — l)!=(lxp一 1)Xn(X)=lXP— 1 二一 1.所以(p — 1)!;— 1 modp.Ec—1± il3環論思想在數論定理證明屮的應用環也是近世代數中一類重要的，基本的代數系統，環論思想與群一樣有著廣泛的應 用?下面我們通過初等數論的定理處理來說明環論思想方法在數論中的應用.定理4(Fermat)設是P奇素數.Kp;lmod4,那么P是兩個平方的和,即存在整數,Y使 得P=+2Y0證明:由于是偶數,那么一 [email?protected])@逆元配 對,1與P— 1;一 [email?protected] X2X???X_X — IX— 1 X---X—_所以[()!]；- lmodp如果一 l;2modp,那么P整除+1.現在我們在高斯整數環Z[i]中分解+1為(一 i)(+i). 既然P不能整除任一個因子，那么P在Z[i]中不是素數?因為高斯整數環是唯一分解環,P 是可約的?所以我們就寫P二，其中和盧都不是單位.定義y=a+bi的范數為N(7)=a+6.那么N(7)=l當且僅當y是1,一 1,咸一 i當且僅 當y是單位?所以P=N(p)=N(Ot)N(fl),其中 N(Ot)>l 且 N(fl)>l, 所以 N(Ot)=N(fl)=P.女口果 6二+iy,男么 P二+.反乙如果P是奇素數且p=+Y,那么P同余于lmod4.［如果是偶數，那么=Omod4, 且如果是奇數，那么；lmod4.由于P是奇數，和Y不能同時為偶數或奇數?］定理5(Wolstenh.lme)如果是p —個大于3素數，那么1 + 1 +了 1+???+的分子能被p2 整除證明:設)=(一 1)(- 2)…(一(P — 1)).將)展開成的幕級數形式)=_?一 S1 一+s2 —+ Sp?2?+Sp — 1其中的一些系數能很簡單的寫出?比如,s=l+2+???+(p — l)=;sp —=(p — l)!;s 一=(1 ++—+…+)X(p — 1)!.這樣我們就建立了與原問題的聯系.而其他的系數我們就把他 [email?protected]，根據費爾馬小定理,)在0巾可［］中的像就是(一1)( 一2)…(一(P 一 1))=?一 1.所以對任意的i<P 一 1,S是P的倍數.P)二(P — i)!=o).所以 O::pP?pp —.pP —.+S1,?3P —$p?2這是P 一 1個數的和，前P —2個數都是P的倍數?所以一是p的倍數.由于(p — l)!;lm?如,(p — 1)!與p互素?所以1+丟+ —+???+就是p.的倍數.914?綿陽師范學院(自然科學版)第26卷問題:口,b,c在什么情況下，｛口 ++C1WZ｝含有無限多個素數.4模方法在素數判斷中的應用素數的定義其實就給出了判斷素數的方法:嘗試每個mW,如果有一個m整除//,, 則〃，是合數，否則凡是素數.篩法生成所有小于n的素數.但這些算法的效率不高?需要()步才能決 定?[3]用近世代數的模方法給出了多項式時間算法.引理1[3]:設口是整數，凡是大于2的自然數且(口,n)=l.那么凡是素數當且僅當(戈+ 口 )=戈 + 口 (modn)利用這個引理判斷素數的吋候，最多需要計算等式左邊n個系數.于是我們可以模 一 1(其中r比較小)來減少需要計算的系數的個數.凡是素數當且僅當(+口);+ 口(modx 一 l,n)對所有的 口和匸而當凡是合數時，只對少數的口和滿足上述等式.定義1:設口是整數,r是自然數且(口,「)=1 ?定義口模r的階為最小的正整數使得 口 ;l(modr).記為0,( 口).算法】：(AKS)輸人整數N>l1 .如果(n= 口，其屮口是自然數,b>l),輸出合數.2?找到最小的r使得0,(n)>log2(n).3?如果存在口 Wr使得1 <( 口 ,n)<n,輸出合數.4.如果nWr,輸岀素數.5?從口=1 到 Iog(n)l 做:如果(+口)H+ □ (modx 一 l,n),輸出合數.6.輸出素數.定理1[31:AKS算法返冋素數當口僅當凡是素數.定理2[3] :AKS算法的極限時間復雜度為0(1 ogn)=O(l og7 ?n?poly(l og(l ogn)))HendrikLenstra和CarlPomerance改進了算法，其時間復雜度為O(log.n).如果下面 的猜想成立，AKS吋間復雜度可以進一步改進為0(logn)?E4]已經驗證了當1W100 口 nWlOm 時，猜想正確.猜想:設r是素數且不能整除n.如果(一 1) 1 (modx 一 l,n),那么凡是素數或n;l(modr).參考文獻：[llRobertB.Ash.AeouI^einalgebraicnumbertheory.Onlinepreprintbook^OOS.[2] DaveRusin,Wolstenholme-congruence.0nlinelecturenotes.2006.[3] Agrawal,KayalandSaxena(AKS),PrimesisinP.AnnualofMathematics,2004( 160):781-793[4] KayalandSaxena(AKS),Towardsapolynomialtimetest.2002.[5] R.BhattaeharjeeandP.Pandey,Primalitytesting.2OO 1.TheApplicationofModernAlgebra ?Way ofThinkinginNumberTheoryZHANGQing,TANGZai—liang(DepartmentofMathematicsandInformationScience,MianyangNormalUniversity,Mian yang,Sichuan621000)Abstract:Inthispaper,wefirsthaveadiscussionofthealgebraapproachforsometheoremsinelementarynumbertheory,andthenwehaveanintroductiontothepolynomialtimeinthejudgmentofpri menumbe r.Keywords:group;ring;module;numbertheory;primenumber 關?鍵?詞： 近世 代數 思想 方法 數論 中的 應用

?天天文庫所有資源均是用戶自行上傳分享，僅供網友學習交流，未經上傳用戶書面授權，請勿作他用。

總結

以上是生活随笔為你收集整理的数论在计算机科学中的应用,近世代数思想方法在数论中的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。