QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1829|回复: 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
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。" h: v  l7 S7 @. O7 _( n0 Z
    设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m" P' b& g, F/ T: s# }: [# a
      a*r1≡q1 (mod n)% h" i, X6 T; H  l4 r. A
      q1*r2≡q2 (mod n)* r, x+ u: |* K
      q2*r3≡q3 (mod n)
    , n1 c  @- e5 L# P. ^   .
    . q) Z0 H/ M3 u# H3 ?8 c- {. C   .
    . C( G# g% Y+ ]) Q  .
    6 P, `( e# k) X" _3 R, D  qm-1*rm≡qm (mod n)
    # q; f; B3 @3 W5 | 上述等式相乘,得:
    . p7 M5 V5 B" C, z! `/ V  a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>1 S8 W+ c# D& P5 m- A
      a*(q1*q2*...*qm)≡rm (mod n) % a- S6 Z( M4 e; Q7 Q4 P& I
      如果对qi(1≤i≤m)进行如下的限定:/ x2 W5 \9 w9 p: T) \
       a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|
    2 [! U/ t0 K; {( c; l# g- v- m   则 qm=±1
    & V; E! N7 W9 U, z' @) M& R. B  即 a与q1*q2*...*qm互逆
    . m5 D6 y+ n  }& `9 G: g7 M7 K  例 求28在299的逆
      [- E) x9 U. R7 p, ?) M! q1 e     28*11≡9 (mod 299)/ Z0 A# u4 e  ]% q* p" s
         9*33≡-2  (mod 299)/ O- o9 ~9 Z( L! I- M2 H8 R/ E
         -2*-150≡1 (mod 299)
    % q+ p2 I9 j4 ^3 ?3 f  逆为:    11*33*-150≡-32 (mod 299)# k9 I" R3 `! Q$ |% \
         28*-22≡-1 (mod 299)
    - R; s3 t; z; Z' f  但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。# i# A- Z% i3 y
    下面给出其中一个算法:% N1 M: V! U4 T- z5 R
      1    输入a,n  
    ! v" T6 q- a0 G% H* R/ V  2   resulte = 1   ; 保存逆的结果
    / ]: W( g" e/ M: I- ~( j0 u  3   r=n/a+1      ; 保证 r*a>n
    5 L2 Y1 {0 X8 _. c  V  4  q=r*a-n       ; 得到余数,该余数小于a
    - w3 _3 e! Y0 j1 o) i" n4 L; k6 I" o  5  resulte=(resulte*r)%n   
    ! `! ^7 W& @1 B2 q3 y  6  if q=1  then  print(逆为: resulte) return  resulte
    , a7 Y4 T0 K3 X6 R; a7 f1 E  ?  7  if q=0 or q=a then  print(存在因子: a)  return a ;6 L, q) w+ u9 f8 F7 ~  J7 |
      8  a=q
    2 |( w0 W% A6 z3 N( c+ F% m! p0 v4 s# ?  9  goto 38 o) x; o2 @1 {3 j
    6 d7 e, x6 v* Q) u( U5 H7 o# Q; E

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

    回顶部