QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2474|回复: 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
    以下给出一个求乘法逆元的方法,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。
    - D3 d  V! @- P设 (a,n)=1  (ri,n)=1  (qi,n)=1  1≤i≤m
    . o. w0 [- R+ c8 C% E; R  a*r1≡q1 (mod n)& Z3 Q0 m6 R0 z. E7 }: @" |& K$ q# W
      q1*r2≡q2 (mod n)" p0 M1 p6 E% [2 l. a3 S* E1 V
      q2*r3≡q3 (mod n)# S: s+ g7 T5 U# u: g/ U7 s' m
       .
    6 V, ?# F6 h8 A$ f+ b   .5 L5 K, }! ]4 @
      .
    / ?. j7 K; r7 ^% n- _2 o; e  qm-1*rm≡qm (mod n)
    ' K8 X- {( d$ q9 l, S* E1 m 上述等式相乘,得:5 P5 h3 J9 f8 c# X. U( X% L
      a*(r1*r2*...*rm-1)*(q1*q2*...*qm)≡r1*r2*...*rm-1*rm (mod n) =>  ~  M  G3 J) q: L' _0 ]
      a*(q1*q2*...*qm)≡rm (mod n) 4 Y8 P# t9 x" j
      如果对qi(1≤i≤m)进行如下的限定:
    , Y" K. X$ g- V4 z1 ]   a>|q1|>|q2|>...>|qi|>...>|qm-1|>|qm|4 c, f7 @7 H/ E, k2 W* y
       则 qm=±1* t- `  ~7 x! J- D( f" Q7 L9 z3 m
      即 a与q1*q2*...*qm互逆1 l! a% {2 x3 F: k4 w  x( B; m0 W
      例 求28在299的逆
    + z! L; d; _% Y3 g+ d     28*11≡9 (mod 299)
    ' u. B/ V2 X6 |% W, v     9*33≡-2  (mod 299)# N/ g$ Q* i2 z. C
         -2*-150≡1 (mod 299)
    3 Z# X8 n. a( m) w# C  逆为:    11*33*-150≡-32 (mod 299)" H# }$ B) ?1 G/ i8 D
         28*-22≡-1 (mod 299)" B, m9 r, h- \7 c, _* \" {% \) G, u
      但该方法有个最大的问题,当(qi,n)>1时,该方法将无法继续往下计算逆。7 z" N+ l4 U9 H- I: f
    下面给出其中一个算法:
    ; i' u! B4 n) E" P: O; t: h8 I  1    输入a,n  
    : k. `* @; {# ]3 Q# [- v  2   resulte = 1   ; 保存逆的结果
    # s- j" J6 h! `; V  3   r=n/a+1      ; 保证 r*a>n- D0 @5 z: D5 Z% M$ G% R
      4  q=r*a-n       ; 得到余数,该余数小于a
    5 |# A9 q# {" j: b! e  5  resulte=(resulte*r)%n   6 A* E" a1 P! X! r" M
      6  if q=1  then  print(逆为: resulte) return  resulte: u- J4 r7 H( c) Z+ V, U3 m7 v
      7  if q=0 or q=a then  print(存在因子: a)  return a ;
    2 l, _$ ^$ T6 d1 R$ U1 C" G  8  a=q7 h* [  h+ _: V9 |: n
      9  goto 34 f8 q# ]! x# x$ S# D/ ]
    ; F1 N* ^: s& f- I+ C

    一个求乘法逆元的方法.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-27 15:29 , Processed in 0.744937 second(s), 52 queries .

    回顶部