QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2447|回复: 0
打印 上一主题 下一主题

一个乘法逆元的计算方法

[复制链接]
字体大小: 正常 放大
songls        

6

主题

3

听众

23

积分

升级  18.95%

  • TA的每日心情
    郁闷
    2023-12-11 09:00
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    跳转到指定楼层
    1#
    发表于 2023-12-10 20:02 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。% j% X+ G/ z7 r; |4 K
    设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m- J- A4 H) }, z' [) p
      a*r1≡q1 (mod n)0 }* y) W2 y* O; u. U. A) E7 W
      q1*r2≡q2 (mod n)9 c7 }: Q0 j6 Q1 m1 j
      q2*r3≡q3 (mod n); p* v# J( B2 p- W
       .4 f& h* b; J' D
       .
    8 g# I& N$ d) D4 W5 h9 u$ G  .5 k8 S' L3 p* \1 B9 `
      qm-1*rm≡qm (mod n); U5 ^" ^3 n) I4 M2 L
    上述等式相乘,得:
    , _; t$ O" D# y7 b/ I  Z: v% f  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>0 C! \7 H7 M4 w' H
      a*(q1*q2*...*qm)≡rm (mod n) / h8 d9 h# P; G) d* ^
      如果对qi(1≤i≤m)进行如下的限定:
    ) f/ a4 V, K5 V9 `" U$ b  L   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|3 M6 j( x4 M( S( O5 W; z2 l
       则 qm=±1' K+ }; _) y; Y% c& v! i
      即 a与q1*q2*...*qm互逆
    3 v; z% I1 o/ Q$ I/ s  例 求28在299的逆/ C) T$ Q1 x: _0 A
         28*11≡9 (mod 299)8 V( Y4 N" j0 q1 o) L1 P
         9*33≡-2  (mod 299)
    ! r3 S5 }& H9 o' ?7 l7 e/ @     -2*-150≡1 (mod 299)" ~+ X" P/ j6 C7 q6 g
      逆为:    11*33*-150≡-32 (mod 299)
    ( o! }, S. n; Z) [     28*-22≡-1 (mod 299)' g7 }) i' e# t5 e+ N8 J
      但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
    $ J$ z$ r1 O# P6 X' D* j 下面给出其中一个算法:
    % M2 U3 P/ h; o/ o( H  1    输入a,n  5 u" k" Z( `. ]' ?
      2   resulte = 1   ; 保存逆的结果
    " O9 _# X& s- k2 X' J4 `0 H  3   r=n/a+1      ; 保证 r*a>n
    + q* s0 Y( f2 F# |: h1 C# S  4  q=r*a-n       ; 得到余数,该余数小于a, Z) |" D+ f( s0 B
      5  resulte=(resulte*r)%n   
    0 i+ m5 A' Y7 ?0 Y  6  if q=1  then  print(逆为: resulte) return  resulte
      w8 `+ c" t$ V  7  if q=0 or q=a then  print(存在因子: a)  return a ;
    9 C7 I6 Y. [& g! G# B" P  8  a=q9 o1 n  e0 }. B; T
      9  goto 30 d4 a% P) [$ m& h' |
    + e- D" n# E, Q1 N. k! I

    一个求乘法逆元的方法.pdf

    39.85 KB, 下载次数: 0, 下载积分: 体力 -2 点

    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-8 21:57 , Processed in 0.359355 second(s), 53 queries .

    回顶部