感谢分享～

容我问一局 a三b(mod n)的三是什么意思

wendax 容我问一局 a三b(mod n)的三是什么意思

那叫 同余，不是3

编得不错，说真的没有看懂。

最近根据以上原理，自己设计了一个算法，该算法的以sqrt(n)作为起点，乘以2、3、5、7，放入一组数组中，再对这组数组进行比较（比较的方法与冒泡排序相似），看是否在设定的范围，在范围内，即分解该数，经在windows用DEV C++和red hat 7.5编译通过，经过测试，在2^63内的数，基本上能秒分解，与pollard_rho算法分解速度差不多，附件为C的源码(上传在正文中），共大家参考，如果有兴趣，可以共同探讨，研究更好、更快的整数分解的算法

上传的附件：

• dss6.c （5.49kb，4次下载）

一个求乘法逆元的方法
以下介绍一个素数求逆元的方法，与其它四种常见的求乘法逆元有所不同，主要是使用除数的积来求逆，供大家参考，如有不足，欢迎大家批评指正。
求a在p中的逆，其中p为素数，按以下公式求余：
  a*r1≡q1(mod p)  其中a*r1>p, a>q1
  q1*r2≡q2(mod p)  其中q1*r2>p, q1>q2
  q2*r3≡q3(mod p)  其中q2*r3>p, q2>q3
   .
   .
   .
   q(n-1)*rn≡1(mod p)  其中q(n-1)*rn>p, q(n-1)>1
   以上相乘得：
   a*r*q1*r2*...q(n-1)*rn≡q1*q2*...1(mod p)
   因假设p为素数，所以上式两边除q1*q2*...得：
   a*(r1*r2...rn)≡=1(mod p)
   即:a与r1*r2....*rn在p中互逆
   
   例如
   求24在83的逆元：
   24*4≡13(mod 83)
   13*7≡8  (mod 83)
   8*11≡5  (mod 83)
   5*17≡2  (mod 83)
   2*42≡1  (mod 83)
   4*7*11*17*42≡45 (mod 83)
   即24的逆元为45

   求25在83的逆元：
   25*4≡17(mod 83)
   17*5≡2  (mod 83)
   2*24≡1  (mod 83)
   4*5*42≡10 (mod 83)
   即25的逆元为10

   求25在131的逆元：
   25*6≡19  (mod 131)
   19*7≡2  (mod 131)
   2*66≡1  (mod 131)
   6*7*66≡21 (mod 131)
   即25的逆元为21

   求34在131的逆元：
   34*4≡5  (mod 131)
   5*27≡4  (mod 131)
   4*33≡1  (mod 131)
   4*27*33≡27 (mod 131)
   即34的逆元为27

 程序如下：

#include <stdio.h>
main()
{
    unsigned long a,b,n;
    unsigned long r,q,res;

    printf("输入两个数：\n");
    scanf("%ld%ld", &a, &n);

    b=a;
    if( a > n )
    {
       a=n;
       n=b;
    }
    res=1;
    while(1)
    {
       r=n/a;
       r++;
       q=r*a-n;
       res=(res*r)%n;
       if( q == 1 )
       {
          printf("%ld的逆%ld\n",b,res);
          printf("%ld*%ld=%ld(mod %ld)\n",b,res,(res*b)%n,n);
          break;
       }
       if( q == 0 || q == a )
       {
             printf("%ld存在因子%ld\n",n,a);
             break;
       }
       a=q;
    }
}