QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2404|回复: 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
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。7 o* F# A8 R/ R  [8 Y
    设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m" p: R; u! P+ S$ }' [7 u4 l  C5 s
      a*r1≡q1 (mod n)
    , E+ N6 ?2 z; r( a$ M" u; ~  g  q1*r2≡q2 (mod n)9 M/ O# U4 u: O! d1 q* a0 Y
      q2*r3≡q3 (mod n)/ x5 F& d; {) |2 q
       .
    6 ^3 H$ O7 j6 V$ E! h$ E; O% A   .8 f; q# Q8 D3 A$ x* H. L, e
      .. P; v, |0 r' D; z  {% x& a
      qm-1*rm≡qm (mod n)
    1 }8 f/ w/ t7 N" c# j, s) Z8 l$ I* c 上述等式相乘,得:' D# ^) m' w; v2 _& E. Y' X! R
      a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>
    8 ?6 Y" B) Z. u4 }+ R$ V8 s  a*(q1*q2*...*qm)≡rm (mod n)
    * G. {/ V. C: Z" q3 h4 P! u9 v  如果对qi(1≤i≤m)进行如下的限定:' U0 j5 x# T5 F) R5 r% @
       a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|% L5 H! ^# Y) i- G3 d0 s4 L9 z
       则 qm=±1
    . t+ D+ [/ V& b- ~9 M: \. ?  即 a与q1*q2*...*qm互逆. ?: F+ b* h% Q# z' W% J
      例 求28在299的逆
    6 a/ h4 X* \! F3 G7 D; G     28*11≡9 (mod 299)
    " B2 m) M* N! N7 L1 o     9*33≡-2  (mod 299)4 l/ m* {& V2 z: K( o* {. ^6 ?
         -2*-150≡1 (mod 299)
    ) A$ Z/ t- V# V) s  逆为:    11*33*-150≡-32 (mod 299). |8 N( d4 y, m" t# C
         28*-22≡-1 (mod 299)
    8 }& U/ W" v% _: o  但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。
    ' Z# z' e! B; C 下面给出其中一个算法:8 [* b. T, l  c% L1 k' O% r5 b
      1    输入a,n  
    0 M& M5 \. ^, T; Q  2   resulte = 1   ; 保存逆的结果
      x5 `# s2 m2 `. U8 C3 |7 s  3   r=n/a+1      ; 保证 r*a>n
    2 o  N. z8 h# z- Y. U  4  q=r*a-n       ; 得到余数,该余数小于a( W' W: I7 L0 @+ e. _" C
      5  resulte=(resulte*r)%n   7 ~& H; u6 K/ B2 S( w5 o" N
      6  if q=1  then  print(逆为: resulte) return  resulte# d& s; ]: E  e
      7  if q=0 or q=a then  print(存在因子: a)  return a ;, n6 F+ E! d) |$ @: X- W% I
      8  a=q  v3 w, B1 k4 Z" \) |# A, |
      9  goto 3
    5 M) A7 j9 _6 [$ q9 V: \  S$ z4 L4 A0 a3 y) l/ D6 q! B

    一个求乘法逆元的方法.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-4-14 23:11 , Processed in 0.401411 second(s), 53 queries .

    回顶部