为什么不使用大于 10 位的数字？

Question

你好社区我有以下问题对于超过10位的数字，以下代码不收敛到任何解决方案，并且不知道问题出在哪里，因为知道数字是素数会满足费马小定理一个调用函数。

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

unsigned long exp_mod(unsigned long x, unsigned long y, unsigned long n)
{
    unsigned long s,t,u;
    int i;
    s=1; t=x; u=y;
    while(u) {
        if (u&1) s=(s*t)%n;
        u>>=1;
        t=(t*t)%n;
    }
    return s;
}

int main(){
    unsigned long number,a,b;
    int i;
    printf("introduce number to test\n");
    scanf("%lu",&a);
    number=a;
    srand((unsigned int)time(0));

    while (1) {
        a=rand()%(number-1)+2;//0<a<number
        b=exp_mod(a,number-1,number);
        if ( b==1 ) {
            printf ("by Fermat:  %lu is prime\n",number);
            break;
        }
    }
    return 0;
}

有什么建议吗？问候

Answer 1

在大多数编译器和系统上，unsigned long 的大小是 32 位，所以它大约是 4 * 10^9 - 这就是它不能处理 10 位数字的原因。只需将 unsigned long 更改为 unsigned long long int。

Answer 2

这里是代码，然后是为您提出的解决方案，谢谢！

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

main()
{
 mpz_t b;
 mpz_init(b);
 int escero;
 unsigned long numero,a;
…
 printf("Introduzca el numero a testear\n");
 scanf("%lu",&a);
 numero=a;
 srand((unsigned int)time(0));
 mpz_t A,P,P1;
 mpz_init(A); mpz_init(P); mpz_init(P1);
…

 while (1) {
        a=rand()%(numero-1)+2;//0<a<numero
        mpz_set_ui(A,a);
        mpz_set_ui(P1, (numero-1) );
        mpz_set_ui(P,numero);
        mpz_powm( b, A, P1, P);//b=exp_mod(a,numero-1,numero);
        //gmp_printf("a^p-1 [mod p] = %Zd\n",b);
        if ( !mpz_cmp_d(b,1) ) {
…
         printf ("%lu es testigo por Fermat de que %lu es primo\n",a,numero);
         break;
         }
        }
 return 0;
}

再次感谢社区！！

为什么不使用大于 10 位的数字？

Why not work with numbers greater than 10 digits?

c

primes

rsa