factoring.c

来自「RSA公钥加密的基本实现 bmp灰度图片加解密操作包括 RSA 的加减密算法； 」· C语言 代码 · 共 62 行

#include <stdlib.h>
#include <stdio.h>

#include <math.h>
#include <time.h>
#include "RSA.h"

unsigned gcd(unsigned, unsigned);
unsigned GMI(unsigned long long, unsigned);
unsigned Pollard_P_1(unsigned n, unsigned B)
{
    unsigned a=2;
    unsigned j;
    srand(time(0));
    do
    {
        a=rand()%(n-3)+2;//2 <= a <= N - 2 ( with a
        for (j=2;j<=B;j++)
        {
            a = fast_exp(a, j, n);
        }
    }
    while (a==1);
    a = gcd(a-1, n);

    if (a>1&&a<n)
        return a;
    else
        return 0;
}



unsigned pollard_p(const unsigned  c,const unsigned num)
{
    int i=2,k=2;
    srand(time(0));
    unsigned x=rand()%num;
    unsigned y=x,comDiv;
    do
    {
        i++;
        if ((x=fast_exp(x,x,num)-c)<0)
            x+=num;
        if (x==y)
            break;
        comDiv=gcd((y-x+num)%num,num);
        if (comDiv>1 && comDiv<num)
            return comDiv;
        if (i==k)
        {
            y=x;
            k<<=1;
        }
    }while(1);
    return num;
}