QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1867|回复: 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
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
    , K% |5 {! G7 ^2 n3 s5 \3 Z. R设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m9 V5 t) ~4 j. A+ z
      a*r1≡q1 (mod n)7 W4 V* S  r! Q5 z: a" e* z
      q1*r2≡q2 (mod n)
    : ^/ F+ @8 W% L# ]* `/ u; D  q2*r3≡q3 (mod n)
    , Y7 J; v, g2 m+ Y   .
    6 K* B$ z, r# ~4 I2 S+ E   .
    ; }3 w8 `/ n% I3 `9 e9 _  .$ s, n% d  {5 [
      qm-1*rm≡qm (mod n)/ L, l( R7 |% t& @
    上述等式相乘,得:1 C* ^- a( B& ]3 `
      a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>2 U, d3 s8 `" S( t- ~) O; r
      a*(q1*q2*...*qm)≡rm (mod n) , P2 m7 z5 w/ g0 R
      如果对qi(1≤i≤m)进行如下的限定:/ ^7 {1 o2 |9 S3 j! _1 \* R
       a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|* l2 C1 Q+ G7 W# m" p4 C% m
       则 qm=±1
    & \' S8 w* h) i  即 a与q1*q2*...*qm互逆
    8 u0 _4 m: g& w( T, N1 r& P  例 求28在299的逆
    & n! f$ |/ B1 u/ K" T' b     28*11≡9 (mod 299)+ X, l* {: j0 u
         9*33≡-2  (mod 299)
    % S( g7 D+ w2 y, c% _0 A     -2*-150≡1 (mod 299)
    ; i% g0 F8 F) {% T/ b  逆为:    11*33*-150≡-32 (mod 299)
    8 o# I5 k: z2 Q& f" u     28*-22≡-1 (mod 299)
    3 }3 L: P4 T. u' V) [  但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。$ c7 S. L# \2 g- \+ O' \* D
    下面给出其中一个算法:5 h- G7 U- N. \6 A8 n) a. O
      1    输入a,n  
    - I0 a& ^- n$ f4 I- ~  2   resulte = 1   ; 保存逆的结果 / e( a1 X. G: p* |
      3   r=n/a+1      ; 保证 r*a>n
    ; Y: O) f8 p4 r0 Q8 y  4  q=r*a-n       ; 得到余数,该余数小于a0 W+ L% G9 O( Y3 ]& S( }/ Z7 t4 y
      5  resulte=(resulte*r)%n   
    % j: g3 R( i/ h; K  b  6  if q=1  then  print(逆为: resulte) return  resulte& k. u4 Y4 i; K9 z; S
      7  if q=0 or q=a then  print(存在因子: a)  return a ;1 _! \. G% S, j; X( x
      8  a=q2 i( X6 }: W! g
      9  goto 3
    ) g% q1 r2 Y" S; Z4 w( v" O- P& o$ h0 F( |

    一个求乘法逆元的方法.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, 2025-7-16 02:09 , Processed in 0.742600 second(s), 54 queries .

    回顶部