QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2547|回复: 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
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
    / Z: n  [( }. V设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m0 Y6 B& W# _+ {( }( ]8 R
      a*r1≡q1 (mod n)
    7 H' M5 b; a4 H2 ?+ E: S  q1*r2≡q2 (mod n)4 M. f& X. P! o  q2 T8 e, V5 r( q0 e. k
      q2*r3≡q3 (mod n)! Z; }+ @8 ]# `/ Y4 l# N
       .0 x( Q! f/ v. Z- \
       .
    ) R8 }7 Y3 O* V# b- I6 E  ./ J3 U, W; s$ o  x8 h# E- b
      qm-1*rm≡qm (mod n)3 Q% r) I  v: A6 V+ l  E1 m  [
    上述等式相乘,得:8 _% i( j3 o: A+ P# D; q
      a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>! O+ l7 w  r& m- A$ c& T4 E
      a*(q1*q2*...*qm)≡rm (mod n)
    / C, e+ U, j5 o5 i& i+ f  如果对qi(1≤i≤m)进行如下的限定:: g2 ]* s8 u4 Z
       a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|0 J8 f8 k6 M3 o$ s0 c
       则 qm=±1
    0 Q1 [- m: ~) C4 t; K# N  即 a与q1*q2*...*qm互逆' ~* U5 Q+ i; U
      例 求28在299的逆
    $ k/ q. \& D% H4 P6 Q- b     28*11≡9 (mod 299)
    . _& ]  W$ c4 s     9*33≡-2  (mod 299)6 R. M" q) F, l( A) T% ]# w+ }
         -2*-150≡1 (mod 299)
    # D7 a  q$ H/ w  逆为:    11*33*-150≡-32 (mod 299)
    . W& w) ~' f3 g# }4 ]     28*-22≡-1 (mod 299); g6 Q& F" s1 ]
      但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。( W, ]- M, ^' ]; d
    下面给出其中一个算法:
    # N4 ^; w. Y! Y/ g' c+ Z, O  1    输入a,n  
    ( l  d; P/ @* z  2   resulte = 1   ; 保存逆的结果
      ?/ K. N2 B- d; V  3   r=n/a+1      ; 保证 r*a>n
      V$ G5 t& K3 S% P# y7 T" J, Y  4  q=r*a-n       ; 得到余数,该余数小于a
    9 U( ^& F( ?" O% q: D4 H) x5 P  \  5  resulte=(resulte*r)%n   + ~3 G. o( f: U: U! C8 C
      6  if q=1  then  print(逆为: resulte) return  resulte8 N5 k# {! c- {" S- M
      7  if q=0 or q=a then  print(存在因子: a)  return a ;
    ( h# ~1 `0 C7 O2 K  8  a=q
    ( z: Y4 \: y9 S4 z4 a9 K  9  goto 3
    * _' C$ y7 d* a7 Z+ D% t" m
    ! M" r% }' q6 P9 O

    一个求乘法逆元的方法.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-7-24 10:08 , Processed in 0.304114 second(s), 53 queries .

    回顶部